# BOJ - 2042 - 구간 합 구하기

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 updateValue(tree, node, left, right, target, value):
if (target < left or right < target): return 0
tree[node] += value
if left == right: return 0

mid = (left + right) // 2
updateValue(tree, node * 2, left, mid, target, value)
updateValue(tree, node * 2 + 1, mid + 1, right, target, value)

def sumValue(tree, node, start, end, left, right):

if (right < start or end < left): return 0
elif (left <= start and end <= right): return tree[node]

mid = (start + end) // 2
return sumValue(tree, node * 2, start, mid, left, right) + \
sumValue(tree, 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):

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

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

for i in range(M + K):

if command[0] == 1:
value = command[2] - arr[command[1] - 1]
arr[command[1] - 1] = command[2]
updateValue(segmentTree, 1, 0, N-1, command[1] - 1, value)

else:
print(sumValue(segmentTree, 1, 0, N-1, command[1]-1, command[2]-1))

solution()
``````

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

Categories:

Updated: