Sparse table in Python
Precomputed table of power-of-two range aggregates giving O(1) queries for idempotent operations.
- File
sparse_table.py, 67 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/sparse-table/. The authors are listed in prov/VSD7FB.jsonl.
from collections.abc import Callable, Sequence
from typing import Generic, TypeVar
T = TypeVar("T")
class SparseTable(Generic[T]):
"""A static sparse table: st[k][i] = A[i] op ... op A[i + 2^k - 1].
Building takes O(n log n) time and space. query(l, r) takes O(1) time and
needs op to be associative and idempotent (op(x, x) == x), as min, max,
gcd, bitwise and and bitwise or are. query_any(l, r) needs only an
associative op and takes O(log n) time. op need not be commutative.
"""
def __init__(self, values: Sequence[T], op: Callable[[T, T], T]) -> None:
n = len(values)
self.n = n
self.op = op
lg = [0] * (n + 1)
for i in range(2, n + 1): # @line L1
lg[i] = lg[i // 2] + 1
self.lg = lg
self.st: list[list[T]] = [list(values)] # @line L2
for k in range(1, lg[n] + 1 if n else 0): # @line L3
prev = self.st[k - 1]
half = 1 << (k - 1)
row = [op(prev[i], prev[i + half]) for i in range(n - (1 << k) + 1)] # @line L4 @line L5
self.st.append(row)
def __len__(self) -> int:
return self.n
def _check(self, l: int, r: int) -> None:
if not 0 <= l <= r < self.n:
raise IndexError("bad range")
def query(self, l: int, r: int) -> T:
"""Return A[l] op ... op A[r] for an idempotent op. O(1) time."""
self._check(l, r)
k = self.lg[r - l + 1] # @line L6
return self.op(self.st[k][l], self.st[k][r - (1 << k) + 1]) # @line L7
def query_any(self, l: int, r: int) -> T:
"""Return A[l] op ... op A[r] for any associative op. O(log n) time."""
self._check(l, r)
res: T | None = None # @line L8
for k in range(self.lg[self.n], -1, -1): # @line L9
if l + (1 << k) - 1 <= r: # @line L10
part = self.st[k][l]
res = part if res is None else self.op(res, part)
l += 1 << k
assert res is not None
return res # @line L11
def check_invariant(self) -> None:
"""Check every cell against a direct product of its range."""
for k, row in enumerate(self.st):
assert len(row) == self.n - (1 << k) + 1
for i, v in enumerate(row):
want = self.st[0][i]
for j in range(i + 1, i + (1 << k)):
want = self.op(want, self.st[0][j])
assert v == want, (k, i)
test_sparse_table.py 71 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/sparse-table/. The authors are listed in prov/VSD7FB.jsonl.
import math
import operator
import random
from functools import reduce
import pytest
from sparse_table import SparseTable
def test_example() -> None:
st = SparseTable([5, 2, 8, 1, 9, 3, 7, 4], min)
assert st.lg == [0, 0, 1, 1, 2, 2, 2, 2, 3]
assert st.st[1] == [2, 2, 1, 1, 3, 3, 4]
assert st.st[2] == [1, 1, 1, 1, 3]
assert st.st[3] == [1]
assert st.query(2, 6) == 1
assert st.query(5, 7) == 3
assert st.query(4, 4) == 9
st.check_invariant()
s = SparseTable([5, 2, 8, 1, 9, 3, 7, 4], operator.add)
assert s.query_any(1, 6) == 30
assert s.query(1, 6) == 40 # the overlap is counted twice: the pitfall
def test_edges() -> None:
empty: SparseTable[int] = SparseTable([], min)
assert len(empty) == 0
with pytest.raises(IndexError):
empty.query(0, 0)
one = SparseTable([7], max)
assert one.query(0, 0) == 7 and one.query_any(0, 0) == 7
same = SparseTable([3] * 13, min)
assert same.query(0, 12) == 3
big = SparseTable([2**63 - 1, -(2**63), 0], max)
assert big.query(0, 2) == 2**63 - 1
with pytest.raises(IndexError):
one.query(1, 0)
def test_non_commutative_idempotent() -> None:
# "keep the left one" is associative and idempotent, not commutative.
a = list("sparsetable")
st = SparseTable(a, lambda x, y: x)
for l in range(len(a)):
for r in range(l, len(a)):
assert st.query(l, r) == a[l]
cat = SparseTable(a, operator.add)
for l in range(len(a)):
for r in range(l, len(a)):
assert cat.query_any(l, r) == "".join(a[l : r + 1])
def test_random_against_brute_force() -> None:
rng = random.Random(11)
ops = [min, max, math.gcd, operator.or_, operator.and_]
for _ in range(700):
n = rng.randrange(1, 40)
a = [rng.randrange(0, 64) for _ in range(n)]
op = rng.choice(ops)
st = SparseTable(a, op)
sums = SparseTable(a, operator.add)
for _ in range(15):
l = rng.randrange(n)
r = rng.randrange(l, n)
assert st.query(l, r) == reduce(op, a[l : r + 1])
assert sums.query_any(l, r) == sum(a[l : r + 1])
st.check_invariant()
What the next level needs
- the tests did not run in this build