These three data structures may look quite different, but they can all solve the same range query problems.
Let's compare their ideas using a simple problem.
1. The Problem
Given an array, find the k-th smallest element in a subarray [l, r].
For example:
a = [5, 1, 4, 2, 3]
For l = 2, r = 5, k = 2, the subarray is:
[1, 4, 2, 3]
After sorting, the answer is 2.
We can solve this by answering a simpler query:
count(l, r, x)
The number of elements in [l, r] that are less than or equal to x.
The k-th smallest element is the smallest x satisfying:
count(l, r, x) >= k
2. Merge Sort Tree
A Merge Sort Tree divides the array by positions.
Each node stores a sorted vector of its corresponding segment.
For example, consider an array of length 8:
[5, 1, 4, 2, 3, 7, 6, 8]
Each node stores the sorted elements of its interval.

To answer count(l, r, x), decompose the query into O(log n) nodes and use upper_bound in each vector.
Complexities:
- Build: O(n log n)
- Count: O(log² n)
- K-th smallest: O(log σ × log² n)
Idea: Divide by positions and keep values sorted.
3. Persistent Segment Tree
Instead of dividing by positions, we build a frequency segment tree over the value domain.
root[i] represents the frequency distribution of the first i elements.
We create each version by inserting the next element, copying only the nodes on the update path.

The key observation is:
root[r] - root[l-1]
represents the frequency distribution of the requested subarray.
To find the k-th smallest, calculate the frequency in the left child of both roots. Depending on that count, move left or right.
Complexities:
- Build: O(n log σ)
- Query: O(log σ)
- Memory: O(n log σ) nodes
Idea: Subtract two prefix versions to obtain a range's frequency distribution.
4. Wavelet Tree
A Wavelet Tree also divides by values, but uses bitvectors instead of persistent segment tree nodes.
At each level, elements are partitioned into two groups according to their values.
For our example:
[5, 1, 4, 2, 3]
The root bitvector is:
01011
Here, 1 means left and 0 means right.

We use rank to count how many elements go to each child and map the query interval into that child.
For K-th smallest queries, we simply follow the child containing the k-th element.
Complexities:
- Build: O(n log σ)
- Query: O(log σ)
- Memory: O(n log σ) words with a straightforward implementation.
Idea: Divide by values and use rank operations to navigate the sequence.
5. Comparison
| Property | Merge Sort Tree | Persistent ST | Wavelet Tree |
|---|---|---|---|
| Division | Position | Value | Value |
| Technique | Sorted vectors | Prefix versions | Rank |
| Count | O(log² n) | O(log σ) | O(log σ) |
| K-th smallest | O(log σ log² n) | O(log σ) | O(log σ) |
There is no universal winner. The best choice depends on the required operations, memory limits, and implementation complexity.
6. Application: 840D — Destiny
Given a query (l, r, k), find the smallest value that occurs more than (r-l+1)/k times.
An important constraint is:
2 <= k <= 5
Let's look at three approaches.
Persistent Segment Tree
Use two prefix versions and traverse the value domain.
If a node's frequency is smaller than the required frequency, discard it. Otherwise, explore its children, visiting the left child first.
At each level, at most k-1 nodes can remain, giving:
O(k log n) per query.
Wavelet Tree
Apply the same pruning idea, but use rank to calculate the frequencies in each child.
The query complexity is also:
O(k log n).
Divide and Conquer
This is the approach used in the official editorial.
Divide the array by positions and precompute the k most frequent values for intervals touching each midpoint.
For a query crossing the midpoint, check the candidates from both halves.
A value occurring more than length/k times must appear among these candidates.
Using occurrence lists and binary search, we can verify them efficiently.
- Preprocessing: O(kn log n)
- Query: O(k log n)
The interesting observation: A small constraint such as k <= 5 can completely change the way we approach a problem.
7. Final Thoughts
We saw three ways to organize the same information:
- Merge Sort Tree: Divide by positions.
- Persistent Segment Tree: Subtract prefix histories.
- Wavelet Tree: Divide by values using rank.
Sometimes, the most interesting part of solving a problem isn't the query itself, but finding the right way to represent the data.
Not gonna lie, I'm just trying to gain some followers. Have mercy and spare me the downvotes! :D
Happy coding!




