wavelet_matrix

class WaveletMatrix:

A Wavelet Matrix for fast queries on a static sequence of integers.

Wavelet Matrix decomposes values into bit layers and supports queries such as:

  • access(i): read value at position i
  • rank(v, end): count v in a prefix
  • select(v, kth): find position of k-th v
  • quantile(l, r, kth): k-th smallest in a range
  • rich range queries: topk, range_sum, range_freq, range_list, ...

This class automatically chooses an internal representation based on input values.

Construction

Time / Space Complexity

  • Time: O(N log V)
  • Space: O(N log V)

where:

  • N = length of the sequence
  • V = value domain / range (roughly related to max bit-width)
from wavelet_matrix import WaveletMatrix
wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
WaveletMatrix(data: Iterable[int])
def values(self) -> list[int]:

Return the entire sequence as a Python list.

Complexity

  • Time: O(N log V)
  • Space: O(N)

Examples

wm.values()
# [5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0]
def access(self, index: int) -> int:

Return data[index].

Complexity

  • Time: O(log V)
  • Space: O(1)

Examples

wm.access(3)
# 5
def rank(self, value: int, end: int) -> int:

Count occurrences of value in the prefix range [0, end).

Complexity

  • Time: O(log V)
  • Space: O(1)

Examples

wm.rank(5, 9)
# 4
def select(self, value: int, kth: int) -> int | None:

Return the index of the kth occurrence of value (1-indexed).
Returns None if it does not exist.

Complexity

  • Time: O(log V) (amortized)
  • Space: O(1)

Examples

wm.select(5, 4)
# 6
def quantile(self, start: int, end: int, kth: int) -> int:

Return the k-th smallest value in [start, end) (1-indexed).

Complexity

  • Time: O(log V)
  • Space: O(1)

Examples

