Day 076-Q4 — 二次元 BIT（2D Fenwick Tree・矩形和クエリ + 点更新 $O(\log H \log W)$）

問題

$H \times W$ のグリッドが与えられる（初期値はすべて 0）。以下の $Q$ 個のクエリを処理せよ：

• クエリ A: A i j v — グリッドの $(i, j)$（1-indexed）の値に $v$ を加算する
• クエリ B: B r1 c1 r2 c2 — 行 $r1$ から $r2$、列 $c1$ から $c2$ の矩形内の値の合計を出力する

入出力例

4 4 5
A 2 2 5
A 3 3 3
B 1 1 4 4
B 2 2 3 3
A 1 4 7

8
8

A(2,2)+=5, A(3,3)+=3 後: B(1,1,4,4)=8, B(2,2,3,3)=5+3=8。

概念図: 2D BIT の prefix sum と矩形包除

矩形和は 4 つの prefix sum の包除で求まる。2D BIT では行・列ともに BIT の更新/クエリをネストして処理する。

ヒント

class BIT2D:
    def __init__(self, H, W):
        self.H = H; self.W = W
        self.data = [[0]*(W+1) for _ in range(H+1)]

    def add(self, i, j, v):
        x = i
        while x <= self.H:
            y = j
            while y <= self.W:
                self.data[x][y] += v
                y += y & (-y)
            x += x & (-x)

    def prefix_sum(self, i, j):
        s = 0; x = i
        while x > 0:
            y = j
            while y > 0:
                s += self.data[x][y]; y -= y & (-y)
            x -= x & (-x)
        return s

    def rect_sum(self, r1, c1, r2, c2):
        return (self.prefix_sum(r2,c2)
                - self.prefix_sum(r1-1,c2)
                - self.prefix_sum(r2,c1-1)
                + self.prefix_sum(r1-1,c1-1))

模範解答

import sys
input = sys.stdin.readline

class BIT2D:
    def __init__(self, H, W):
        self.H = H
        self.W = W
        self.data = [[0] * (W + 1) for _ in range(H + 1)]

    def add(self, i, j, v):
        x = i
        while x <= self.H:
            y = j
            while y <= self.W:
                self.data[x][y] += v
                y += y & (-y)
            x += x & (-x)

    def prefix_sum(self, i, j):
        s = 0
        x = i
        while x > 0:
            y = j
            while y > 0:
                s += self.data[x][y]
                y -= y & (-y)
            x -= x & (-x)
        return s

    def rect_sum(self, r1, c1, r2, c2):
        return (self.prefix_sum(r2, c2)
                - self.prefix_sum(r1 - 1, c2)
                - self.prefix_sum(r2, c1 - 1)
                + self.prefix_sum(r1 - 1, c1 - 1))

def main():
    H, W, Q = map(int, input().split())
    bit = BIT2D(H, W)
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'A':
            i, j, v = int(line[1]), int(line[2]), int(line[3])
            bit.add(i, j, v)
        else:
            r1, c1, r2, c2 = int(line[1]), int(line[2]), int(line[3]), int(line[4])
            out.append(bit.rect_sum(r1, c1, r2, c2))
    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

Step 1: 一次元 BIT の復習

bit[i] は $[i - \text{lowbit}(i) + 1,\; i]$ の和を保持する。更新は $i$ に lowbit(i) を加え続け、クエリは $i$ から lowbit(i) を引き続けて和を取る。

Step 2: 二次元への拡張

行方向の BIT ループの中で、各位置について列方向の BIT ループを回す。data[x][y] は「行方向区間 $[\ldots, x]$、列方向区間 $[\ldots, y]$」の部分和を表す（BIT のセマンティクスにより）。

Step 3: 矩形和の包除原理

$$\text{rect}(r1, c1, r2, c2) = P(r2,c2) - P(r1-1,c2) - P(r2,c1-1) + P(r1-1,c1-1)$$

ここで $P(i,j) = \text{prefix\_sum}(i,j)$（$(1,1)$ から $(i,j)$ までの和）。

Step 4: 計算量の確認

点加算: 行 $O(\log H)$ × 列 $O(\log W)$ = $O(\log H \log W)$。矩形和: 4 つの prefix sum × 同コスト = $O(\log H \log W)$。全体: $O(Q \log H \log W)$。

Step 5: メモリ

data は $(H+1) \times (W+1)$ のリスト。$H = W = 1000$ なら $\approx 10^6$ 要素で問題なし。

よくあるミス

次のステップ

• 発展問題: 「3 次元 BIT」→ 同じ原理で 3 重ループ。$O(\log^3 N)$ で点更新・直方体和クエリ

自己評価