eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn Wavelet Matrices: Bitvector Rank, Range Quantiles, Frequency Queries and Succinct Sequence Indexing

Quick Read. A wavelet matrix is a static sequence index that repeatedly partitions values by their bits while preserving enough positional information to answer access, rank, frequency and order-statistics queries quickly. The beginner should first learn how one bitvector can split values into zeros and ones. The intermediate learner should trace positions through several levels using rank. The advanced learner should derive range-frequency and k-th-smallest queries. The professional should understand bitvector engineering, coordinate compression, signed values, large alphabets, cache behaviour, construction cost and the relationship to compressed text indexes.

One-sentence answer

A wavelet matrix stores a sequence as a stack of stable bit partitions, then uses rank operations on those bitvectors to translate a query range from one level to the next until the desired value or order statistic is determined.

Why this data structure exists

Suppose you have an array containing millions of integers and repeatedly need questions such as: “How many values between positions 200,000 and 500,000 are below 17?”, “What is the median in this subarray?”, “How many times does 42 occur before position i?”, or “What is the fifth-smallest value in this interval?” A sorted copy of the whole array loses positional information. A prefix-frequency table becomes too large when the value alphabet is large. A segment tree can answer some of these questions but often with much more memory or more complicated nested structures.

The wavelet family solves a different problem: keep the original sequence order available while recursively organising values. Wavelet trees introduced this idea as a compressed sequence representation. The wavelet matrix later reorganised the same logical information into levelwise bitvectors that are often simpler and faster for large alphabets.

Level 1 — Beginner: learn one stable bit partition

Start with values that fit in three bits:

sequence:  5  1  6  3  2  7  4  0
binary:  101 001 110 011 010 111 100 000

Look only at the most significant bit. Record a 1 for values whose first bit is 1 and a 0 for the rest. Then stably place all zero-bit values before all one-bit values. “Stable” means values within each group keep their relative order.

top bitvector: 1 0 1 0 0 1 1 0
zero group:    1 3 2 0
one group:     5 6 7 4
next order:    1 3 2 0 5 6 7 4

The bitvector remembers which side each original position entered. A single number, the count of zeros at that level, tells us where the one-group begins. Repeat the operation for the next bit and then the next. The final representation is a small stack of bitvectors plus one zero-count per level.

The key skill: rank

For a bitvector B, rank0(i) means the number of zero bits in the prefix B[0..i), and rank1(i) means the number of ones. Rank lets us translate a position from one level into the compacted zero or one region at the next level.

if bit == 0:
    next_position = rank0(position)
else:
    next_position = zero_count + rank1(position)

This position translation is the heart of the wavelet matrix. Learn it before learning any fancy query.

Level 2 — Intermediate: access and rank

Access: recover the value at position i

Begin at the top level with position i. Read the bit stored there. That bit becomes the next bit of the answer. Use rank to map i into the appropriate partition at the next level. Repeat until every bit has been recovered.

If the value universe needs w bits, access takes O(w) rank steps. When values are machine integers, w is often a small fixed constant such as 32 or 64; when values have been coordinate-compressed to σ distinct values, w is about ceil(log2 σ).

Rank of a value

To count how many copies of x occur before position i, follow the bits of x down the matrix. At each level translate the prefix boundary i through the zero or one partition. The size of the final interval is the number of copies.

A powerful mental model is that the query carries an interval rather than an individual position. A prefix [0,i) becomes a new prefix at each level. For range queries, carry [l,r) instead.

Range frequency: count values below x

Now ask: how many values in A[l..r) are less than x? Walk from the most significant bit downward. If the current bit of x is 0, only the zero partition can contain values smaller than x at later bits, so map the interval into the zero side. If the current bit of x is 1, every value in the zero side is already smaller than x; add that zero count to the answer, then continue through the one side.

count_less(l, r, x):
    answer = 0
    for each bit from high to low:
        zl = rank0(l)
        zr = rank0(r)
        zeros_in_range = zr - zl

        if bit_of(x) == 0:
            l, r = zl, zr
        else:
            answer += zeros_in_range
            l = zero_count + rank1(l)
            r = zero_count + rank1(r)
    return answer

From this primitive, a value-range count follows immediately:

count values in [low, high) = count_less(high) - count_less(low)

Range quantile: find the k-th smallest

The k-th-smallest query turns the same machinery around. At a level, count how many elements of the current [l,r) interval have bit 0. If k lies within that zero count, the answer’s current bit is 0 and the query descends into the zero partition. Otherwise the answer’s bit is 1, subtract the zero count from k and descend into the one partition.

This is essentially binary decision-making over the value bits, but unlike binary search it never sorts the queried subarray. The ordering information was prepared once during construction.

Level 3 — Advanced: what is actually stored?

  • One bitvector per level. Each bitvector records the current value bit for every sequence element in the order produced by the previous level.
  • A rank structure for each bitvector. Simple implementations use prefix counts per machine-word block; succinct implementations use multi-level directories so rank is effectively constant time with low overhead.
  • The zero boundary per level. This is the number of zeros and therefore the starting offset of the one partition.
  • Optional auxiliary structures. Select support, range sums, compressed bitvectors or per-level prefix aggregates can extend the query set.

The logical complexity is O(log σ) levels for a compressed alphabet. The engineering complexity is mostly in the bitvectors: memory layout, popcount throughput, branch avoidance and cache locality determine much of the real performance.

Wavelet tree versus wavelet matrix

A classical balanced wavelet tree recursively stores separate nodes for value ranges. A wavelet matrix flattens each depth into one level and changes how the partitions are arranged. The same high-level operations survive, but the matrix often avoids pointer-heavy tree navigation and handles large alphabets cleanly. Francisco Claude, Gonzalo Navarro and Alberto Ordóñez introduced the wavelet matrix specifically as an efficient wavelet-tree alternative for large alphabets.

Do not learn them as unrelated structures. Learn the wavelet tree idea first — recursively partition values while tracking positions — then see the wavelet matrix as a layout transformation that preserves the query logic.

Correctness: what should you prove?

  • Stable partitioning preserves the relative order of elements within the zero group and within the one group.
  • rank0 and rank1 therefore map any original prefix exactly to the corresponding prefix inside its next-level partition.
  • Applying this mapping to both l and r maps the whole interval [l,r) without losing or inventing elements.
  • Following the bits of one value isolates exactly the occurrences of that value.
  • For count-less-than, whenever x has a 1 bit, all zero-branch values at that first differing bit are strictly smaller and may be counted immediately.
  • For quantile, the zero count tells whether the desired order statistic belongs to the lower or upper value half.

Professional engineering

  • Coordinate compression: map sparse values to dense ranks when preserving numerical gaps is unnecessary. Keep the reverse map if original values must be returned.
  • Signed integers: define a consistent unsigned ordering transformation, such as flipping the sign bit, before bitwise partitioning.
  • Bit width: do not blindly use 64 levels when only 17 are needed; unnecessary levels cost memory and time.
  • Rank implementation: benchmark broadword popcount and block directories rather than assuming one representation is universally best.
  • Select: select is harder to engineer efficiently than rank. Add it only if the application needs it.
  • Compression: compressed bitvectors can reduce memory for skewed data, but decompression and rank support change the space–time trade-off.
  • Parallel construction: construction can be parallelised levelwise or with more sophisticated bottom-up methods; practical wavelet-tree research continues to optimise this stage.
  • Static assumption: the classic wavelet matrix is fundamentally a static index. Dynamic updates require substantially different machinery and should not be casually bolted on.

Testing ladder

  • Build a three-bit example by hand and verify every level’s stable partition.
  • For random arrays of length under 30, compare access against the original array.
  • Compare rank and range-frequency queries against direct counting.
  • Compare every k-th-smallest query against sorting the requested subarray.
  • Stress repeated values, all-equal arrays, strictly increasing arrays, maximum values and empty ranges.
  • Test signed values separately if the implementation supports them.
  • Measure construction time, bytes per element and query latency independently.

Common misconceptions

  • “The sequence is globally sorted.” No. Each level is only stably partitioned by one bit.
  • “Rank means the numerical rank of a value.” Here rank is a bitvector prefix-count operation.
  • “A wavelet matrix is only for strings.” It can index integer sequences and support range analytics as naturally as text operations.
  • “Quantile queries require a sorted subarray.” The matrix uses precomputed bit partitions to recover order statistics without sorting each query range.
  • “O(log σ) tells the whole performance story.” Rank representation, bit width, memory bandwidth and cache layout strongly affect real systems.

A learning route from beginner to professional

  • Beginner: manually stable-partition eight small integers by one bit and compute rank0/rank1 tables.
  • Intermediate: implement access and rank for a fixed 8-bit universe.
  • Advanced: add count-less-than, range-frequency and k-th-smallest queries, proving each interval mapping.
  • Algorithm engineer: replace full prefix arrays with block-based rank directories and benchmark memory versus latency.
  • Professional: compare wavelet trees, wavelet matrices and application-specific indexes on real distributions; measure construction, query throughput, working-set size and branch/cache behaviour.

For teaching, prediction should come before implementation. Give learners a bitvector and ask them to predict where an interval maps after stable partitioning, then run the code and explain any mismatch. This follows the same logic supported by programming-education research on worked examples, code tracing and scaffolded progression from reading existing code to modifying and creating it.

Authoritative sources and further reading

Closing idea. The wavelet matrix is worth learning because it turns a deceptively simple operation — stable partition by one bit — into a compact query language for large static sequences. Once you understand how intervals move through the bitvectors, rank, frequency and quantile queries stop looking like separate tricks and become variations of the same invariant.