Faygoat's blog

By Faygoat, 5 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  

»
5 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...

  • »
    »
    5 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!

    • »
      »
      »
      5 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!

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

        Oh, haha! This was the question I wanted to address. That appears to be what I was calling a "segment tree" before. although It doesn't have "Lazy propagation", or "lazy loading" as you have called it. People use these terms interchangably so its hard to know exactly what they're talking about unless theres code. Here's what wikipedia says about interval trees: http://en.wikipedia.org/wiki/Interval_tree

        It appears you have to augment a BST (which is why I mentioned it)