[knuthsat]

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/

[ZephyrBlu]

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]

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.