Source code for titan_pylib.data_structures.sparse_table.sparse_table_RmQ

 1from titan_pylib.my_class.supports_less_than import SupportsLessThan
 2from typing import Generic, TypeVar, Iterable
 3
 4T = TypeVar("T", bound=SupportsLessThan)
 5
 6

[docs]
 7class SparseTableRmQ(Generic[T]):
 8    """
 9    2項演算を :math:`\\min` にしたものです。
10    """
11
12    def __init__(self, a: Iterable[T], e: T):
13        if not isinstance(a, list):
14            a = list(a)
15        self.size = len(a)
16        log = self.size.bit_length() - 1
17        data = [a] + [[]] * log
18        for i in range(log):
19            pre = data[i]
20            l = 1 << i
21            data[i + 1] = [
22                pre[j] if pre[j] < pre[j + l] else pre[j + l]
23                for j in range(len(pre) - l)
24            ]
25        self.data = data
26        self.e = e
27

[docs]
28    def prod(self, l: int, r: int) -> T:
29        assert 0 <= l <= r <= self.size
30        if l == r:
31            return self.e
32        u = (r - l).bit_length() - 1
33        return (
34            self.data[u][l]
35            if self.data[u][l] < self.data[u][r - (1 << u)]
36            else self.data[u][r - (1 << u)]
37        )

38
39    def __getitem__(self, k: int) -> T:
40        assert 0 <= k < self.size
41        return self.data[0][k]
42
43    def __len__(self):
44        return self.size
45
46    def __str__(self):
47        return str(self.data[0])
48
49    def __repr__(self):
50        return f"{self.__class__.__name__}({self.data[0]}, {self.e})"