Wavelet matrices: count frequencies and find subarray quantiles

Last updated: 5 Oct 20269 min read

tutorial

A wavelet matrix stores one bit sequence per value bit position, starting with the most significant bit. At each level it stably places all zero-bit values before one-bit values and records a prefix count of ones plus the number of zeros. A query translates a half-open position interval into its zero or one child interval at every level. Frequency follows the target's bits; kth chooses a zero branch when its count covers the requested zero-based rank, otherwise subtracts that count and follows ones. Unlike a pointer-based wavelet tree, each level is one global sequence. This example accepts nonnegative integers and retains unpacked Python prefix arrays rather than compressed bitvectors.

Operational case

A static alert-level stream is 47, 19, 83, 47, 29, 61, 19. The third smallest value in positions one through five is 47; value 47 appears twice in the first five positions. Both repeated 47s remain separate observations, so this is a sequence index, not a set. Frequency for a value outside the represented bit width is zero. An empty kth window is rejected because no rank can be valid. Replacing one alert level changes every later stable partition at some bit level, so the matrix must be rebuilt from a new snapshot.

Working Python program

class AlertWaveletMatrix:
    def __init__(self, alert_levels):
        if any(level < 0 for level in alert_levels):
            raise ValueError("alert levels must be nonnegative")
        self.length = len(alert_levels)
        self.width = max((level.bit_length() for level in alert_levels), default=1)
        self.width = max(1, self.width)
        self.prefix_ones = []
        self.zero_counts = []
        ordered = list(alert_levels)
        for shift in range(self.width - 1, -1, -1):
            zero_group, one_group = [], []
            prefix = [0]
            for level in ordered:
                bit = (level >> shift) & 1
                prefix.append(prefix[-1] + bit)
                (one_group if bit else zero_group).append(level)
            self.prefix_ones.append(prefix)
            self.zero_counts.append(len(zero_group))
            ordered = zero_group + one_group

    def _bounds(self, left, right):
        if not 0 <= left <= right <= self.length:
            raise IndexError("invalid half-open window")

    def frequency(self, level, left, right):
        self._bounds(left, right)
        if level < 0 or level >= (1 << self.width):
            return 0
        for depth, shift in enumerate(range(self.width - 1, -1, -1)):
            prefix = self.prefix_ones[depth]
            if (level >> shift) & 1:
                left = self.zero_counts[depth] + prefix[left]
                right = self.zero_counts[depth] + prefix[right]
            else:
                left -= prefix[left]
                right -= prefix[right]
        return right - left

    def kth(self, left, right, rank):
        self._bounds(left, right)
        if not 0 <= rank < right - left:
            raise IndexError("rank outside window")
        answer = 0
        for depth, shift in enumerate(range(self.width - 1, -1, -1)):
            prefix = self.prefix_ones[depth]
            left_zeros = left - prefix[left]
            right_zeros = right - prefix[right]
            zeros = right_zeros - left_zeros
            if rank < zeros:
                left, right = left_zeros, right_zeros
            else:
                rank -= zeros
                answer |= 1 << shift
                left = self.zero_counts[depth] + prefix[left]
                right = self.zero_counts[depth] + prefix[right]
        return answer


if __name__ == "__main__":
    matrix = AlertWaveletMatrix([47, 19, 83, 47, 29, 61, 19])
    print("third in [1,6):", matrix.kth(1, 6, 2))
    print("47 count in [0,5):", matrix.frequency(47, 0, 5))
    print("19 count in [2,7):", matrix.frequency(19, 2, 7))

Output

third in [1,6): 47
47 count in [0,5): 2
19 count in [2,7): 1

Time, space, and tradeoff

For N values and W bits in the largest value, construction takes O(NW) time and O(NW) integers in these prefix arrays. Frequency and kth each take O(W) time and O(1) query memory. A packed bitvector implementation can change practical memory use substantially; this Python teaching version does not claim succinct storage. The static wavelet tree elsewhere in this curriculum answers a related subarray order question with recursive nodes. This matrix emphasizes the levelwise layout and direct bit routing, which is useful when the alphabet is fixed and reads dominate updates.

Common Mistakes

Do not collapse duplicate values during construction.
Do not pass an inclusive right endpoint to a half-open query.
Do not use a rank outside the selected window.
Do not describe Python prefix lists as compressed bitvectors.

Connected lessons

Compare its update and query contract with Palindromic trees: index distinct palindromes as text arrives, Segment tree beats: cap a range while retaining its sum, Two-stack window aggregation: keep FIFO order under a monoid, then complete the structure audit and decision quiz.

FM-index backward search: narrow a suffix interval by character adds a distinct structure contract to compare.

Range-majority indexes: verify a candidate before returning it adds a related structure with a different operation boundary.

Persistent range MEX: search last occurrences in prefix versions examines a related structure with a different operation boundary.

data structures

range-query-structures