Ch 9. 구간 쿼리 (Range Queries)

← 수업 목록

Ch 9. 구간 쿼리 (Range Queries)

수업 목표

본 수업은 다양한 구간 질의(Range Queries) 문제들의 특성에 따라 알맞은 자료구조를 선택하고 효율적으로 구현하는 것을 목표로 합니다. - 정적 배열에서의 고속 구간 질의와 동적 배열에서의 실시간 원소 갱신 및 질의 처리 방식의 차이를 이해합니다. - 누적 합, 스파스 테이블, 펜윅 트리, 세그먼트 트리 자료구조의 시간 복잡도와 설계 목적을 비교 학습합니다. - 구간 업데이트 및 구간 합 구하기 문제를 효율적으로 설계하고 최적화할 수 있는 역량을 기릅니다.

학습 동기부여

대규모 데이터 분석이나 실시간 데이터 스트리밍 서비스에서는 특정 구간의 합이나 최솟값을 구해야 하는 요구사항이 빈번하게 발생합니다. 매번 전체 구간을 탐색하면 $O(N)$의 시간이 소요되지만, 적절한 자료구조와 전처리를 도입하면 이를 $O(1)$ 또는 $O(\log N)$으로 획기적으로 줄일 수 있습니다. 이러한 구간 쿼리는 알고리즘의 성능 병목 현상을 해결하는 결정적인 도구입니다.

도입 스토리

매일의 매출 기록이 적힌 장부를 펼치고 특정 날짜 범위의 총매출을 바로 구하고 싶을 때, 첫날부터 매출을 누적으로 더한 합산 장부(누적 합)를 한 권 더 적어두면 두 번의 뺄셈만으로 원하는 구간의 매출 합을 바로 찾을 수 있습니다. 그러나 매출이 실시간으로 수정된다면 어떻게 해야 할까요? 매번 누적 장부를 다시 쓰기는 비효율적이므로, 각 구역의 책임을 나눈 분할 장부(펜윅 트리와 세그먼트 트리)를 운영하는 편이 훨씬 영리합니다. 본 수업에서는 상황에 부합하는 장부 작성 방식을 학습합니다.

1. 누적 합 (Prefix Sum)

정적 배열에서 $O(N)$ 전처리로 누적 합 배열을 구성하면, 임의의 구간 $[l, r]$의 합을 $O(1)$에 구할 수 있습니다. 배열 원소의 변경이 없을 때 가장 간단하고 강력한 기법입니다.

# 8049번: 구간 합 쿼리 — O(1) 구간 합 질의
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
arr = list(map(int, input().split()))

# 누적합 배열 구성 (1-based)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
    prefix[i] = prefix[i - 1] + arr[i - 1]

for _ in range(q):
    l, r = map(int, input().split())
    # l번째부터 r번째까지의 구간 합 계산
    print(prefix[r] - prefix[l - 1])

2. 스파스 테이블 (Sparse Table)

정적 배열에서 구간 최솟값(RMQ)과 같이 결합 법칙이 성립하고 중복 계산이 무관한 쿼리를 $O(N \log N)$ 전처리 후 $O(1)$에 해결하는 테이블입니다. 구간을 2의 거듭제곱 크기로 분할하여 최솟값을 미리 구한 뒤 질의를 처리합니다.

# 8050번: 구간 최솟값 쿼리 — O(1) 구간 최솟값 질의
import sys
import math
input = sys.stdin.readline

n, q = map(int, input().split())
arr = list(map(int, input().split()))

# 스파스 테이블 구성
log_n = int(math.log2(n)) + 1
sparse = [[0] * n for _ in range(log_n)]

# k = 0 레이어 초기화
for i in range(n):
    sparse[0][i] = arr[i]

# 테이블 채우기
for k in range(1, log_n):
    for i in range(n - (1 << k) + 1):
        sparse[k][i] = min(sparse[k - 1][i], sparse[k - 1][i + (1 << (k - 1))])

for _ in range(q):
    l, r = map(int, input().split())
    # 0-based 인덱스로 변환
    l_idx = l - 1
    r_idx = r - 1
    length = r_idx - l_idx + 1
    k = int(math.log2(length))
    
    # 겹치는 두 구간의 최솟값 비교를 통한 O(1) 연산
    ans = min(sparse[k][l_idx], sparse[k][r_idx - (1 << k) + 1])
    print(ans)

3. 펜윅 트리 (Fenwick Tree / BIT)

동적 배열에서 원소의 변경과 구간 합 쿼리를 $O(\log N)$에 동시에 수행하는 경량 자료구조입니다. 각 인덱스가 담당하는 구간을 비트의 하위 1비트(LSB) 크기만큼 지정하여 메모리와 연산을 최적화합니다.

