코딩 테스트 구간 처리 최적화

구간 질의가 많은 문제는 자료구조 선택 하나로 통과와 시간 초과가 갈립니다. 갱신 여부와 질의 종류를 기준으로 누적합·차분 배열·펜윅 트리·단조 덱 중 하나를 고릅니다.

배열의 한 구간에 대해 합·최솟값·최댓값을 묻거나, 한 구간의 값을 한꺼번에 더하는 질의는 코딩 테스트에서 자주 나옵니다. 입력이 커지면 단순 반복으로는 제한 시간을 넘기므로, 전처리와 자료구조로 질의 비용을 줄여야 합니다. 갱신이 있는지, 질의가 합인지 최대·최소인지가 선택의 두 축입니다.

구간 질의에서 시간이 터지는 곳

질의마다 구간 전체를 다시 훑으면 한 번에 $O(N)$ 이 듭니다. 질의가 $Q$ 개면 전체는 $O(NQ)$ 가 되고, 입력이 커질수록 빠르게 한계에 부딪힙니다. $N$ 과 $Q$ 가 각각 $10^5$ ~ $5 \times 10^5$ 규모면 이 방식은 통과하기 어렵습니다.

대략적인 기준으로, 1초 안에 처리 가능한 연산은 $10^8$ 안팎입니다(추정, 언어·채점기에 따라 다름). $N = 5 \times 10^5$ 에서 $O(NQ)$ 는 $10^{11}$ 을 넘어 시간 초과로 이어집니다. 따라서 질의를 $O(1)$ 이나 $O(\log N)$ 으로 줄이는 전처리가 필요합니다.

핵심 질문은 두 가지입니다. 첫째, 값이 중간에 바뀌는지(갱신 여부)입니다. 둘째, 질의가 구간 합인지 구간 최대·최소인지입니다. 이 둘의 조합이 자료구조를 결정합니다.

갱신 여부로 갈리는 선택 기준

아래 표는 상황별로 어떤 방법이 맞는지를 정리한 것입니다. 갱신이 없으면 전처리형, 갱신이 있으면 트리형, 윈도우 최대·최소는 단조 덱이 기본입니다.

상황	추천 방법	복잡도
갱신 없음, 구간 합 질의 많음	누적합(Prefix Sum)	전처리 $O(N)$ , 질의 $O(1)$
구간 업데이트 많고 최종 값만 필요	차분 배열(Difference Array)	업데이트 $O(1)$ , 복원 $O(N)$
질의·갱신 모두 많음	세그먼트 트리(Segment Tree)	질의·갱신 $O(\log N)$
합 질의 + 점 갱신 위주	펜윅 트리(Fenwick Tree, BIT)	질의·갱신 $O(\log N)$
윈도우 최대·최소	단조 덱(Monotonic Deque)	전체 $O(N)$

표를 결정 흐름으로 옮기면 다음과 같습니다. 먼저 갱신 유무를 보고, 갱신이 있으면 질의가 합인지 최대·최소인지로 다시 나눕니다.

위 분기에서 누적합과 차분 배열은 한 번 전처리해 두면 질의가 가볍습니다. 반면 값이 자주 바뀌면 트리 계열이 필요합니다.

누적합과 차분 배열

갱신이 없고 구간 합을 여러 번 묻는다면 누적합이 가장 단순합니다. 누적합(Prefix Sum)은 0번부터 $i$ 번까지의 합을 미리 저장해 두는 배열입니다. 구간 $[l, r]$ 의 합은 두 누적값의 뺄셈으로 $O(1)$ 에 구합니다.

python

def build_prefix(arr):
    pre = [0] * (len(arr) + 1)
    for i in range(1, len(arr) + 1):
        pre[i] = pre[i - 1] + arr[i - 1]
    return pre
 
def range_sum(pre, l, r):  # 1-indexed, [l, r] 포함
    return pre[r] - pre[l - 1]
 
arr = [3, 1, 4, 1, 5, 9, 2, 6]
pre = build_prefix(arr)
print(range_sum(pre, 2, 5))  # 1 + 4 + 1 + 5 = 11

여기서 pre[i]는 원소 1번부터 $i$ 번까지의 합입니다. 1-indexed로 두면 range_sum에서 l - 1이 0까지 안전하게 내려가, 첫 원소를 포함하는 질의도 예외 없이 처리됩니다.

반대 상황도 있습니다. 여러 구간에 값을 더하는 갱신이 많고, 모든 갱신이 끝난 뒤의 최종 배열만 필요할 때입니다. 이때는 차분 배열(Difference Array)이 맞습니다. 구간 $[l, r]$ 에 $v$ 를 더하는 일을 양 끝 두 칸만 건드려 $O(1)$ 에 기록한 뒤, 마지막에 한 번만 누적합으로 복원합니다.

python

def range_update(diff, l, r, val):  # [l, r]에 val 더하기, 1-indexed
    diff[l] += val
    diff[r + 1] -= val
 
def restore(diff, n):
    out = [0] * (n + 1)
    for i in range(1, n + 1):
        out[i] = out[i - 1] + diff[i]
    return out[1:]
 
n = 6
diff = [0] * (n + 2)        # r+1 접근을 위해 여유 한 칸
range_update(diff, 2, 4, 10)
range_update(diff, 3, 6, 5)
print(restore(diff, n))     # [0, 10, 15, 15, 5, 5]

