-
Notifications
You must be signed in to change notification settings - Fork 0
/
BOJ_2042.py
65 lines (52 loc) · 2.12 KB
/
BOJ_2042.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import sys
input = sys.stdin.readline
def init(node, start, end):
# start == end는 리프 노드일 때를 뜻함
# 리프 노드인 경우 배열의 원소 값을 반환
if start == end:
tree[node] = l[start]
return tree[node]
# 재귀적으로 왼쪽, 오른쪽 자식 트리를 만들고 합을 저장
middle = (start + end) // 2
tree[node] = init(node*2, start, middle) + init(node*2+1, middle+1, end)
return tree[node]
# 트리의 구역 start, end
# 합을 구할 구역 left, right
def section_sum(node, start, end, left, right):
# 합을 구해야하는 구역과 현재 탐색할 트리의 구역이 겹치지 않아 탐색할 필요가 없다
if left > end or right < start:
return 0
# 범위에 포함될 시 그 자식노드들도 포함이기 때문에 더 이상 호출하지 않아도 된다
if left <= start and right >= end:
return tree[node]
middle = (start+end)//2
# 왼쪽, 오른쪽 자식을 루트로 하는 트리에서 재귀적으로 재탐색
return section_sum(node*2, start, middle, left, right) + section_sum(node*2+1, middle+1, end, left, right)
def change_num(node, start, end, index, diff):
# 범위 외일 시 종료
if index < start or index > end:
return
# 트리의 값을 Update
tree[node] += diff
# 리프 노드가 아닐 경우 자식들도 값을 변경해야하기 때문에 재귀적으로 호출
if start != end:
middle = (start+end)//2
change_num(node*2, start, middle, index, diff)
change_num(node*2+1, middle+1, end, index, diff)
# 수의 개수, 수의 변경이 일어나는 횟수, 구간의 합을 구하는 횟수
n, m, k = map(int, input().split())
l = []
tree = [0 for _ in range(3000000)]
for _ in range(n):
l.append(int(input()))
init(1, 0, n-1)
for _ in range(m+k):
a, b, c = map(int, input().split())
if a == 1:
b -= 1
# 현재 인덱스에 있는 수와 바꿔야되는 수의 차이
diff = c - l[b]
l[b] = c
change_num(1, 0, n-1, b, diff)
else:
print(section_sum(1, 0, n-1, b-1, c-1))