Skip to content
Tutorials Center
My learning

Topics

Lesson 119 of 225 ยท Tries and Range Queries

Merge Sort Tree and Wavelet Trees

Answer 'how many values are below x' and 'what is the k-th smallest' in any array range using a merge sort tree and a wavelet tree, with Python code and diagrams.

Segment trees and sparse tables answer questions like "what is the sum or minimum of this range?". But some questions depend on the order of the values inside a range: "how many elements in a[l..r] are smaller than 50?" or "what is the 3rd smallest value in a[l..r]?". A single number per node cannot answer those, because you cannot combine two ranges' medians into the median of the union.

Two structures solve this for a static array. A merge sort tree stores a sorted list at every node and answers in O(logยฒ n). A wavelet tree splits by value instead of by position and answers the k-th smallest in O(log ฯƒ), where ฯƒ is the number of distinct values. Both have simple Python implementations.

The merge sort tree

Build a segment tree over positions, but let each node keep the sorted list of the values in its range. A parent's sorted list is made by merging its two children's lists, exactly like one step of merge sort, which is where the name comes from.

flowchart TD
    R["[0..7]<br/>1 2 3 4 5 6 8 9"] --> L["[0..3]<br/>2 4 5 8"]
    R --> Rt["[4..7]<br/>1 3 6 9"]
    L --> LL["[0..1]<br/>2 8"]
    L --> LR["[2..3]<br/>4 5"]
    Rt --> RL["[4..5]<br/>3 9"]
    Rt --> RR["[6..7]<br/>1 6"]

A merge sort tree over the array 8, 2, 5, 4, 3, 9, 1, 6 (leaves omitted). Each node shows its values in sorted order.

Every level stores n values in total, and there are about log n levels, so memory and build time are O(n log n).

Counting values below x in a range

To count elements < x in a[l..r], descend like a normal segment tree query. The range splits into O(log n) nodes that exactly tile it. In each node, the sorted list lets us use binary search (bisect_left) to count values below x in O(log n). The total is O(logยฒ n).

Python Merge sort tree: count values below x in a range

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

k-th smallest with a merge sort tree

Counting is a monotone function of the threshold: the bigger x is, the more values are below it. So the k-th smallest in a range is the smallest value v for which count_less(l, r, v + 1) >= k. Use binary search on the answer over the sorted distinct values. That adds another log factor: O(logยณ n) per query. It works, but it is slow, and that is what the wavelet tree improves.

The wavelet tree

The wavelet tree splits by value rather than by position. Take the smallest and largest value of the array, compute the midpoint, and send every element <= mid to the left child and every element > mid to the right child, keeping their original relative order. Recurse until a node holds a single distinct value.

At each node, remember for every prefix how many elements went left. With that table, any position range [l, r) in the parent maps to a range in the left child or the right child in O(1):

  • Elements that went left in this range: left_count[r] - left_count[l].
  • In the left child, the range becomes [left_count[l], left_count[r]).
  • In the right child, it becomes [l - left_count[l], r - left_count[r]).
flowchart TD
    A["values 1..9<br/>8 2 5 4 3 9 1 6"] -->|"<= 5"| B["values 1..5<br/>2 5 4 3 1"]
    A -->|"> 5"| C["values 6..9<br/>8 9 6"]
    B -->|"<= 3"| D["values 1..3<br/>2 3 1"]
    B -->|"> 3"| E["values 4..5<br/>5 4"]
    C -->|"<= 7"| F["values 6..7<br/>6"]
    C -->|"> 7"| G["values 8..9<br/>8 9"]

The first levels of a wavelet tree. Each split keeps the original order of the elements it passes down.

k-th smallest in O(log ฯƒ)

To find the k-th smallest (1-based) in positions [l, r): at each node, count how many elements of the range went left. If k is at most that count, the answer is in the left child; otherwise subtract it from k and go right. When the value range collapses to one number, that is the answer.

Python Wavelet tree: k-th smallest and range counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop runs once per level of the value range, so a query is O(log ฯƒ), independent of the range length. With 10โถ distinct values that is only about 20 steps.

Comparing the options

Structure Build Count below x k-th smallest Memory Updates
Scan the range and sort none O(n log n) O(n log n) O(n) trivial
Merge sort tree O(n log n) O(logยฒ n) O(logยณ n) O(n log n) rebuild
Wavelet tree O(n log ฯƒ) O(log ฯƒ) O(log ฯƒ) O(n log ฯƒ) rebuild

The merge sort tree is easier to write and extends to other queries (for instance, the nearest value above x in a range). The wavelet tree is faster and leaner for k-th smallest and rank queries. Neither supports changing elements cheaply; for that, look at a Fenwick tree of ordered sets or square root decomposition.

Common mistakes

  • Mixing inclusive and half-open ranges. The merge sort tree above uses [l, r]; the wavelet tree uses [l, r). Pick one convention and convert at the boundary.
  • Using the structure with updates. Changing one element changes sorted lists in O(log n) nodes, each of size up to n. These structures are for static data.
  • Forgetting to keep order when splitting. A wavelet node must keep the original order of the elements passed down, or position ranges stop mapping correctly.
  • Asking for k out of range. The k-th smallest only exists for 1 <= k <= r - l.
  • Recursion depth. In Python a recursive build is fine for 10โต elements; for much larger inputs build bottom-up iteratively.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does each node of a merge sort tree store?

    Sorted lists allow binary search inside every node that tiles a query range.
  2. 2. How long does a count-less-than-x query take on a merge sort tree?

    The range splits into O(log n) nodes and each needs an O(log n) binary search.
  3. 3. How does a wavelet tree decide which child an element goes to?

    Values at or below the midpoint go left and larger ones go right, with their relative order preserved.
  4. 4. At a wavelet node, 3 elements of the query range went left and k = 5. What happens?

    Only 3 elements are smaller, so the 5th smallest is the 2nd smallest among the elements that went right.
  5. 5. What is the cost of a k-th smallest query in a wavelet tree?

    The query walks down one root-to-leaf path, one step per level of the value range.

Summary

  • Order-based range queries (rank, count below x, k-th smallest) need more than one number per node.
  • A merge sort tree stores a sorted list per segment tree node: O(n log n) memory, O(logยฒ n) counting by binary search.
  • The k-th smallest with a merge sort tree needs a binary search on the answer on top, giving O(logยณ n).
  • A wavelet tree splits by value, keeps order, and maps position ranges down with prefix counts: O(log ฯƒ) for k-th smallest and rank.
  • Both structures are static; with updates, use sqrt decomposition or ordered-set tricks.

Next: Graphs