구간 합 구하기

• 기본적인 구간합 쿼리 + 포인트 업데이트 쿼리 문제.
• 펜윅 트리나 세그먼트 트리를 사용하면, 트리를 만드는데에 O(n), 각 쿼리를 처리하는 데에 O(logn), 그래서 전체 O(n + (m+k)logn)에 해결 가능하다.
• 이 문제에서는 쿼리가 최대 20000개인데, 이 정도 범위에서는 펜윅트리가 세그먼트 트리와 비슷하게 속도가 나거나 오히려 느리게 나오거나 했다.

"""Solution code for "BOJ 2042. 구간 합 구하기".

- Problem link: https://www.acmicpc.net/problem/2042
- Solution link: http://www.teferi.net/ps/problems/boj/2042
"""

import sys
from teflib import fenwicktree


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    nums = [int(sys.stdin.readline()) for _ in range(N)]
    fenwick = fenwicktree.FenwickTree(nums)
    for _ in range(M + K):
        a, b, c = [int(x) for x in sys.stdin.readline().split()]
        if a == 1:
            fenwick.set(b - 1, c)
        else:
            print(fenwick.query(b - 1, c))


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree