[백준] 2042 - 구간 합 구하기 / 바이너리 인덱스 트리

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
num_list = [0] * (n+1)
tree = [0] * (n+1)

def update_tree(idx, dif):
    while idx <= n:
        tree[idx] += dif
        idx += idx & -idx
def prefix_sum(idx):
    result = 0
    while idx > 0:
        result += tree[idx]
        idx -= idx & -idx
    return result

for i in range(n):
    tmp = int(input().strip())
    dif = tmp - num_list[i+1]
    num_list[i+1] = tmp
    update_tree(i+1, dif)    
     
for _ in range(m+k):
    a, b, c = map(int, input().split())
    if a == 1:
        dif = c - num_list[b]
        num_list[b] = c
        update_tree(b, dif) 
    else:
        print(prefix_sum(c) - prefix_sum(b-1))

 

참고

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)