STL for segment tree in C++

Question

Is there any STL for segment tree?

In competitive programming it takes a lot of time to code for seg tree. I wonder if there is any STL for that so that lot of time could be saved.

Costive

Related: https://mcmap.net/q/80524/-why-does-the-c-stl-not-provide-any-quot-tree-quot-containers/252576 – Steerageway

Answer 1

I assume by "segment tree" you actually mean range tree, which is more commonly used in programming contests than the more specialized structure for storing a set of intervals.

There is no such container in the C++ standard library but if you are competing in ACM contests you can consider writing your own and simply copying it as needed. You can find my own implementation here (including lazy propagation) but if you search the web you can probably find a more generic version.

In applications where you need the sum instead of the minimum or maximum, you can use a binary indexed tree instead of a segment tree, which is faster, uses less memory, and is also easier to code (about a dozen lines or less).

Baleen

Although this is totally unrelated, and I'm sorry that if it goes against SO rules, but I'm suddenly in awe of seeing your answer just above mine. I follow you on Quora as well (I'm the guy who was against letting felons vote, and had commented the same on your answer), so this was definitely a pleasant surprise. PS: If such a comment is against the rules, let me know and I will delete it. – Banquer

Why is there no segment tree / fenwick tree built into STL? IMO that'd be a really cool and helpful feature to add. – Freed

Answer 2

There is no STL in C++ for segment tree. However, you can check out the Boost Library called Interval Container Library (ICL) which should satisfy your requirements.

Banquer