STL for segment tree in C++

c++ algorithm stl segment-tree
Ankita Singh picture Ankita Singh · Feb 16, 2015 · Viewed 6.9k times · Source

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.

Answer

Brian Bi picture Brian Bi · Feb 16, 2015

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).

Related questions

Is it more efficient to copy a vector by reserving and copying, or by creating and swapping?

I am trying to efficiently make a copy of a vector. I see two possible approaches: std::vector<int> copyVecFast1(const std::vector<int>& original) { std::vector<int> newVec; newVec.reserve(original.size()); …

Read More
Use of for_each on map elements

I have a map where I'd like to perform a call on every data type object member function. I yet know how to do this on any sequence but, is it possible to do it on an associative container? The …

Read More
Where can I get a "useful" C++ binary search algorithm?

I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_search in the standard library's <algorithm> header, but I need it to return the iterator that points at the result, …

Read More