## 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:

### Range Trees

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:

### Re: Range Trees

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!