백준 10999- 구간합 구하기 2:

by

일반 세그먼트 트리는 O(log(N))에서 특정 간격, 최소, 최대, xor, …의 세그먼트 합계를 쿼리할 수 있습니다.

또한 업데이트는 O(log(N)) 시간에도 가능하지만 간격의 길이가 M일 때 주어진 범위에 대한 업데이트는 O(M log(N)) 그다지 매력적인 시간 복잡도가 아닙니다.

게으른 전파는 간격 업데이트를 더 빠르게 하기 위해 나온 아이디어입니다. 적시에 모든 값을 업데이트하는 대신 실제로 업데이트가 필요할 때만 업데이트됩니다.

즉, 필요한 순간이 올 때까지 시간을 이기는 알고리즘이다.

'추천 관련글,

https://www.acmicpc.net/problem/10999

#10999 섹션의 합 찾기 2

숫자 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 10,000) 및 K(1 ≤ K ≤ 10,000)의 수는 첫 번째 줄에 표시됩니다. M은 숫자가 변경되는 횟수이고 K는 간격의 합이 계산되는 횟수입니다. 그리고 두 번째 라인에서 N+1 라인

www.acmicpc.net

from sys import stdin

f = open("test.txt", "r")

N, M, K = map(int, stdin.readline().split());
nums = (int(stdin.readline()) for i in range(N))

tree = (0) * 4 * N
lazy_val = (0) * 4 * N


def build(left, right, node, node_left, node_right):
    if node_left == node_right:
        tree(node) = nums(node_left)
        return tree(node)
    mid = (node_left + node_right) // 2
    left_val = build(left, right, node * 2, node_left, mid)
    right_val = build(left, right, node * 2 + 1, mid + 1, node_right)
    tree(node) = left_val + right_val
    return tree(node)


def query(left, right, node, node_left, node_right):
    if right < node_left or node_right < left:
        return 0;
    push_down(node, node_left, node_right)

    if left <= node_left and node_right <= right:
        return tree(node)

    mid = (node_left + node_right) // 2

    return query(left, right, node * 2, node_left, mid) + query(left, right, node * 2 + 1, mid + 1, node_right)


def update(left, right, delta, node, node_left, node_right):
    push_down(node, node_left, node_right)

    if right < node_left or node_right < left:
        return
    if left <= node_left and node_right <= right:
        tree(node) += (node_right - node_left + 1) * delta
        if node_left != node_right:
            lazy_val(node * 2) += delta
            lazy_val(node * 2 + 1) += delta
        return

    mid = (node_left + node_right) // 2
    update(left, right, delta, node * 2, node_left, mid)
    update(left, right, delta, node * 2 + 1, mid + 1, node_right)
    tree(node) = tree(node * 2) + tree(node * 2 + 1)


def push_down(node, node_left, node_right):
    if lazy_val(node):
        tree(node) += (node_right - node_left + 1) * lazy_val(node)
        if node_left != node_right:
            lazy_val(node * 2) += lazy_val(node)
            lazy_val(node * 2 + 1) += lazy_val(node)
        lazy_val(node) = 0


build(0, N - 1, 1, 0, N - 1)

for i in range(M + K):
    operation = tuple(map(int, stdin.readline().split()));
    if operation(0) == 1:
        l, r, d = operation(1) - 1, operation(2) - 1, operation(3)
        update(l, r, d, 1, 0, N - 1)
    else:
        l, r = operation(1) - 1, operation(2) - 1
        q = query(l, r, 1, 0, N - 1)
        print(q)

모든 하위 노드를 업데이트하는 대신 상위 노드의 값을 변경하고 하위 노드를 건너뜁니다. 별도의 lazy_val 배열에 기록하여 나중에 계산할 때 무엇을 해야 하는지 알 수 있습니다.

문제에서 입력 범위가 상당히 커서 오버플로가 발생할 수 있습니다. 그러나 파이썬은 천하무적입니다.