[백준 2268번] 수들의 합 7 (Python3)

import sys
input = sys.stdin.readline

def sumfenwick(i):
  SUM = 0
  while i:
    SUM += fenwick[i]
    i -= i&-i
  return SUM

N,M = map(int,input().split())
data,fenwick = [0]*(N+1),[0]*(N+1)

for _ in range(M):
  q,i,j = map(int,input().split())
  if q:
    diff,data[i] = j-data[i],j
    while i <= N:
      fenwick[i] += diff
      i += i&-i
  else:
    print(sumfenwick(max(i,j))-sumfenwick(min(i,j)-1))

구간 합 구하기 [백준 2042번] 구간 합 구하기 (Python3) (tistory.com) 와 거의 똑같은 문제이다. 다만 M의 크기가 100만으로 매우 크다는 것이 차이점인데, 이로 인해서 파이썬의 경우 세그먼트 트리로는 코드가 시간초과로 통과가 안된다.

세그먼트 트리를 C++로 구현하던지 다른 방법을 찾아야 했는데, 나는 팬윅 트리를 이용하였다.

 

팬윅 트리는 세그먼트 트리와 비슷한 원리의 자료구조인데, 구간합을 구하는데 있어서 훨씬 효율적이고 구현이 매우 쉽다는 장점이 있다. 시간복잡도 자체는 세그먼트 트리와 똑같이 O(logN)이지만, 비트연산을 이용하고 재귀를 이용하지 않기 때문에 훨씬 빠르다. 다만 누적합 방식을 이용하기 때문에 구간의 최솟값, 최댓값과 같은 연산에는 이용하기 어렵다는 단점이 있다.

 

팬윅 트리의 구현은 https://yabmoons.tistory.com/438 이곳을 참조하였다.

 

 

오늘의 교훈) 구간합을 구할때는 세그먼트 트리보다는 팬윅 트리를 이용하자