Блог пользователя who_i_am

Is interval tree is segment tree?
Автор who_i_am, история, 9 месяцев назад, По-английски

Can you answer my questions?

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      → Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks

    → Ответить