Segment trees are data structures commonly used in competitive programming. It was really interesting seeing it used here!
That said, I wonder if there are any real-world comparisons on production code?
That said, I wonder if there are any real-world comparisons on production code?
RE comparisons: Do you mean comparisons of some production profiling data with versus without this compression?
I know also of examples where lazy segment tree is used too.
Segment trees can also be used to decode the kth lexicographic permutation of a sequence of elements in O(n log n) instead of O(n ^ 2).
Here's one variant of the above application: https://www.spoj.com/problems/QUE2/
The only way I can currently envision a segment tree being used for a problem like that is grouping elements every k to provide a faster lookup.
Like, these k elements have a value < x, the next k elements have a value < y, etc.
1: 1 2 3 4 5
2: 1 2 3 5 4
3: 1 2 4 3 5
Number 3 codes into operations that manipulate 1 2 3 4 5 sequence ( https://en.wikipedia.org/wiki/Factorial_number_system ):
1. get 0th elem twice (1 2) 2. get 1st elem (4) 3. get 0th elem twice (3 5)
The data you are maintaining in the segment tree allows you to get the elements out of 1 2 3 4 5 sequence in O(log n), and when you remove the element O(log n), the structure can tell you again what the k-th element is.
If you hold the data in a normal array, you get quadratic algorithm.
Of course, you can use a different tree that allows you to get the k-th element of a sorted sequence but segment trees are easy to code in comppro setting.