Wavelet Tree
Recursively partition values so k-th order statistics and frequency queries on subarrays can be answered quickly.
Wavelet Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Wavelet tree is a static range-query structure for arrays when the queries care about values inside a subarray: how many numbers are \(\le x\), what is the \(k\)-th smallest, how many times does a value occur, and similar questions.
When to Use It
Use it when:
the array is static or mostly static,
queries are on subarrays,
the answer depends on the multiset of values inside that subarray, not just on a sum or minimum.
Core Idea
The tree recursively splits the value range \([lo, hi]\) by its midpoint. At each node, it stores a prefix-count array telling how many elements of the current subsequence went to the left child.
That one prefix array is enough to map a subarray \([l, r]\) in the parent node into the corresponding subarray inside either child.
Key Insight
The structure does not partition by indices; it partitions by value ranges while preserving relative order inside each node. That is why it can answer order-statistics questions without sorting every queried subarray.
Worked Problem
Problem.
Given a static array, answer queries of the form:
\(k\)-th smallest value in \([l, r]\),
count of values \(\le x\) in \([l, r]\).
Why a wavelet tree fits.
At each level, the query only needs to know how many of the range elements went left. That tells you whether the answer stays in the left value half or the right value half.
Correctness Intuition
Every node stores exactly the subsequence of values whose numeric range belongs to that node. The prefix counts map query indices from parent order into child order, so recursion always follows the correct subset of positions.
Complexity Analysis
For value range size \(\sigma\):
build: \(O(n \log \sigma)\),
\(k\)-th smallest: \(O(\log \sigma)\),
count \(\le x\): \(O(\log \sigma)\),
memory: \(O(n \log \sigma)\).
Implementation
The reference code supports:
kth(l, r, k),lte(l, r, x).The array is assumed to be 1-indexed for query arguments in the usual wavelet-tree style.
Common Pitfalls
Mixing 0-indexed array storage with 1-indexed query formulas.
Forgetting that the structure is static; arbitrary updates are not cheap.
Building over a huge raw value domain instead of compressing when appropriate.
Variants / Extensions
Frequency of one exact value.
Range sum over values in a numeric interval with extra prefix data.
Wavelet matrix, which stores the same idea in a flatter layout.
Practice Problems
K-th smallest on subarrays.
Count values below a threshold on subarrays.
Static range median or quantile queries.
References
Code
Contest-ready reference implementation for the idea explained above.
struct WaveletTree {
int lo;
int hi;
WaveletTree* left;
WaveletTree* right;
vector<int> pref;
WaveletTree(vector<int>::iterator from, vector<int>::iterator to, int x, int y)
: lo(x), hi(y), left(nullptr), right(nullptr) {
if (from >= to || lo == hi) return;
int mid = (lo + hi) / 2;
auto goes_left = [mid](int value) { return value <= mid; };
pref.reserve((to - from) + 1);
pref.push_back(0);
for (auto it = from; it != to; ++it) {
pref.push_back(pref.back() + goes_left(*it));
}
auto pivot = stable_partition(from, to, goes_left);
if (from < pivot) left = new WaveletTree(from, pivot, lo, mid);
if (pivot < to) right = new WaveletTree(pivot, to, mid + 1, hi);
}
int kth(int l, int r, int k) const {
if (l > r) return -1;
if (lo == hi) return lo;
int in_left = pref[r] - pref[l - 1];
if (k <= in_left) {
return left->kth(pref[l - 1] + 1, pref[r], k);
}
return right->kth(l - pref[l - 1], r - pref[r], k - in_left);
}
int lte(int l, int r, int x) const {
if (l > r || x < lo) return 0;
if (hi <= x) return r - l + 1;
int left_count = left ? left->lte(pref[l - 1] + 1, pref[r], x) : 0;
int right_count = right ? right->lte(l - pref[l - 1], r - pref[r], x) : 0;
return left_count + right_count;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.