Sorted lists at every node
A merge sort tree is a segment tree where each node stores a sorted copy of the elements in its range. The name comes from the build: it works exactly like the merge step of merge sort, since a parent's sorted list is the merge of its two children's sorted lists.
What it answers
This structure shines on queries like: how many elements in a subarray are less than or equal to a given value, or what is the kth smallest in a range. To count elements below a threshold in a range, descend the tree, and at each fully covered node run a binary search on its sorted list to count qualifying elements, then add the counts.
Costs
- Build: each level holds all the elements once, and there are logarithmically many levels, so the space is the array size times the number of levels.
- Query: you visit a logarithmic number of covering nodes, and each does a binary search, giving a query cost of a logarithm squared.
The structure is static, so it suits offline problems where the array does not change.
Key idea
Storing a sorted list at each segment tree node lets a range count or kth smallest query reduce to a handful of binary searches over covering nodes.