[Python] BOJ 2042번. 구간 합 구하기

작성일 | In |

2042번. 구간 합 구하기

문제 링크

풀이 코드

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
# 2042번. 구간 합 구하기


import sys
input = sys.stdin.readline


def init(start, end, node):  # 세그먼트 트리 만들기
    if start == end:
        tree[node] = nList[start]
        return tree[node]

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


# 구간 합 구하기
def summit(start, end, node, left, right):
    # left 와 right가 범위에서 벗어났기 떄문에 return
    if left > end or right < start:
        return 0

    if left <= start and end <= right:
        return tree[node]

    mid = (start+end) // 2
    return summit(start, mid, node*2, left, right) + summit(mid + 1, end, node*2+1, left, right)


# 특정 인덱스 값 바꾸기
def update(start, end, node, index, diff):
    if index < start or index > end:
        return

    tree[node] += diff
    if start == end:
        return

    mid = (start+end) // 2
    update(start, mid, node*2, index, diff)
    update(mid + 1, end, node * 2 + 1, index, diff)


n, m, k = map(int, input().split())
nList = []
tree = [0] * ((4 * n))

for i in range(n):
    nList.append(int(input()))

init(0, n - 1, 1)

for i in range(m + k):
    cmd = list(map(int, input().split()))

    if cmd[0] == 1:
        cmd[1] -= 1
        diff = cmd[2] - nList[cmd[1]]
        nList[cmd[1]] = cmd[2]
        update(0, n - 1, 1, cmd[1], diff)
    elif cmd[0] == 2:
        print(summit(0, n - 1, 1, cmd[1] - 1, cmd[2] - 1))

비고