테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 수들의 합 7 ======

===== 풀이 =====
  * [[ps:problems:boj:2042|구간 합 구하기]]와 동일하게, 아무 응용 없이 기본적인 [[ps:구간 쿼리#구간합|구간합 쿼리 + 포인트 업데이트 쿼리]]를 묻는 문제.
  * 다만 쿼리의 갯수가 최대 1,000,000으로 상당히 커서 시간이 빡빡하다. Python으로 제출시 세그먼트 트리로는 시간 초과가 났고, 펜윅트리로만 통과됐다.
  * 그리고 실수하기 쉬운 포인트는, sum쿼리에 대한 입력에 대해서 i<j 이거나 i>j 인 경우 모두 가능하다는 점에 주의.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2268. 수들의 합 7".

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

import sys
from teflib import fenwicktree


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


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]

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