who_i_am's blog

Is interval tree is segment tree?
By who_i_am, history, 10 months ago, In English

Can you answer my questions?

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty much the answer

Or in short, no.

As far as I know, I don't see many problems that can only be solved by using interval trees (or I am dumb, I do not know much of its properties anyway), so for now the latter one is enough. We need to learn things that are more useful first.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Not entirely. There are two different concepts called "segment tree".

    The first one is what the top answer in StackOverflow is talking about, and also what the Segment tree article in Wikipedia talks about. It's something to do with counting the number of intervals that cover a given point.

    The second one is more or less a term only used within competitive programming: a perfectly balanced binary tree where each node maintains the sum (or any other monoid) of its descendant leaves.

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

      Oh, I see, that's why a lot of people (including me) see both of them as one sometimes. I was really surprised back then when saw that the interval tree was a different data structure.

      Thanks a lot!

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

    thanks

    → Reply