BOJ - 10999 - 구간 합 구하기 2

Updated:

import sys, math

def init(arr, tree, node, start, end):
    if start == end:
        tree[node] = arr[start]
        return tree[node]

    mid = (start + end) // 2
    tree[node] = init(arr, tree, node * 2, start, mid) + \
                 init(arr, tree, node * 2 + 1, mid + 1, end)
    return tree[node]

def updateLazyTree(tree, lazy, node, start, end):
    if lazy[node] != 0:
        tree[node] += lazy[node] * (end - start + 1)
        if start != end:
            lazy[node * 2] += lazy[node]
            lazy[node * 2 + 1] += lazy[node]
        lazy[node] = 0

def updateValue(tree, lazyTree, node, start, end, left, right, value):
    updateLazyTree(tree, lazyTree, node, start, end)

    if (right < start or end < left): return tree[node]
    elif (left <= start and end <= right):
        tree[node] += value * (end - start + 1)
        if start != end:
            lazyTree[node * 2] += value
            lazyTree[node * 2 + 1] += value
        return tree[node]

    mid = (start + end) // 2
    tree[node] = updateValue(tree, lazyTree, node * 2, start, mid, left, right, value) + \
                 updateValue(tree, lazyTree, node * 2 + 1, mid + 1, end, left, right, value)
    return tree[node]

def sumValue(tree, lazy, node, start, end, left, right):
    updateLazyTree(tree, lazy, node, start, end)
    if (right < start or end < left): return 0
    elif (left <= start and end <= right): return tree[node]

    mid = (start + end) // 2
    return sumValue(tree, lazy, node * 2, start, mid, left, right) + \
           sumValue(tree, lazy, node * 2 + 1, mid + 1, end, left, right)

def solution():
    N, M, K = map(int, sys.stdin.readline().split())

    arr = []
    for i in range(N):
        arr.append(int(sys.stdin.readline()))

    height = int(math.ceil(math.log2(N)))
    treeSize = 1 << (height + 1)
    segmentTree = [0] * treeSize
    lazySegmentTree = [0] * treeSize

    init(arr, segmentTree, 1, 0, N-1)

    for i in range(M + K):
        command = list(map(int, sys.stdin.readline().split()))

        if command[0] == 1:
            updateValue(segmentTree, lazySegmentTree, 1, 0, N-1, command[1]-1, command[2]-1, command[3])
        else:
            print(sumValue(segmentTree, lazySegmentTree, 1, 0, N-1, command[1]-1, command[2]-1))

solution()

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

Categories:

Updated:

Leave a comment