1# from titan_pylib.data_structures.sparse_table.sparse_table import SparseTable
2from typing import Generic, TypeVar, Iterable, Callable
3
4T = TypeVar("T")
5
6
7class SparseTable(Generic[T]):
8 """``SparseTable`` です。
9
10 静的であることに注意してください。
11 """
12
13 def __init__(self, a: Iterable[T], op: Callable[[T, T], T], e: T = None):
14 """
15 :math:`O(n\\log{n})` です。
16
17 Args:
18 a (Iterable[T]): ``SparseTable`` を構築する配列です。
19 op (Callable[[T, T], T]): 2項演算の関数です。
20 e (T, optional): 単位元です。
21 """
22 if not isinstance(a, list):
23 a = list(a)
24 self.size = len(a)
25 log = self.size.bit_length() - 1
26 data = [a] + [[]] * log
27 for i in range(log):
28 pre = data[i]
29 l = 1 << i
30 data[i + 1] = [op(pre[j], pre[j + l]) for j in range(len(pre) - l)]
31 self.data = data
32 self.op = op
33 self.e = e
34
35 def prod(self, l: int, r: int) -> T:
36 """区間 ``[l, r)`` の総積を返します。
37
38 :math:`O(\\log{n})` です。
39
40 Args:
41 l (int): インデックスです。
42 r (int): インデックスです。
43 """
44 assert (
45 0 <= l <= r <= self.size
46 ), f"IndexError: {self.__class__.__name__}.prod({l}, {r}), len={self.size}"
47 if l == r:
48 return self.e
49 u = (r - l).bit_length() - 1
50 return self.op(self.data[u][l], self.data[u][r - (1 << u)])
51
52 def __getitem__(self, k: int) -> T:
53 assert (
54 0 <= k < self.size
55 ), f"IndexError: {self.__class__.__name__}[{k}], len={self.size}"
56 return self.data[0][k]
57
58 def __len__(self):
59 return self.size
60
61 def __str__(self):
62 return str(self.data[0])
63
64 def __repr__(self):
65 return f"{self.__class__.__name__}({self}, {self.op}, {self.e})"