====== 구간 합 구하기 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]

{{tag>BOJ ps:problems:boj:골드_1}}