日期：2026年5月27日
ZeroJudge 題目連結：d796. 區域調查
解題想法
這題理論上可以用線段樹解題，但是程式碼非常長，我只寫了二元索引樹版本，0.3 s 過關，Python 會超時。
Python 程式碼
測資 #0 50%，4.7s，90.3 MB。測資 #1 開始超時。如果把二維串列攤平成一維串列，應該還可以再快一點。
class BIT2D:
def __init__(self, n, m):
self.n = n
self.m = m
self.arr = [[0]*(m+1) for _ in range(n+1)]
self.tree = [[0]*(m+1) for _ in range(n+1)]
def _lowbit(self, x):
return x & (-x)
def _update(self, x, y, delta):
i = x
while i <= self.n:
j = y
while j <= self.m:
self.tree[i][j] += delta
j += self._lowbit(j)
i += self._lowbit(i)
def _query(self, x, y):
total = 0
i = x
while i > 0:
j = y
while j > 0:
total += self.tree[i][j]
j -= self._lowbit(j)
i -= self._lowbit(i)
return total
def update_val(self, x, y, val):
delta = val - self.arr[x][y]
self._update(x, y, delta)
self.arr[x][y] = val
def query_range(self, x1, y1, x2, y2):
if x1 > x2: x1, x2 = x2, x1
if y1 > y2: y1, y2 = y2, y1
return self._query(x2, y2) - self._query(x1 - 1, y2) - self._query(x2, y1 - 1) + self._query(x1 - 1, y1 - 1)
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
N = int(data[ptr])
Q = int(data[ptr+1])
ptr += 2
bit = BIT2D(N, N)
for i in range(1, N+1):
for j in range(1, N+1):
v = int(data[ptr])
ptr += 1
bit.update_val(i, j, v)
for _ in range(Q):
op = int(data[ptr])
ptr += 1
if op == 1:
x1 = int(data[ptr])
y1 = int(data[ptr+1])
x2 = int(data[ptr+2])
y2 = int(data[ptr+3])
ptr += 4
ans = bit.query_range(x1, y1, x2, y2)
result.append(f"{ans:d}\n")
else:
x = int(data[ptr])
y = int(data[ptr+1])
v = int(data[ptr+2])
ptr += 3
bit.update_val(x, y, v)
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
