---
title: "희소 테이블: 바뀌지 않는 구간 질의를 미리 준비하기"
author: "Lee"
published_at: "2026-10-23T00:16:04.150Z"
updated_at: "2026-09-30T09:51:50.486Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%ED%9D%AC%EC%86%8C-%ED%85%8C%EC%9D%B4%EB%B8%94-%EB%B0%94%EB%80%8C%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B5%AC%EA%B0%84-%EC%A7%88%EC%9D%98%EB%A5%BC-%EB%AF%B8%EB%A6%AC-%EC%A4%80%EB%B9%84%ED%95%98%EA%B8%B0"
ai_assisted: false
---

# 희소 테이블: 바뀌지 않는 구간 질의를 미리 준비하기

[원문](https://ariser.io/@writer_a1cd615ab19e/%ED%9D%AC%EC%86%8C-%ED%85%8C%EC%9D%B4%EB%B8%94-%EB%B0%94%EB%80%8C%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B5%AC%EA%B0%84-%EC%A7%88%EC%9D%98%EB%A5%BC-%EB%AF%B8%EB%A6%AC-%EC%A4%80%EB%B9%84%ED%95%98%EA%B8%B0)

희소 테이블은 배열의 2⁰,2¹,2² 길이 구간 결과를 미리 계산해 여러 구간 질의에 사용하는 자료구조다. 원본 값이 자주 바뀌지 않는 정적 데이터에 적합하다. 최솟값 질의에서는 전처리 후 O(1) 응답이 가능하다.

![인덱스 1부터 3의 최솟값을 겹치는 두 길이 2 블록으로 구하는 희소 테이블](/api/v1/media/6a54e3a7-6c92-4b58-8a00-3173bdd82986)

*최솟값처럼 중복 적용해도 결과가 같은 연산은 겹치는 블록을 사용할 수 있다.*

### 두 작은 구간으로 큰 구간 만들기

table[k][i]를 i에서 시작하는 길이 2ᵏ 구간의 최솟값이라고 하자. 길이 2ᵏ 구간은 앞 절반과 뒤 절반으로 나뉘므로 이전 행의 두 결과 중 작은 값으로 채운다. 시작 위치마다 범위가 배열 밖으로 나가지 않아야 한다.

```python
import math

def build_sparse_min(values):
    table = [list(values)]
    length = 2
    while length <= len(values):
        half = length // 2
        previous = table[-1]
        row = [min(previous[i], previous[i + half])
               for i in range(len(values) - length + 1)]
        table.append(row)
        length *= 2
    return table

def minimum(table, left, right):
    # Nonempty half-open interval [left, right).
    power = (right - left).bit_length() - 1
    block_length = 1 << power
    return min(table[power][left], table[power][right - block_length])
```

power는 질의 길이 이하의 가장 큰 2의 거듭제곱을 고른다. 왼쪽에서 시작한 구간과 오른쪽에서 끝나는 같은 길이 구간은 전체를 덮는다. 둘이 겹칠 수 있지만 최솟값에서는 문제가 없다. 빈 구간은 bit_length 규칙에 맞지 않아 별도로 처리해야 한다.

### 멱등성이 O(1) 질의를 가능하게 한다

길이 6 구간을 길이 4 구간 두 개로 덮으면 가운데 두 원소가 겹친다. min(x,x)=x이므로 같은 값을 두 번 포함해도 결과가 달라지지 않는다. 이런 성질을 멱등성이라고 한다. 최댓값, AND, OR, 최대공약수도 적합한 예다.

합은 다르다. 두 겹치는 구간 합을 더하면 중간 원소를 중복 계산한다. 일반 희소 테이블에서 겹치지 않는 2의 거듭제곱 구간으로 분해하면 O(log n) 집계가 가능하고, 합에는 누적합이 더 간단하다. 모든 결합 연산이 O(1) 질의를 얻는 것은 아니다.

전처리 시간과 공간은 O(n log n), 최솟값 질의는 O(1)이다. 원소 한 개가 바뀌면 여러 행의 많은 구간이 영향을 받아 갱신이 효율적이지 않다. 동적 데이터에는 다른 구조를 고려해야 한다.

나무의 최소 공통 조상을 오일러 순회와 깊이의 구간 최솟값 문제로 바꾸는 응용도 있다. 이 경우도 변환의 의미와 질의 조건을 별도로 확인한다.

희소 테이블은 큰 전처리 비용을 많은 읽기 질의에 나누어 쓰는 선택이다. 데이터가 고정적인지, 집계 연산이 멱등적인지, 충분한 메모리가 있는지 확인하면 왜 빠른지와 언제 부적합한지 함께 이해할 수 있다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)