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
??
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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
??
Name |
---|
Auto comment: topic has been updated by T1duS (previous revision, new revision, compare).
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.
it's pretty easier to understand
I think it's because it's easier to understand and to modify(lazy updates, persistency...).
In competitive programming there is a lot of stuff that matters. This ain't it.
To answer your questions:
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.
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.
No, iterative segtree supports non commutative combiner operations. So, a strict ordering is maintained.
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.