# 8051번: 구간 합 업데이트 — O(log N) 점 갱신 및 구간 합
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
arr = list(map(int, input().split()))

bit = [0] * (n + 1)

def update(i, diff):
    while i <= n:
        bit[i] += diff
        i += i & (-i)

def query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s

# 초기 트리 빌드
for i in range(1, n + 1):
    update(i, arr[i - 1])

for _ in range(q):
    type_q, a, b = map(int, input().split())
    if type_q == 1:
        # a번째 원소에 b를 더함
        update(a, b)
    else:
        # a번째부터 b번째까지의 합 출력
        print(query(b) - query(a - 1))

4. 세그먼트 트리와 레이지 프로파게이션 (Segment Tree & Lazy Propagation)

구간 업데이트와 구간 합 질의를 모두 $O(\log N)$에 처리하는 트리 형태의 자료구조입니다. 레이지 기법을 통해 실제 하위 노드 값이 필요한 시점까지 업데이트 전파를 지연시킵니다. 여기서는 펜윅 트리 2개를 이용한 구간 갱신-구간 합 구현 코드를 소개합니다.

# 8052번: 구간 합 + 구간 업데이트 — 듀얼 BIT를 이용한 고속 구간 관리
import sys
input = sys.stdin.readline

n, q = map(int, input().split())

# 2개의 BIT를 사용하여 구간 갱신 및 구간 합 계산
bit1 = [0] * (n + 2)
bit2 = [0] * (n + 2)

def bit_add(bit, i, val):
    while i <= n:
        bit[i] += val
        i += i & (-i)

def bit_query(bit, i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s

def range_add(l, r, v):
    bit_add(bit1, l, v)
    bit_add(bit1, r + 1, -v)
    bit_add(bit2, l, v * (l - 1))
    bit_add(bit2, r + 1, -v * r)

def prefix_sum(i):
    return bit_query(bit1, i) * i - bit_query(bit2, i)

def range_sum(l, r):
    return prefix_sum(r) - prefix_sum(l - 1)

for _ in range(q):
    line = list(map(int, input().split()))
    if line[0] == 1:
        l, r, v = line[1], line[2], line[3]
        range_add(l, r, v)
    else:
        l, r = line[1], line[2]
        print(range_sum(l, r))

자주 하는 실수 & 오류 예방

- 인덱스 기준점 혼동: 펜윅 트리와 세그먼트 트리는 내부 연산의 편리함을 위해 보통 1-based 인덱스를 사용합니다. 0-based 입력과의 변환 시 오프셋 실수를 방지하십시오. - 펜윅 트리 0번 인덱스 무한 루프: 펜윅 트리 연산 도중 i += i & (-i) 또는 i -= i & (-i) 연산을 할 때, i가 0이 되면 값이 변하지 않고 무한 루프에 빠집니다. 절대 0번 인덱스를 갱신하거나 참조하지 않도록 유의하십시오. - 구간 연산 오버플로우: 구간 합 계산 시 누적되는 값이나 원소의 크기가 $10^9$을 상회할 때 정수 오버플로우가 나지 않도록 유의하십시오. 파이썬은 대형 정수를 지원하지만 속도가 다소 느려질 수 있습니다.

핵심 정리

자료구조	전처리 복잡도	구간 합 질의 복잡도	값 갱신(Update) 복잡도	비고 (갱신 가능 형태)
누적 합 (Prefix Sum)	$O(N)$	$O(1)$	지원 안 함	원소 변경이 없는 정적 데이터 최적
스파스 테이블 (Sparse Table)	$O(N \log N)$	$O(1)$ (결합 법칙 RMQ)	지원 안 함	최솟값/최댓값 등 중복 연산 무관 쿼리 최적
펜윅 트리 (BIT)	$O(N)$	$O(\log N)$	$O(\log N)$	점 갱신 및 구간 합 처리에 매우 경제적
세그먼트 트리 (Lazy Segment Tree)	$O(N)$	$O(\log N)$	$O(\log N)$ (구간 갱신)	구간 갱신과 다양한 구간 연산(합, 최소, 최대 등) 완벽 지원

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8049	구간 합 쿼리	CSES	쉬움	누적 합 (Prefix Sum)
8050	구간 최솟값 쿼리	CSES	보통	스파스 테이블 (Sparse Table)
8051	구간 합 업데이트	CSES	보통	펜윅 트리 (Fenwick Tree)
8052	구간 합 + 구간 업데이트	CSES	어려움	세그먼트 트리 & 레이지 프로파게이션