wm.quantile(2, 12, 8)
# 5
def topk(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Return the most frequent values in [start, end).
Result items look like {"value": x, "count": c}.

Complexity

  • Time: O(L (log L) (log V))
  • Space: O(L)
  • L = number of distinct values in the range

Examples

wm.topk(1, 10, 2)
# [{'value': 5, 'count': 3}, {'value': 1, 'count': 2}]
def range_sum(self, start: int, end: int) -> int:

Sum of values in [start, end).

Complexity

  • Time: O(L log V)
  • Space: O(L)

Examples

wm.range_sum(2, 8)
# 24
def range_intersection( self, start1: int, end1: int, start2: int, end2: int) -> list[dict[str, int]]:

Intersection of values between two ranges.
Each item: {"value": x, "count1": a, "count2": b}.

Complexity

  • Time: O(L log V)
  • Space: O(L)

Examples

wm.range_intersection(0, 6, 6, 11)
# [{'value': 1, 'count1': 1, 'count2': 1}, {'value': 5, 'count1': 3, 'count2': 2}]
def range_freq( self, start: int, end: int, lower: int | None = None, upper: int | None = None) -> int:

Count elements c in [start, end) such that lower <= c < upper.

Complexity

  • Time: O(log V)
  • Space: O(1)

Examples

wm.range_freq(1, 9, 4, 6)
# 4
def range_list( self, start: int, end: int, lower: int | None = None, upper: int | None = None) -> list[dict[str, int]]:

List distinct values c in [start, end) satisfying lower <= c < upper, with counts.

Complexity

  • Time: O(L log V)
  • Space: O(L)

Examples

wm.range_list(1, 9, 4, 6)
# [{'value': 4, 'count': 1}, {'value': 5, 'count': 3}]
def range_maxk(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Return the k largest values in [start, end) with counts.

Complexity

  • Time: O(k log V)
  • Space: O(k)

Examples

wm.range_maxk(1, 9, 2)
# [{'value': 6, 'count': 1}, {'value': 5, 'count': 3}]
def range_mink(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Return the k smallest values in [start, end) with counts.

Complexity

  • Time: O(k log V)
  • Space: O(k)

Examples

wm.range_mink(1, 9, 2)
# [{'value': 1, 'count': 2}, {'value': 2, 'count': 1}]
def prev_value(self, start: int, end: int, upper: int | None = None) -> int | None:

Return the maximum value c in [start, end) such that c < upper.
Returns None if no value matches.

Complexity

  • Time: O(log V)
  • Space: O(1)

Examples

wm.prev_value(1, 9, 7)
# 6
def next_value(self, start: int, end: int, lower: int | None = None) -> int | None:

Return the minimum value c in [start, end) such that lower <= c.
Returns None if no value matches.

Complexity

  • Time: O(log V)
  • Space: O(1)

Examples

wm.next_value(1, 9, 3)
4
def max_bit(self) -> int:

Return the maximum bit-length of elements.

Complexity

  • Time: O(1)
  • Space: O(1)

Examples

wm.max_bit()
# 4
class DynamicWaveletMatrix:

A dynamic wavelet matrix supporting insert/remove/update.

Use this when you need to mutate the sequence.
⚠️ Values must fit within max_bit (bit-width constraint).

Construction

Time / Space Complexity

  • Time: O(N log V)
  • Space: O(N log V)
from wavelet_matrix import DynamicWaveletMatrix
dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0], max_bit=4)
DynamicWaveletMatrix(data: Iterable[int], max_bit: int | None = None)
def values(self) -> list[int]:

Return the entire sequence as a Python list.

Complexity

  • Time: O(N log V)
  • Space: O(N)

Examples

dwm.values()
# [5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0]
def access(self, index: int) -> int:

Return data[index].

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.access(3)
# 5
def rank(self, value: int, end: int) -> int:

Count occurrences of value in the prefix range [0, end).

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.rank(5, 9)
# 4
def select(self, value: int, kth: int) -> int | None:

Return the index of the kth occurrence of value (1-indexed).
Returns None if it does not exist.

Complexity

  • Time: O((log N) (log V)) (amortized)
  • Space: O(1)

Examples

dwm.select(5, 4)
# 6
def quantile(self, start: int, end: int, kth: int) -> int:

Return the k-th smallest value in [start, end) (1-indexed).

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.quantile(2, 12, 8)
# 5
def topk(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Return the most frequent values in [start, end).
Result items look like {"value": x, "count": c}.

Complexity

  • Time: O(L (log L) (log N) (log V))
  • Space: O(L)
  • L = number of distinct values in the range

Examples

dwm.topk(1, 10, 2)
# [{'value': 5, 'count': 3}, {'value': 1, 'count': 2}]
def range_sum(self, start: int, end: int) -> int:

Sum of values in [start, end).

Complexity

  • Time: O(L (log N) (log V))
  • Space: O(L)

Examples

dwm.range_sum(2, 8)
# 24
def range_intersection( self, start1: int, end1: int, start2: int, end2: int) -> list[dict[str, int]]:

Intersection of values between two ranges.
Each item: {"value": x, "count1": a, "count2": b}.

Complexity

  • Time: O(L (log N) (log V))
  • Space: O(L)

Examples

dwm.range_intersection(0, 6, 6, 11)
# [{'value': 1, 'count1': 1, 'count2': 1}, {'value': 5, 'count1': 3, 'count2': 2}]
def range_freq( self, start: int, end: int, lower: int | None = None, upper: int | None = None) -> int:

Count elements c in [start, end) such that lower <= c < upper.

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.range_freq(1, 9, 4, 6)
# 4
def range_list( self, start: int, end: int, lower: int | None = None, upper: int | None = None) -> list[dict[str, int]]:

List distinct values c in [start, end) satisfying lower <= c < upper, with counts.

Complexity

  • Time: O(L (log N) (log V))
  • Space: O(L)

Examples

dwm.range_list(1, 9, 4, 6)
# [{'value': 4, 'count': 1}, {'value': 5, 'count': 3}]
def range_maxk(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Return the k largest values in [start, end) with counts.

Complexity

  • Time: O(k (log N) (log V))
  • Space: O(k)

Examples

dwm.range_maxk(1, 9, 2)
# [{'value': 6, 'count': 1}, {'value': 5, 'count': 3}]
def range_mink(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Return the k smallest values in [start, end) with counts.

Complexity

  • Time: O(k (log N) (log V))
  • Space: O(k)

Examples

dwm.range_mink(1, 9, 2)
# [{'value': 1, 'count': 2}, {'value': 2, 'count': 1}]
def prev_value(self, start: int, end: int, upper: int | None = None) -> int | None:

Return the maximum value c in [start, end) such that c < upper.
Returns None if no value matches.

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.prev_value(1, 9, 7)
# 6
def next_value(self, start: int, end: int, lower: int | None = None) -> int | None:

Return the minimum value c in [start, end) such that lower <= c.
Returns None if no value matches.

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.next_value(1, 9, 3)
4
def max_bit(self) -> int:

Return the maximum bit-length allowed for stored values.

Complexity

  • Time: O(1)
  • Space: O(1)

Examples

dwm.max_bit()
# 4
def insert(self, index: int, value: int) -> None:

Insert value at index.
⚠️ value must fit within max_bit.

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.insert(3, 10)
def remove(self, index: int) -> int:

Remove and return the value at index.

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.remove(3)
def update(self, index: int, value: int) -> int:

Replace data[index] with value and return the old value.
⚠️ value must fit within max_bit.

Complexity

  • Time: O((log N) (log V))
  • Space: O(1)

Examples

dwm.update(2, 10)
# returns old value