Faygoat's blog

Differences between Segment Tree, Interval Tree, and Range Tree
By Faygoat, 12 years ago, In English

Hi,

I see a lot of solutions use these terms interchangeably, especially Range Tree and Segment Tree. I know how to implement a segment tree very well because I've done it multiple times in problems. However, not an interval tree or range tree. Do you need a heap like tree, or do you need a self balancing BST for it (I can't implement any at the moment. which ones should I learn)? Also, according to the wikipedia article, you can query the number of points in a 1-D, 2-D, or n-Dimensional area using a range tree, but can't you do the same thing with a 1-D, 2-D, or n-D Fenwick (Binary Indexed) Tree?

Please, someone answer me, and maybe give examples of problems solvable using a range tree?

Your help is very appreciated!!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Afaik using a Fenwick tree to count the number of points in a nD area is possible. The operations of a basic FT are update value[i] to new_val, and get the sum of value1..i. If you consider value[i] to be the number of points at position i, then it's easy to see how you can count points in range [a,b] efficiently in 1D case — it's just the difference between sums of ranges [1,b] and [1,a-1]. Higher dimensions are possible using a similar approach.

I've never used a RT or ST yet (but I'm just a secondary school competitor, so that doesn't mean it's useless :D), but I've been using IT rather frequently, sometimes coupled with lazy loading. The progression FT — IT — IT+LL (in increasing order of simplicity) has proved deadly for many tasks, in my competition experience :D So I'd advise you to learn a short and clear implementation of an interval tree...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes I've used a segment tree in many problems, as well as a 1 dimensional BITs and 2 dimensional BITs.

    I've looked at Interval Trees online, but do you have a link to a clear explanation/implementation of one? Also do you need a code a BST from scratch for an interval tree? or is it just arranged like a heap (like the segment tree).

    thanks for your answer!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      IT is arranged pretty much like a heap, but you still need to code it... here's an implementation of a sum-IT (a slightly modified extract from some solution; slightly modified = I'm too lazy to debug :D): http://ideone.com/a7X9cP

      But the best way to learn an implementation is to write your own while thinking through what it's supposed to do — the 2nd time you do it, it's much faster than the first time!

      → Reply