wavelet_matrix

class WaveletMatrix:

A Wavelet Matrix data structure for efficient rank, select, and quantile queries.

The Wavelet Matrix decomposes a sequence into multiple bit vectors, one for each bit position. This allows for efficient queries on the sequence.
This class supports various integer types, automatically selecting the appropriate internal representation based on the input data.

WaveletMatrix(data: Iterable[int])

def values(self) -> list[int]:

Get all values in the Wavelet Matrix as a list.

Complexity

Time: O(N log V)

where:

N = length of the sequence
V = range of possible values (max value domain)

Exapmles

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.values()
[5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0]

def access(self, index: int) -> int:

Access the value at the specified index.

Complexity

Time: O(log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.access(3)
5

def rank(self, value: int, end: int) -> int:

Counts the occurrences of the given value in the range [0, end).

Complexity

Time: O(log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.rank(5, 9)
4

def select(self, value: int, kth: int) -> int | None:

Finds the position of the k-th occurrence of the given value.

Complexity

Time: O(log V) (amortized)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.select(5, 4)
6

def quantile(self, start: int, end: int, kth: int) -> int:

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

Complexity

Time: O(log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.quantile(2, 12, 8)
5

def topk(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Finds the top-k most frequent elements in the range [start, end).

Complexity

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

where:

L = the number of distinct values in the range [start, end)
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.topk(1, 10, 2)
[{'value': 5, 'count': 3}, {'value': 1, 'count': 2}]

def range_sum(self, start: int, end: int) -> int:

Computes the sum of values in the range [start, end).

Complexity

Time: O(L log V)

where:

L = the number of distinct values c in the range [start, end) that satisfy lower <= c < upper
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.range_sum(2, 8)
24

def range_intersection( self, start1: int, end1: int, start2: int, end2: int) -> list[dict[str, int]]:

Finds the intersection of values in the two ranges [start1, end1) and [start2, end2).

Complexity

Time: O(L log V)

where:

L = the number of distinct values c in the intersection of the two ranges
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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:

Counts the number of elements c in the range [start, end) such that lower <= c < upper.

Complexity

Time: O(log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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]]:

Lists all elements c in the range [start, end) such that lower <= c < upper.

Complexity

Time: O(L log V)

where:

L = the number of distinct values c in the range [start, end) that satisfy lower <= c < upper
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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]]:

Finds the k largest values in the range [start, end).

Complexity

Time: O(k log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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]]:

Finds the k smallest values in the range [start, end).

Complexity

Time: O(k log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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:

Finds the maximum value c in the range [start, end) such that c < upper.

Complexity

Time: O(log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.prev_value(1, 9, 7)
6

def next_value(self, start: int, end: int, lower: int | None = None) -> int | None:

Finds the minimum value c in the range [start, end) such that lower <= c.

Complexity

Time: O(log V)

where:

V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import WaveletMatrix
>>> wm = WaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> wm.next_value(1, 9, 3)
4

class DynamicWaveletMatrix:

A dynamic wavelet matrix supporting various integer types.

This class provides efficient storage and querying of sequences of integers, with support for dynamic updates such as insertions and deletions.
It can handle integers of varying bit widths, automatically selecting the appropriate internal representation based on the input data.

DynamicWaveletMatrix(data: Iterable[int], max_bit: int | None = None)

def values(self) -> list[int]:

Get all values in the Wavelet Matrix as a list.

Complexity

Time: O(N log V)

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.values()
[5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0]

def access(self, index: int) -> int:

Access the value at the specified index.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.access(3)
5

def rank(self, value: int, end: int) -> int:

Counts the occurrences of the given value in the range [0, end).

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.rank(5, 9)
4

def select(self, value: int, kth: int) -> int | None:

Finds the position of the k-th occurrence of the given value.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.select(5, 4)
6

def quantile(self, start: int, end: int, kth: int) -> int:

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

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.quantile(2, 12, 8)
5

def topk(self, start: int, end: int, k: int | None = None) -> list[dict[str, int]]:

Finds the top-k most frequent elements in the range [start, end).

Complexity

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

where:

L = the number of distinct values in the range [start, end)
N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.topk(1, 10, 2)
[{'value': 5, 'count': 3}, {'value': 1, 'count': 2}]

def range_sum(self, start: int, end: int) -> int:

Computes the sum of values in the range [start, end).

Complexity

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

where:

L = the number of distinct values c in the range [start, end)
N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.range_sum(2, 8)
24

def range_intersection( self, start1: int, end1: int, start2: int, end2: int) -> list[dict[str, int]]:

Finds the intersection of values in the two ranges [start1, end1) and [start2, end2).

Complexity

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

where:

L = the number of distinct values c in the intersection of the two ranges
N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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:

Counts the number of elements c in the range [start, end) such that lower <= c < upper.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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]]:

Lists all elements c in the range [start, end) such that lower <= c < upper.

Complexity

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

where:

L = the number of distinct values c in the range [start, end) that satisfy lower <= c < upper
N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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]]:

Finds the k largest values in the range [start, end).

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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]]:

Finds the k smallest values in the range [start, end).

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> 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:

Finds the maximum value c in the range [start, end) such that c < upper.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.prev_value(1, 9, 7)
6

def next_value(self, start: int, end: int, lower: int | None = None) -> int | None:

Finds the minimum value c in the range [start, end) such that lower <= c.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.next_value(1, 9, 3)
4

def max_bit(self) -> int:

Returns the maximum bit length of the values stored in the Wavelet Matrix.

Complexity

Time: O(1)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.max_bit()
3

def insert(self, index: int, value: int) -> None:

Inserts a value at the specified index.
The bit width of the new value must not exceed max_bit.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0], max_bit=4)
>>> dwm.insert(3, 10)
>>> dwm.values()
[5, 4, 5, 10, 5, 2, 1, 5, 6, 1, 3, 5, 0]

def remove(self, index: int) -> int:

Removes and returns the value at the specified index.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0])
>>> dwm.remove(3)
5
>>> dwm.values()
[5, 4, 5, 2, 1, 5, 6, 1, 3, 5, 0]

def update(self, index: int, value: int) -> int:

Updates the value at the specified index and returns the old value.
The bit width of the new value must not exceed max_bit.

Complexity

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

where:

N = length of the sequence
V = range of possible values (max value domain)

Examples

>>> from wavelet_matrix import DynamicWaveletMatrix
>>> dwm = DynamicWaveletMatrix([5, 4, 5, 5, 2, 1, 5, 6, 1, 3, 5, 0], max_bit=4)
>>> dwm.update(2, 10)
5
>>> dwm.values()
[5, 4, 10, 5, 2, 1, 5, 6, 1, 3, 5, 0]