[파이썬] 2042 구간 합 구하기

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
li = [int(input()) for _ in range(n)]
tree = [0] * 4 * n

def init(start, end, index):
    if start == end:
        tree[index] = li[start]
        return tree[index]
    mid = (start + end) // 2
    tree[index] = init(start, mid, index * 2) + init(mid + 1, end, index * 2 + 1)
    return tree[index]

def interval_sum(start, end, index, left, right):
    if left > end or right < start:
        return 0
    if left <= start and right >= end:
        return tree[index]
    mid = (start + end) // 2
    return interval_sum(start, mid, index * 2, left, right) + interval_sum(mid + 1, end, index * 2 + 1, left, right)


def update(start, end, index, what, value):
    if what < start or what > end:
        return
    tree[index] += value
    if start == end:
        return
    mid = (start + end) // 2
    update(start, mid, index * 2, what, value)
    update(mid + 1, end, index * 2 + 1, what, value)


init(0, n - 1, 1)
for _ in range(m + k):
    a, b, c = map(int, input().split())
    if a == 1:
        update(0, n - 1, 1, b - 1, c - li[b - 1])
        li[b - 1] = c
    else:
        print(interval_sum(0, n - 1, 1, b - 1, c - 1))

세그먼트 트리