길이를 두 배씩 늘리기
길이 1인 구간의 답은 배열의 각 원소다. 길이 2, 4, 8인 구간의 답은 바로 아래 단계의 두 구간을 결합해 만든다. 최솟값이라면 두 절반의 최솟값 중 작은 값을 저장한다. 가능한 시작 위치에 대해 이 결과를 만들어 질의에 재사용한다.
두 구간으로 최솟값 구하기
질의 구간 길이가 L이면 2ᵏ≤L인 가장 큰 k를 선택한다. 구간의 왼쪽 끝에서 시작하는 길이 2ᵏ 구간과 오른쪽 끝에서 끝나는 같은 길이 구간을 고른다. 두 구간은 전체를 덮으며 겹칠 수 있다. 최솟값은 같은 원소를 두 번 고려해도 바뀌지 않으므로 두 저장값만 비교하면 된다.
합에는 같은 공식을 쓰지 않기
구간 [0,5]에는 원소가 여섯 개 있다. 길이 4인 [0,3]과 [2,5]를 사용하면 [2,3]이 겹친다. 최솟값 질의에는 문제가 없지만 두 구간의 합을 더하면 겹친 원소를 두 번 센다. 합처럼 중복이 영향을 주는 연산에는 겹치지 않는 분할이나 다른 구조가 필요하다.
변경이 잦은 배열과의 차이
일반적인 희소 테이블은 O(n log n)의 전처리와 저장 공간을 사용한다. 정적인 배열의 최솟값 질의는 O(1)이지만 값 변경을 빠르게 지원하는 것이 주목적은 아니다. 같은 배열에서 질의가 반복되는지와 갱신이 필요한지를 살펴 자료 구조를 선택해야 한다.