Sparse Table
(Sparse_Table.py)

• View this file on GitHub
• Last update: 2025-06-22 19:54:08+09:00
• Link: https://qiita.com/recuraki/items/0fcbc9e2abbc4fae5f62"""

Outline

可換で冪等律を満たす半群 $S=(S, *)$ の列 $A=(A_0, A_1, \dots, A_{\lvert A \rvert-1})$ に対して, 区間積 $A_L * \dots * A_R$ の計算を $O(1)$ Time で行うことができるデータ構造.

ただし, 区間積を $O(1)$ Time で計算できる代償として, 更新ができない.

Constructer

T=Sparse_Table(A, calc)

• $A$ : $S$ の列

以下, $N:=\lvert A \rvert$ とする.

• $\operatorname{calc} : S \times S \to S; (x,y) \mapsto x * y$ : 二項演算
• 計算量 : $O(N \log N)$ Time.

---

product

T.product(l, r, default=None, left_close=True, right_close=True)

• 区間積 $A_L * A_{L+1} * \dots * A_R$ を求める. なお, $L>R$ の場合は default を返す.
• なお, left_close , right_close を False とすると, それぞれに対応する方が開区間 (端点が含まれない) になる.
• 制約
  • $0 \leq L \lt N$
  • $0 \leq R \lt N$
• 計算量 : $O(1)$ Time.

Verified with

• test_verify/yosupo_library_checker/Data_Structure/Sparse_Table.test.py

Code

from typing import TypeVar, Generic, Callable

SemiGroup = TypeVar('SemiGroup')
class Sparse_Table(Generic[SemiGroup]):
    """ 参考: https://qiita.com/recuraki/items/0fcbc9e2abbc4fae5f62"""

    def __init__(self, A: list[SemiGroup], op: Callable[[SemiGroup, SemiGroup], SemiGroup]):
        """ 半群 (SemiGroup, op) 上の列 A に関する Sparse Table を構築する.

        Args:
            A (list[SemiGroup]): 半群 (SemiGroup, op) 上の列
            op (Callable[[SemiGroup, SemiGroup], SemiGroup]): 半群上の演算 (x, y) -> xy

        Remark:
            半群 (SemiGroup, op) は結合則, 可換則, 冪等則を満たしていることを要求する.
        """
        self.op = op
        n = len(A)
        depth = max(1, (n - 1).bit_length())

        self.table = [[a for a in A]]
        for k in range(1, depth):
            prev_row = self.table[-1]
            m = 1 << (k - 1)
            row = [op(prev_row[i], prev_row[i + m]) for i in range(n - 2 * m + 1)]
            self.table.append(row)

    def __len__(self) -> int:
        return len(self.table[0])

    def product(self, l: int, r: int, default: SemiGroup = None, left_close: bool = True, right_close: bool = True) -> SemiGroup:
        """ 総積 A_l A_{l+1} ... A_r を求める. ただし, 空積は default とする.

        Args:
            l (int): 左端
            r (int): 右端
            default (SemiGroup, optional): 空積のときの返り値. Defaults to None.
            left_close (bool, optional): False にすると, 左端が開になる. Defaults to True.
            right_close (bool, optional): False にすると, 右端が開になる. Defaults to True.

        Returns:
            SemiGroup: 総積
        """

        # 区間を左半開区間に変換する.
        if not left_close:
            l += 1

        if right_close:
            r += 1

        length = r - l
        if length == 1:
            # 単項
            return self.table[0][l]
        elif length <= 0:
            # 空積
            return default

        lv = (length - 1).bit_length() - 1
        row = self.table[lv]
        return self.op(row[l], row[r - pow(2, lv)])

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page