====== 가계부 (Hard) ======

===== 풀이 =====
  * 그냥 전형적인 [[ps:구간 쿼리#구간합|구간합 쿼리 + 포인트 업데이트 쿼리]] 문제. 펜윅트리를 이용해서 풀면 된다
  * 트리를 만드는데에 O(n), 각 쿼리를 처리하는 데에 O(logn), 그래서 전체 O(n + mlogn)에 해결 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12837. 가계부 (Hard)".

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

Tags: [Fenwick tree]
"""

import sys
from teflib import fenwicktree


def main():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    fenwick = fenwicktree.FenwickTree(N)
    for _ in range(Q):
        oper, *args = [int(x) for x in sys.stdin.readline().split()]
        if oper == 1:
            p, x = args
            fenwick.update(p - 1, x)
        else:
            p, q = args
            print(fenwick.query(p - 1, q))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]

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