Doubt regarding Segment Trees

See usually we all implement segement trees using recursion which we all know is slower than iterative so my question is if in a solution can it be a case that if i apply the segment tree(recursion) solution it’s giving me TLE (as it is) but when i change my strategy to Fenwick tree it can pass the time limit?

Yes, it’s possible. However, it’s usually quite rare, and either requires the solution to be O(n\log^2{n}) (or worse) in the first place or the problem having very stupid high constraints like greater than 10^6.

1 Like

Okay thanks :grinning:

Btw, can you please tell which resource to go for to study seg trees and fenwick trees. Is cp-algorithms good for it :sweat_smile:

Probably. My advice is to read the theory, let it sink in, then try to implement it from scratch instead of copying code. If you can do that, it’ll confirm that you really understand it.

Another thing you can do is write tutorial blogs (:slight_smile:) - it’ll really force you to rehash and understand the material, to an extent where you can explain it intuitively to others


Thanks for the reply : D

Can you also please explain that what is the point of having a build function in segment trees I mean we can just update the values in the segment tree as we receive them, I always prefer to have only 2 functions in my segment trees (range and query) and it worked every time up until now then why do people have a build function ?

Build is O(n), while inserting elements via queries is O(n\log{n}). Most standard implementations have build because it’s asymptotically good, so most people using those implementations also have build for themselves. However, it’s not strictly necessary, and doing it your way likely won’t cause any problems.

1 Like

thanks ! :innocent:

also, check Everything about Segment tree blog. It might be useful.