수열과 쿼리 21

• 구간 업데이트와 포인트 쿼리를 요구하는 문제이다.
• lazy propagation을 지원하는 세그먼트 트리를 이용해서 푸는 방법도 있지만, 원소의 값을 구간합으로 처리하는 테크닉을 사용하면, 포인트 업데이트와 구간합 쿼리 문제로 변환할 수 있다. 이렇게 푸는 쪽이 단순한 펜윅 트리만을 이용해서 풀 수 있으므로 더 간단하고 빠르게 해결 가능하다.
• lazy propagation을 지원하는 세그먼트 트리를 사용하든, 펜윅트리를 사용하든, 트리를 만드는 데에 O(n), m개의 쿼리를 각각 처리하는 데에 O(logn)이 걸린다. 따라서 총 시간복잡도는 O(n+mlogn)

"""Solution code for "BOJ 16975. 수열과 쿼리 21".

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

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]
    M = int(sys.stdin.readline())

    fenwick = fenwicktree.FenwickTreeForRangeUpdatePointQuery(A)
    for _ in range(M):
        match sys.stdin.readline().split():
            case ['1', i, j, k]:
                fenwick.range_update(int(i) - 1, int(j), int(k))
            case ['2', x]:
                print(fenwick.get(int(x) - 1))


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTreeForRangeUpdatePointQuery