Re:Show HN: O(log n) makes continuous profiling possible
by knuthsat on Wednesday March 17, 2021 @06:58AM
(#26489267)
Decoding the k-th permutation:
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.
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.