난이도 Easy 버전이 궁금하다면 가계부 (Easy)

BOJ 12837 - 가계부 (Hard) 링크
(2022.11.09 기준 G1)

문제

다음과 같은 두 종류의 쿼리가 Q개 주어진다.
1. 1 p x : 생후 p일에 x를 추가한다. (1 ≤ p ≤ N, -2*10^9 ≤ x ≤ 2*10^9)
2. 2 p q : 생후 p일부터 q일까지 변화한 양을 출력한다. (1 ≤ p ≤ q ≤ N)

2번 쿼리에 대해 계산된 값을 각 줄에 출력

알고리즘

Easy처럼 쿼리를 그대로 구현하면 터진다.
그러므로 이 문제처럼 리스트의 특정 인덱스의 값 변경과 특정 범위의 합을 구하는 연산이 자주 일어나면 세그먼트 트리를 사용해야 한다.

풀이

이분 탐색을 사용할 줄 아는가? 그와 비슷한 개념이라고 생각해도 된다.
세그먼트 트리는 범위를 반으로 나누어 합이든 곱이든 원하는 값을 저장하고 다시 반으로 나누어가는.. 그런 트리다.

이 문제는 트리에 구간 합을 저장해야 한다. 아주아주 간단하고 기초 세그먼트 트리 문제이므로 세그먼트 트리에 대한 공부를 했다면 바로 풀 수 있는 문제일 것이다.

처음엔 모든 날의 수입이나 지출은 전부 0이므로 리스트를 트리로 만들어줄 필요가 없다.
그냥 바로 0으로 초기화된 알맞은 크기의 트리를 만들면 된다.
그리고 모든 쿼리를 수행 및 필요에 따라 출력.

별다른 설명은 따로 하지 않고 코드에 주석을 달겠다. 기본적인 세그먼트 트리를 모른다면 구글링해서 기초적인 부분은 알아오자.
다만, 하나의 조언을 하자면
날마다의 수입이나 지출을 저장할 리스트를 만들어놓고 1번 쿼리를 수행할 때마다 tree 값 뿐만 아니라 리스트 값까지 변경하는 그런 바보 같은 짓은 하지 말자.
리스트 값은 필요로 하지 않을 뿐더러 소요 시간도 확 오른다.

코드

import sys; input = sys.stdin.readline
from math import ceil, log2

def update(node, start, end): # 1번 쿼리 (값 변경)
    if start <= p <= end: # 현재 범위에 p가 들어있으면
        tree[node] += q # 트리 값에 q 더하고
        if start != end: # start와 end가 같지 않으면 반으로 나눈 두 범위에 update
            mid = (start + end) // 2
            update(node * 2, start, mid)
            update(node * 2 + 1, mid + 1, end)

def calc(node, start, end): # 2번 쿼리 (합 계산)
    if q < start or end < p: # 현재 범위와 구하려는 범위가 서로 벗어나면
        return 0 # 0 반환
    if p <= start and end <= q: # 구하려는 범위 안 현재 범위가 포함되어 있으면
        return tree[node] # tree 값 반환
    # 위 두 경우에 포함되지 않으면 반으로 나눈 두 범위로 하여금 calc 재귀
    mid = (start + end) // 2
    return calc(node * 2, start, mid) + calc(node * 2 + 1, mid + 1, end)

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

# 어차피 초기 리스트는 전부 0이므로 바로 트리를 만들자.
tree = [0] * (1 << (ceil(log2(N)) + 1))

# 0-based index를 유의해서 인덱스에는 -1을 해주자.
for _ in range(Q):
    query, p, q = map(int, input().split())
    if query == 1: # 1번 쿼리 (update)
        p -= 1
        update(1, 0, N - 1)
    else: # 2번 쿼리 (calc)
        p -= 1; q -= 1
        print(calc(1, 0, N - 1))

여담

그야말로 Easy한 Hard다.