import sys
input = sys.stdin.readline
def update(y,x,v):
while y<=K:
x1 = x
while x1<=K:
fen[y][x1] += v
x1 += x1&-x1
y += y&-y
def cal(y,x):
s = 0
while y:
x1 = x
while x1:
s += fen[y][x1]
x1 -= x1&-x1
y -= y&-y
return s
def solve(y1,x1,y2,x2):
return cal(y2,x2)-cal(y1-1,x2)-cal(y2,x1-1)+cal(y1-1,x1-1)
N,M = map(int,input().split()); K = 1<<10
board = [[]]+[[0,*map(int,input().split())] for i in range(N)]
fen = [[0]*(K+1) for i in range(K+1)]
for i in range(1,N+1):
for j in range(1,N+1):
update(i,j,board[i][j])
for _ in range(M):
q,*a = map(int,input().split())
if q:
print(solve(*a))
else:
y,x,v = a
d = v-board[y][x]; board[y][x] = v
update(y,x,d)
팬윅트리로 해결하였다.
이전에 세그먼트 트리로 풀려고 여러번 시도했는데 실패했던 문제였다. 팬윅트리로 구현하니 쉽게 해결할 수 있었다.
가로로 팬윅트리로 만든 후, 세로에 대해서 똑같이 팬윅트리로 더해주면 되는 문제이다.
이때 포함관계를 잘 생각해서, 구간합을 구해주어야한다. 구간과 구간 사이를 한번만 빼주면 되는 1차원 팬윅트리와 다르게 2차원에서는 겹쳐지는 부분이 있기 때문에 주의해야한다.
오늘의 교훈) 팬윅트리는 매우 유용하다.