[1. 개요]
배열에 대한 제곱근 분할법이란
배열을 길이의 제곱근 단위로 나누어 구간에 대한 쿼리를 처리하는 것이다.
즉, 오프라인 쿼리 처리에서 매우 유용하지만, 수정이 불가능한다는 단점이 있다.
[2. 상세]
배열의 특정 구간에 대해 최대값, 최소값 등을 계산해야 한다고 할 때,
세그먼트 트리 등을 이용해 처리할 수 도 있지만,
배열을 특정한 크기로 묶어서(이하 블록) 아래와 같이 처리 할 수 있다.
- 쿼리 구간 [L, R] 이 블록 들에 interleave 한 경우
- 쿼리 구간 [L, R] 이 전체 블록을 포함 하는 경우
전체 배열의 길이를 N , 블록의 크기를 K 라 할 때,
1번 경우는 아래와 같다.
- L 이 왼쪽 블록에 포함되고
- R 이 오른쪽 블록에 포함 됨.
- 이 경우, 쿼리의 시간복잡도는 2K
2번 경우는 전체 구간이라고 볼 수 있다.
- 모든 블록들에 대해서 최대/최소 값을 찾도록 한다.
- 이 경우, 쿼리의 시간복잡도는 N/K
두 시간복잡도를 더하면 T(K) = 2K + N/K , 이 수식의 최소 값이 곧 적절한 K 가 된다.
K = sqrt(N) 이 되어, (상수는 무시하고)
배열을 N 의 제곱근으로 나누는 것이다.
[3. 예제]
'알고리즘 > 이론' 카테고리의 다른 글
| 차분 배열 (0) | 2025.05.21 |
|---|---|
| radix tree (0) | 2025.05.17 |
| 라빈-카프 알고리즘 (0) | 2025.05.17 |
| Convex hull (볼록 껍질) (0) | 2025.01.02 |
| 네트워크 유량, Dinic 알고리즘 (0) | 2024.12.26 |