T1duS's blog

Why do most people use recursive segment tree?
By T1duS, history, 7 years ago, In English

Why do most people use recursive segment tree when-
1. It is slower
2. It takes more memory
3. It is longer to code
4. It is harder to understand

??

  • Vote: I like it
  • -30
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by T1duS (previous revision, new revision, compare).

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

Well, in my opinion it's quite the opposite. At least for me the iterative approach is somewhat harder to understand than the recursive one. I mean in recursion you literally write what you want to do, there's nothing to think about. Also recursion is a lot more fun to write. But yeah, after you understand iterative approach there's no reason not to use it.

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

it's pretty easier to understand

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

I think it's because it's easier to understand and to modify(lazy updates, persistency...).

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

In competitive programming there is a lot of stuff that matters. This ain't it.

To answer your questions:

  1. Not significantly.
  2. Not significantly (and for some implementations, the only extra memory is on the stack).
  3. Not significantly.
  4. Not for them, that's why they do it.

If I had to implement a segment tree right now, I would use a vector of vectors to store its layers, and I would implement the functions recursively, because currently for me that's the most convenient way to do it. If the constant factors really mattered I could do it another way, but if these constants do matter, the problemsetter is probably doing something horribly wrong anyway.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Actually, I found there's at least one advantage of recursive segment tree over an iterative one (aside from the fact lazy propagation is much nicer like that): You might want to use a segment tree of, say, subarrays in your array, and the merging function (the one you use in querying to merge the answers of all the elements you need, like minimum function) is only able to merge subarrays that share a mutual end (they're next to each other). In this case, what you might notice is that you can make the recursive segtree merge all the needed subarrays in order from left to right, while an iterative segtree merges without any strict order (it starts at both ends, sometimes adds to the left part, sometimes to the right, etc). I'm not sure if that's possible to do iteratively, and if so, I don't know how comfortable it will be to code.

An example problem can be this, where the author's solution is to build a segment tree of such blocks, and merging can only be done to adjacent blocks.

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

    No, iterative segtree supports non commutative combiner operations. So, a strict ordering is maintained.

    → Reply
»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Ok got it. I guess everyone finds recursive segtree easier to understand. Well, we all have different opinions. Personally, I do not at all myself get the idea of recursive segtree. I find it pretty confusing.

→ Reply