一点加算・矩形和取得
(DataStructure/BinaryIndexedTree/PointAddRangeSum2D.py)

• View this file on GitHub
• Last update: 2021-01-02 15:25:04+09:00

概要

二次元配列に対して一点加算、矩形和取得を計算量 $O(\log h\log w)$ で行えるデータ構造。

使い方

BinaryIndexedTree(h: int, w: int)
大きさが $h × w$ の二次元 Binary Indexed Tree を構築する。初期値はすべて $0$ である。計算量 $O(hw)$

• add(i: int, j: int, val: int) -> None
  $i$ 行 $j$ 列目の要素に val を加える。計算量 $O(\log h\log w)$

• sum(hl: int, hr: int, wl: int, wr: int) -> int
  矩形範囲 $\lbrack hl, hr) × \lbrack wl, wr)$ の要素の総和を返す。計算量 $O(\log h\log w)$

Verified with

• TestCase/AOJ/0560.BIT.test.py

Code

class BinaryIndexedTree:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.bit = [[0] * (self.w + 1) for _ in range(self.h + 1)]

    def add(self, i, j, val):
        hi, wj = i, j
        i = hi + 1
        while i <= self.h:
            j = wj + 1
            while j <= self.w:
                self.bit[i][j] += val
                j += j & -j
            i += i & -i

    def _sum(self, i, j):
        s, hi, wj = 0, i, j
        i = hi
        while i > 0:
            j = wj
            while j > 0:
                s += self.bit[i][j]
                j -= j & -j
            i -= i & -i
        return s

    def sum(self, hl, hr, wl, wr):
        """sum of values in range [hl, hr) * [wl, wr)"""
        return self._sum(hr, wr) - self._sum(hl, wr) \
               - self._sum(hr, wl) + self._sum(hl, wl)

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