diff[l] += val은 $l$ 번부터 값이 $v$ 만큼 올라간다는 표시이고, diff[r + 1] -= val은 $r$ 다음부터 그 효과를 되돌린다는 표시입니다. 복원 단계의 누적합이 이 두 표시를 펼쳐 실제 구간 덧셈으로 바꿉니다. 갱신 $Q$ 번과 복원 1번을 합쳐 전체 $O(N + Q)$ 에 끝납니다.

점 갱신과 구간 질의가 함께 올 때

값이 자주 바뀌면서 구간 합도 자주 물으면 전처리형으로는 부족합니다. 누적합은 원소 하나만 바뀌어도 그 뒤를 모두 다시 계산해야 하므로 갱신이 $O(N)$ 입니다. 이 조합에서는 펜윅 트리나 세그먼트 트리를 씁니다.

펜윅 트리(Fenwick Tree)는 이진 인덱스 트리(Binary Indexed Tree, BIT)라고도 부르며, 점 갱신과 구간 합을 모두 $O(\log N)$ 에 처리합니다. 인덱스의 최하위 비트(i & -i)를 따라 부분합을 쪼개 저장하는 구조입니다.

python

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # 1-indexed
 
    def update(self, i, delta):     # i번에 delta 더하기
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
 
    def prefix(self, i):            # 1..i 합
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l - 1)
 
ft = Fenwick(8)
for idx, v in enumerate([3, 1, 4, 1, 5, 9, 2, 6], start=1):
    ft.update(idx, v)
print(ft.range_sum(2, 5))   # 11
ft.update(3, 10)            # 3번 원소 4 -> 14
print(ft.range_sum(2, 5))   # 21

i += i & -i는 갱신할 때 영향받는 상위 구간으로 올라가는 이동이고, i -= i & -i는 부분합을 모을 때 다음 구간으로 내려가는 이동입니다. 두 연산 모두 비트가 하나씩 줄거나 늘어 $O(\log N)$ 번만 반복됩니다. 펜윅 트리는 코드가 짧아 합 질의 + 점 갱신 문제에서 먼저 떠올릴 선택지입니다.

질의와 갱신이 모두 구간 단위면 세그먼트 트리가 필요합니다. 세그먼트 트리(Segment Tree)는 구간을 반씩 쪼갠 이진 트리로, 구간 합·최솟값·최댓값 같은 질의를 $O(\log N)$ 에 답합니다. 구간 전체에 같은 값을 더하는 갱신까지 빠르게 하려면 갱신을 자식에게 미뤄 두는 지연 전파(Lazy Propagation)를 얹습니다.

윈도우 최대·최소는 단조 덱으로

고정 길이 윈도우가 한 칸씩 이동하며 최댓값이나 최솟값을 묻는 문제는 따로 다룹니다. 매번 윈도우를 다시 훑으면 $O(NK)$ 가 되지만, 단조 덱(Monotonic Deque)을 쓰면 전체 $O(N)$ 에 끝납니다. 덱에 값을 내림차순으로 유지하면 맨 앞이 항상 현재 윈도우의 최댓값입니다.

python

from collections import deque
 
def sliding_max(a, k):
    dq = deque()      # 인덱스 저장, 대응 값은 내림차순 유지
    out = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()                 # 더 작은 값은 최댓값이 될 수 없음
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()             # 윈도우를 벗어난 인덱스 제거
        if i >= k - 1:
            out.append(a[dq[0]])
    return out
 
print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

새 값이 들어올 때 자기보다 작은 뒤쪽 값들을 먼저 버리는 것이 핵심입니다. 그 값들은 새 값이 윈도우에 남아 있는 동안 최댓값 후보가 될 수 없기 때문입니다. 각 인덱스는 덱에 한 번 들어가고 한 번 나오므로 전체 연산이 $O(N)$ 에 머뭅니다.

자주 하는 실수

구현은 작은 인덱스 실수에서 자주 무너집니다. 아래는 구간 처리에서 반복되는 함정입니다.

누적합에서 0-index와 1-index를 섞어 구간 경계가 한 칸씩 어긋남
차분 배열 갱신에서 r + 1 칸의 경계 체크를 빠뜨려 배열 범위를 벗어남
펜윅 트리를 0-index로 구현해 i & -i 이동 로직이 꼬임
세그먼트 트리가 필요한 갱신 문제를 누적합으로 풀어 갱신마다 $O(N)$ 으로 시간 초과

이 실수들은 대부분 인덱스 기준을 코드 전체에서 하나로 통일하면 줄어듭니다. 1-index 기준으로 누적합·차분 배열·펜윅 트리를 함께 쓰면 경계 계산이 일관됩니다. 제출 전에 길이 1짜리 구간과 배열 양 끝 구간을 반례로 한 번 더 확인하면 좋습니다.

정리

구간 처리 문제는 두 질문으로 자료구조가 거의 정해집니다. 값이 바뀌지 않으면 누적합과 차분 배열로 전처리해 질의를 $O(1)$ 이나 $O(N + Q)$ 에 끝냅니다. 값이 바뀌면 합 + 점 갱신은 펜윅 트리, 구간 갱신 + 구간 질의는 세그먼트 트리로 $O(\log N)$ 을 확보합니다. 고정 길이 윈도우의 최대·최소만큼은 단조 덱으로 $O(N)$ 에 처리합니다. 복잡도는 표준 알고리즘 분석 기준이며, 실제 통과 여부는 백준 온라인 저지(BOJ) 11659·2042·10999·11003 같은 문제로 직접 제출해 확인합니다.