[백준 11658번] 구간 합 구하기 3 (Python3)

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차원에서는 겹쳐지는 부분이 있기 때문에 주의해야한다.

 

 

오늘의 교훈) 팬윅트리는 매우 유용하다.