Range Trees

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
angelus
Posts: 1
Joined: Mon Dec 26, 2011 4:55 pm
Gender: None specified

Range Trees

Postby angelus » Mon Dec 26, 2011 5:18 pm

Someone who can help me with trees range? I've been studying this programming paradigm, but I really do not know how to encode.
If anyone can help me it would be greatly appreciated.
thanks



melkor
Posts: 3
Joined: Wed Dec 21, 2011 11:16 am
Gender: None specified

Re: Range Trees

Postby melkor » Tue Jan 03, 2012 6:10 pm

I have discovered that all algorithms using range/segment trees share a common pattern, a template if you like. It's something like this:

Code: Select all

void Update(int node, int lo, int hi)
{
    if (lo == hi)
    {
        // this is a leaf, update it
        UpdateInfo(node);
        return;
    }

    int mid = (lo + hi) / 2;

    // assuming our tree is zero-based
    update(2 * node + 1, lo, mid);
    update(2 * node + 2, mid + 1, hi);

    // update the current non-leaf node, generally
    // using the info stored at its children

    // these are just dummy names
    UpdateInfo(T[node].info, T[2 * node + 1].info, T[2 * node + 2].info);
}

[some type] Query(int node, int lo, int hi)
{
    if (lo == hi)
    {
        // the same as before
        return T[node].info; // or something alike
    }

    int mid = (lo + hi) / 2;
    [some type] res = ExtractInfo(Query(2 * node + 1, lo, mid), Query(2 * node + 2, mid + 1, hi));
    // that is, we're using the info provided by the queries on the children to compute
    // the general query

    // do something with the info stored at this node
    CombineInfo(result, T[node].info);

    return result;
}


As you can see, these are (very) general ideas, but the core of your code will always look like this.

Range/segment trees can be used in virtually all problems concerning intervals and/or queries on them. One classic application of the data structure is for solving the Range Minimum/Maximum Query (RMQ) problem, or processing a large amount of queries on the sum of intervals over a long sequence of numbers.

Again, just general ideas. Look at some of these classical problems.

Good luck!


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest