[Python] 백준 2042번: 구간 합 구하기(using fenwick-tree)

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

2042번: 구간 합 구하기

 

import sys
input = sys.stdin.readline


def update_fenwick_tree(tree, index, value):
    while index < len(tree):
        tree[index] += value
        index += (index & -index)

    return tree


def query_fenwick_tree(tree, index):
    res = 0
    while index > 0:
        res += tree[index]
        index -= (index & -index)

    return res


if __name__ == '__main__':
    N, M, K = map(int, input().split())

    tree = [0]*(N+1)
    nums = [int(input()) for _ in range(N)]
    for i in range(N):
        tree = update_fenwick_tree(tree, i+1, nums[i])

    for _ in range(M + K):
        a, b, c = map(int, input().split())

        if a == 1:
            tree = update_fenwick_tree(tree, b, c - nums[b-1])
            nums[b-1] = c
        elif a == 2:
            print(query_fenwick_tree(tree, c) - query_fenwick_tree(tree, b-1))

 

펜윅트리에 대한 설명은 아래 링크에 너무나도 잘 되어있다.

 

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

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

 

 

 

펜윅트리를 구현한 뒤, update만 좀 신경써주면 된다. update는 값을 더하는 것이 기본이기 때문에, 가령 3을 7로 바꿔야한다고 하면 4를 인자로 넣어주는 것이다.

업데이트를 마친 뒤 nums(입력 받은 값, 트리가 아님)에 바뀐 값(7)을 넣어주어야한다.