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.
Post Reply
angelus
Posts: 1
Joined: 6 years ago
Gender: None specified

Range Trees

Post by angelus » 6 years ago

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: 6 years ago
Gender: None specified

Re: Range Trees

Post by melkor » 6 years ago

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!

Post Reply

Return to “Algorithms”