문제링크

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

코드

import sys, math

tree = []
a = []


def solution():
    global a, tree

    read = sys.stdin.readline
    write = sys.stdout.write
    n, q = map(int, read().split())
    a = list(map(int, read().split()))
    commands = [list(map(int, read().split())) for _ in range(q)]

    h = math.ceil(math.log(n, 2))
    tree_size = 2 ** (h+1)
    tree = [0] * tree_size
    init(0, n-1, 1)

    for x, y, aa, b in commands:

        if x > y:
            y, x = x, y
        write(f'{get_sum(x-1, y-1, 0, n-1, 1)}\n')

        diff = b - a[aa-1]
        origin = a[aa-1]
        a[aa-1] = b
        update(aa-1, 0, n-1, 1, diff, origin)


def init(start, end, node):

    # 리프노드일때
    if start == end:
        tree[node] = a[start]
        return tree[node]

    # 아닐때
    tree[node] = init(start, (start+end)//2, node*2) + init((start+end)//2+1, end, node*2+1)
    return tree[node]


def get_sum(left, right, start, end, node):

    # 포함하지 않을 때
    if left > end or right < start:
        return 0

    # 포함할 때
    if left <= start and end <= right:
        return tree[node]

    return get_sum(left, right, start, (start+end)//2, node*2) + get_sum(left, right, (start+end)//2+1, end, node*2+1)


def update(index, start, end, node, diff, origin):

    # 포함하지 않을 때
    if index < start or index > end:
        return

    tree[node] += diff
    # 리프가 아닐 때
    if start != end:
        update(index, start, (start+end)//2, node*2, diff, origin)
        update(index, (start+end)//2+1, end, node*2+1, diff, origin)


solution()