가계부 (Hard)

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

"""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()

• Dependency: teflib.fenwicktree.FenwickTree