스파스 테이블(구간 최솟값 질의) 계산기
갱신 없는 배열에서 구간 최솟값을 O(1)에 답합니다. 2의 거듭제곱 구간을 겹쳐 덮는 것이 핵심 아이디어입니다.
[2, 6] 구간 최솟값1
전처리(O(n log n))만 한 번 해두면 이후 어떤 구간 질의든 O(1)에 답합니다. 대신 배열이 바뀌면 다시 전처리해야 해서, 값이 자주 바뀌는 데이터에는 세그먼트 트리가 더 적합합니다.
사용 방법
- 1배열을 입력합니다.
- 2질의할 구간의 왼쪽·오른쪽 인덱스(0부터)를 정합니다.
- 3그 구간의 최솟값을 확인합니다.
자주 묻는 질문
미리 모든 2의 거듭제곱 길이(1, 2, 4, 8, …) 구간의 최솟값을 표로 만들어 둡니다. 질의가 들어오면 그 구간을 정확히 나누는 대신, 2의 거듭제곱 두 개로 겹쳐서 덮습니다 — 최솟값은 같은 원소를 두 번 세어도 결과가 바뀌지 않는 연산이라 겹쳐도 상관없습니다.
구간을 정확히 겹치지 않게 나누려면 이진수 분해처럼 여러 조각이 필요할 수 있지만(세그먼트 트리가 이 방식), 겹쳐도 되는 최솟값·최댓값·최대공약수 같은 연산이면 "그 구간을 덮는 가장 큰 2의 거듭제곱 구간 두 개"만 있으면 충분해 항상 O(1) 조회로 끝납니다.
배열 값이 바뀌지 않는다면 스파스 테이블이 더 빠릅니다(질의 O(1)). 값이 자주 바뀐다면 세그먼트 트리를 써야 합니다 — 스파스 테이블은 원소 하나만 바뀌어도 전체를 O(n log n)에 다시 만들어야 하지만, 세그먼트 트리는 갱신도 O(log n)에 됩니다.
최댓값이나 최대공약수처럼 "같은 값을 여러 번 반영해도 결과가 바뀌지 않는" 멱등연산이면 똑같은 방식으로 됩니다. 반면 합계처럼 겹치면 값이 중복 계산되는 연산에는 이 트릭을 쓸 수 없습니다.
알아두면 좋은 점
- 이 계산기는 최솟값 질의만 다룹니다. 최댓값은 같은 원리로 min을 max로 바꾸면 됩니다.
함께 보면 좋은 도구
세그먼트 트리배열을 넣으면 세그먼트 트리를 만들어 구간 질의가 어느 노드를 타고 답하는지 실제로 방문한 노드를 칠해 보입니다.펜윅 트리배열을 넣으면 펜윅 트리를 만들어 누적합 질의와 점 갱신이 타는 인덱스 사슬을 보입니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.