問題
N×N グリッドに対し: add x y v で値加算、sum x1 y1 x2 y2 で矩形和。
制約
$1 \le N \le 1000$
$1 \le Q \le 2 \times 10^5$
v は整数（負も可）
入出力例
入力例 1
4 5
add 2 3 5
add 1 1 3
sum 1 1 4 4
sum 2 2 4 4
add 3 3 -2出力例 1
8
5ヒント (段階的開示)
ヒント1: 方向性
2次元BIT は行・列に BIT を適用。点加算・矩形和ともに $O(\log^2 N)$。
ヒント2: アプローチ
矩形和は包除原理: query(x2,y2) - query(x1-1,y2) - query(x2,y1-1) + query(x1-1,y1-1)。
ヒント3: 誘導
外側で行 i、内側で列 j を BIT 走査。i, j ともに $i \mathrel{+}= i \& (-i)$。
模範解答 (Python)
import sys
input = sys.stdin.readline
class BIT2D:
def __init__(self, n):
self.n = n
self.tree = [[0] * (n + 1) for _ in range(n + 1)]
def update(self, x, y, v):
i = x
while i <= self.n:
j = y
while j <= self.n:
self.tree[i][j] += v
j += j & (-j)
i += i & (-i)
def query(self, x, y):
s = 0; i = x
while i > 0:
j = y
while j > 0:
s += self.tree[i][j]
j -= j & (-j)
i -= i & (-i)
return s
def rect_sum(self, x1, y1, x2, y2):
return (self.query(x2, y2)
- self.query(x1 - 1, y2)
- self.query(x2, y1 - 1)
+ self.query(x1 - 1, y1 - 1))
def main():
N, Q = map(int, input().split())
bit = BIT2D(N)
out = []
for _ in range(Q):
line = input().split()
if line[0] == 'add':
x, y, v = int(line[1]), int(line[2]), int(line[3])
bit.update(x, y, v)
else:
x1, y1, x2, y2 = int(line[1]), int(line[2]), int(line[3]), int(line[4])
out.append(bit.rect_sum(x1, y1, x2, y2))
print('\n'.join(map(str, out)))
main()Step-by-Step 解説
11次元BIT
更新: $i \mathrel{+}= i \& (-i)$、クエリ: $i \mathrel{-}= i \& (-i)$。
更新: $i \mathrel{+}= i \& (-i)$、クエリ: $i \mathrel{-}= i \& (-i)$。
22次元拡張
外側で行、内側で列を走査。
外側で行、内側で列を走査。
3矩形クエリ
2次元の包除原理。
2次元の包除原理。
4計算量
各 $O(\log^2 N)$、N=1000, Q=2×10^5 で 2×10^7 操作。
各 $O(\log^2 N)$、N=1000, Q=2×10^5 で 2×10^7 操作。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 配列サイズ N+1 | 1-indexed | [[0]*(N+1) for _ in range(N+1)] |
| 包除の符号ミス | 4 項の符号 | +,−,−,+ で確実に |
| int overflow (C) | Python は不問 |
次のステップ
- 3次元BIT、2次元 Segment Tree との比較