수열과 쿼리 22

• 포인트 업데이트 + 구간합 쿼리를 처리하는 기본 문제이다.
• 다만, 순서대로 쿼리를 처리해서는 해결이 안되기 때문에, 오프라인 쿼리 처리를 강제하는 문제이다
  • (뭐.. 퍼시스턴트 세그먼트 트리를 쓴다면 굳이 온라인으로 못할 것도 없긴 하다)
• 쿼리를 미리 모두 읽어서 처리해야 할 순서대로 잘 정렬해주면, 각각의 쿼리는 기본적인 펜윅 트리나 세그먼트 트리를 사용해서 O(logn)에 해결 가능하다.
• 그래서 총 시간복잡도는 O(qlogq + qlogn)이 되어야 하겠지만, 실제 구현에서는 쿼리를 정렬하지도 않고, 그냥 N사이즈의 버켓에 나눠 담아버렸다. 그래서 실질적으로는 O(q + qlogn) = O(qlogn)

"""Solution code for "BOJ 16978. 수열과 쿼리 22".

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

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())
    sum_queries = [[] for _ in range(M)]
    sum_query_num = 0
    update_queries = []
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, v = query
            update_queries.append((i - 1, v))
        else:
            _, k, i, j = query
            sum_queries[k].append((i - 1, j, sum_query_num))
            sum_query_num += 1

    answers = [0] * sum_query_num
    fenwick = fenwicktree.FenwickTree(A)
    for i, (pos, value) in enumerate(update_queries):
        for beg, end, n in sum_queries[i]:
            answers[n] = fenwick.query(beg, end)
        fenwick.set(pos, value)
    for beg, end, n in sum_queries[len(update_queries)]:
        answers[n] = fenwick.query(beg, end)

    print(*answers, sep='\n')


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree