|
|
|
|
|
|
by ZephyrBlu
1926 days ago
|
|
|
The first example makes sense, but could you elaborate on decoding permutations with that problem? 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.