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

Автор T1duS, история, 6 лет назад, По-английски

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

??

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

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

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

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

it's pretty easier to understand

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

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

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

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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

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

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

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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.