12837번 가계부 (Hard)

이왜틀?

---

12837번 가계부 (Hard) - 백준

이왜틀 마지막 골드 문제
솔직히 이건 소스 볼 필요도 없다.
Hard라는건 Easy도 있다는 말이고
아마 과거의 내가 Easy를 풀고 소스 그대로 Hard에 집어넣어서 시간초과 났을 것이다.

설계

---

대충 구간합 구하는데 값 변경이 필요함 == 세그먼트 트리

구현

---

1. 세그먼트 트리 구현

update와 query로 구성된 정석적인 세그먼트 트리 클래스를 구현한다.
값 갱신이 아니라 숫자를 합하는 것에 주의

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.size = 1 

        while self.size < self.n:
            self.size *= 2

        self.tree = [0] * (2 * self.size)

    def update(self, idx, val):
        idx += self.size
        # 갱신이 아니라 합치기
        self.tree[idx] += val

        while idx > 1:
            idx //= 2 
            self.tree[idx] = self.tree[idx * 2] + self.tree[idx * 2 + 1]
            
    def query(self, l, r):
        l += self.size
        r += self.size
        result = 0

        while l <= r:
            if l % 2 == 1:
                result += self.tree[l]
                l += 1
            if r % 2 == 0:
                result += self.tree[r]
                r -= 1

            l //= 2
            r //= 2

        return result

2. 쿼리 수행

입력받아 쿼리를 수행한다.

N, Q = map(int, input().split())
tree = SegmentTree(N)

for _ in range(Q):
    q, p, x = map(int, input().split())

    # 1은 업데이트 2는 구간합
    if q == 1:
        tree.update(p - 1, x)
    elif q == 2:
        print(tree.query(p - 1, x - 1))

채점

---

반성

---

골드도 끝났고 플래티넘 문제 2개가 남았다.
이건 각오하고 접근해야지…

코드 확인

---

Link to GitHub