하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

• 구간에 등차수열을 더하는 업데이트와, 특정 포인트의 값을 구하는 두 종류의 쿼리를 처리해야 하는 문제.
• 등차수열을 더하는 업데이트도 세그먼트 트리의 lazy propagation으로 처리가 불가능한 것은 아니지만 다소 복잡하다.
• 원소의 값을 구간합으로 처리하는 테크닉을 여기에 적용하면, 구간에 일정한 값을 더하는 업데이트와 구간합을 구하는 쿼리로 변환된다.
• 여전히 lazy propagation이 필요하기는 하지만, 쿼리 종류가 흔히 접하던 유형으로 변환되어서 쉽게 식을 세울 수 있다. 또한 이 형태는 구간 업데이트 펜윅트리 의 테크닉을 사용하면 펜윅트리 두개의 조합으로도 해결이 가능하다. 아래 코드는 이 방식으로 구현된 RangeUpdatableFenwickTree를 사용한 버전.
• 어떻게 하든 쿼리를 처리하는 시간 복잡도 자체에는 변화가 없다. 쿼리당 O(logn)이 걸린다. 트리를 O(n)에 구축하고 q개의 쿼리를 처리하면 전체 시간복잡도는 O(n+qlogn)

"""Solution code for "BOJ 17353. 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별".

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

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()]
    range_fenwick = fenwicktree.RangeUpdatableFenwickTree(N)
    Q = int(sys.stdin.readline())
    for _ in range(Q):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, L, R = query
            range_fenwick.range_update(L - 1, R, 1)
            range_fenwick.range_update(R, R + 1, -(R - L + 1))
        else:
            _, X = query
            print(range_fenwick.query(0, X) + A[X - 1])


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.RangeUpdatableFenwickTree