071 구간 합 구하기

첫번째 코드

 

세그먼트 트리에 관련된 문제이다.

개념에 따라서 천천히 책을 참고하면서 코드를 작성하면 이해하기 편하다.

하지만 꾸준히 혼자 생각하면서 다음에 또 풀어봐야 할 문제이다.

 

점점 개념이 많아지면서 헷갈린다.

한번만이 아니라 꾸준히 보면서 상기시켜야 할 것이다.

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
treeHeight = 0
length = n

while length != 0:
    length //= 2
    treeHeight += 1

treeSize = 2 ** (treeHeight + 1)
leftNodeStartIndex = treeSize//2 - 1
tree = [0] * (treeSize + 1)

for i in range(leftNodeStartIndex + 1, leftNodeStartIndex + n + 1):
    tree[i] = int(input())

def setTree(i):
    while i != 1:
        tree[i // 2] += tree[i]
        i -= 1

setTree(treeSize - 1)

def ChangeVal(index, value):
    diff = value - tree[index]
    while index > 0:
        tree[index] = tree[index] + diff
        index = index // 2

def getSum(s, e):
    partSum = 0
    while s <= e:
        if s % 2 == 1:
            partSum += tree[s]
            s += 1
        if e % 2 == 0:
            partSum += tree[e]
            e -= 1
        s = s // 2
        e = e // 2
    return partSum

for _ in range(m + k):
    question, s, e = map(int, input().split())
    if question == 1:
        ChangeVal(leftNodeStartIndex + s, e)
    elif question == 2:
        s = s + leftNodeStartIndex
        e = e + leftNodeStartIndex
        print(getSum(s, e))

 

통과

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/2042.%E2%80%85%EA%B5%AC%EA%B0%84%E2%80%85%ED%95%A9%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0

programmers/백준/Gold/2042. 구간 합 구하기 at main · ornni/programmers