4 ms·

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

by zwliew 6y ago

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?

petethepig 6y ago
Thanks! We loved geeking out on all of these data structures and algorithms. RE comparisons: Do you mean comparisons of some production profiling data with versus without this compression?
ZephyrBlu 6y ago
How are segment trees used in competitive programming? I can't immediately see how they would be useful in that situation.
- knuthsat 6y ago
  Any dynamic programming algorithm where n-th item depends on contiguous k ones with some nice binary operation (like +) can benefit from storing the state in a segment tree, so when you go and calculate n-th item, you can get the value in log(n) instead of O(k) (although prefix sums work fine there too if + is involved). 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/ https://www.spoj.com/problems/QUE2/
  - ZephyrBlu 6y 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.
    - knuthsat 6y ago
      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 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.
- vladimirralev 6y ago
  Competitive programming problems are often designed with intended solution technique in mind first so whatever the trendy thing to do is finds its way into the competitions. Segment trees used to be popular but less so now because it's unfair to some languages. Python and C++ competitors can often work around a segment tree with a sortedlist/ordered_set oneliner while someone using Java is coding it from scratch or resorting to a "hackpack".

by zwliew 6y ago

petethepig 6y ago

Thanks! We loved geeking out on all of these data structures and algorithms. RE comparisons: Do you mean comparisons of some production profiling data with versus without this compression?

ZephyrBlu 6y ago

How are segment trees used in competitive programming? I can't immediately see how they would be useful in that situation.

knuthsat 6y ago
Any dynamic programming algorithm where n-th item depends on contiguous k ones with some nice binary operation (like +) can benefit from storing the state in a segment tree, so when you go and calculate n-th item, you can get the value in log(n) instead of O(k) (although prefix sums work fine there too if + is involved). 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/ https://www.spoj.com/problems/QUE2/
- ZephyrBlu 6y 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.
  - knuthsat 6y ago
    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 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.
vladimirralev 6y ago
Competitive programming problems are often designed with intended solution technique in mind first so whatever the trendy thing to do is finds its way into the competitions. Segment trees used to be popular but less so now because it's unfair to some languages. Python and C++ competitors can often work around a segment tree with a sortedlist/ordered_set oneliner while someone using Java is coding it from scratch or resorting to a "hackpack".