구간 합 구하기 2

• 구간 업데이트와 구간 합 쿼리 를 요구하는 문제이다.
• 세그먼트 트리의 lazy propagation을 필요로 하는 대표적인 문제이다. 이 경우 구간합과 구간 업데이트를 모두 O(logn)에 해결 가능하다.
• 그리고, 2개의 펜윅 트리를 조합해서도 O(logn) 에 각 쿼리를 해결할 수 있는 것이 알려져 있다. n이 커지면, 이 방법이 세그먼트 트리보다 빠르게 동작한다. 자세한 것은 펜윅 트리 참고.
• 트리를 구축하는 것에 O(n)이 걸리고, m+k개의 쿼리를 각각 O(logn)에 해결하므로, 전체 시간 복잡도는 O(n + (m+k)logn)

"""Solution code for "BOJ 10999. 구간 합 구하기 2".

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

import sys
from teflib import fenwicktree


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    range_fenwick = fenwicktree.RangeUpdatableFenwickTree(
        (int(sys.stdin.readline()) for _ in range(N)))
    for _ in range(M + K):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            a, b, c, d = query
            range_fenwick.range_update(b - 1, c, d)
        else:
            a, b, c = query
            print(range_fenwick.query(b - 1, c))


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.RangeUpdatableFenwickTree