테페리넷

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

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

===== 코드 =====
<dkpr py>
"""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()

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

{{tag>BOJ ps:problems:boj:플래티넘_4}}