二次元Sparse Table
(DataStructure/misc/SparseTable2D.py)

• View this file on GitHub
• Last update: 2021-02-14 12:02:31+09:00

概要

構築を $O(hw\log h\log w)$、矩形畳み込みを $O(1)$ で行える二次元データ構造。畳み込みは半群 + 冪等性を要請する。定数倍が重いので注意。

使い方

SparseTable(matrix: Sequence[Sequence[Any]], op: Callable[[Any, Any], Any])
大きさ $h × w$ の matrix を初期値とした 二次元 Sparse Table を構築する。op は畳み込み計算で用いる演算子であり、定数倍改善のため引数を 4 つ取ることがあるので注意。計算量 $O(hw\log h\log w)$

• fold(hl: int, hr: int, wl: int, wr: int) -> Any
  矩形範囲 $\lbrack hl, hr) × \lbrack wl, wr)$ の要素の畳み込み結果を返す。計算量 $O(1)$

Verified with

• TestCase/AOJ/1068.test.py

Code

class SparseTable2D:
    def __init__(self, matrix, op):
        h = len(matrix)
        w = len(matrix[0])
        self.op = op
        lg_h = h.bit_length()
        lg_w = w.bit_length()

        self.lg_tbl = [0] * (max(h, w) + 1)
        for i in range(2, len(self.lg_tbl)):
            self.lg_tbl[i] = self.lg_tbl[i // 2] + 1

        self.sp_tbl = [[] * lg_w for _ in range(lg_h)]
        self.sp_tbl[0].append(matrix)

        for lv_h in range(lg_h - 1):
            dh = 1 << lv_h
            data = [[0] * w for _ in range(h - dh * 2 + 1)]
            tbl = self.sp_tbl[lv_h][0]
            for i in range(h - dh * 2 + 1):
                for j in range(w):
                    data[i][j] = op(tbl[i][j], tbl[i + dh][j])
            self.sp_tbl[lv_h + 1].append(data)

        for lv_w in range(lg_w - 1):
            dw = 1 << lv_w
            data = [[0] * (w - dw * 2 + 1) for _ in range(h)]
            tbl = self.sp_tbl[0][lv_w]
            for i in range(h):
                for j in range(w - dw * 2 + 1):
                    data[i][j] = op(tbl[i][j], tbl[i][j + dw])
            self.sp_tbl[0].append(data)

        for lv_h in range(lg_h - 1):
            dh = 1 << lv_h
            for lv_w in range(lg_w - 1):
                dw = 1 << lv_w
                data = [[0] * (w - dw * 2 + 1) for _ in range(h - dh * 2 + 1)]
                tbl = self.sp_tbl[lv_h][lv_w]
                for i in range(h - dh * 2 + 1):
                    for j in range(w - dw * 2 + 1):
                        # 二項演算ではない
                        data[i][j] = op(tbl[i][j], tbl[i][j + dw], tbl[i + dh][j], tbl[i + dh][j + dw])
                self.sp_tbl[lv_h + 1].append(data)

    def fold(self, hl, hr, wl, wr):
        lv_h = self.lg_tbl[hr - hl]
        lv_w = self.lg_tbl[wr - wl]
        tbl = self.sp_tbl[lv_h][lv_w]
        ul = tbl[hl][wl]
        ur = tbl[hl][wr - (1 << lv_w)]
        dl = tbl[hr - (1 << lv_h)][wl]
        dr = tbl[hr - (1 << lv_h)][wr - (1 << lv_w)]
        return self.op(ul, ur, dl, dr)  # 二項演算ではない

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/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.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page