Merge Sort Tree vs Persistent Segment Tree vs Wavelet Tree
Разница между en1 и en2, 0 символ(ов) изменены
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.↵
↵
<img src="https://i.postimg.cc/jwnp6hV2/1.png" width="900">↵
↵
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.↵
↵
<img src="https://i.postimg.cc/nsm8BkbN/2.png" width="900">↵
↵
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.↵
↵
<img src="https://i.postimg.cc/kVSrKcPr/3.png" width="900">↵
↵
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 &mdash; Destiny](https://codeforces.me/problemset/problem/840/D)↵
↵
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.↵
↵
[Official Editorial](https://codeforces.me/blog/entry/53943)↵
↵
## 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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский amirjr 2026-11-16 19:11:59 0 (published)
en1 Английский amirjr 2026-11-16 19:10:58 5223 Initial revision (saved to drafts)