Range Trees

[angelus]

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]

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!