Menu
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.
335
asked Feb 16 '15 05:02
Construction of Segment Tree from the given array: We start with a segment arr[0 . . . n-1]. and every time we divide the current segment into two (if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node.
Segment tree can be used to do preprocessing and query in moderate time. With a segment tree, preprocessing time is O(n) and the time complexity for a range minimum query is O(Logn). The extra space required is O(n) to store the segment tree.
The height of the segment tree is O(log n) because while moving from the root to the leaves at every level, the length of the segments is reduced by half. The total number of nodes involved in the segment tree is 4*n.
Size of the Array Used in Segment Tree Representation If the size of the input array is of power 2, then there are no dummy nodes. Thus, the size of the segment tree is (2 * n - 1), where n is the size of the input array. It is because the total number of leaf nodes will be s, and internal nodes will be n - 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).
55
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
