평방 분할(구간 질의) 계산기

배열을 크기 b짜리 버킷으로 잘라 버킷마다 요약값(합·최솟값 등)을 미리 구해 두는 방법입니다. 구간 질의가 「왼쪽 자투리 + 통째로 들어가는 버킷들 + 오른쪽 자투리」로 나뉘어, 자투리는 최대 2b개를 하나씩 보고 가운데는 버킷 요약값 최대 n/b개만 읽습니다.

질의 비용이 대략 2b + n/b인데, 이것을 b로 미분해 0으로 두면 b = √(n/2)가 나오기 때문입니다. 그때 비용이 2√(2n)이라 O(√n)이 됩니다. b가 작으면 버킷 개수가 많아지고 크면 자투리가 길어져 양쪽으로 다 손해라, 연산 횟수가 U자 곡선을 그립니다.

구현이 훨씬 짧고, 합치기 어려운 연산에도 붙기 때문입니다. 세그먼트 트리는 두 구간의 답을 합쳐 큰 구간의 답을 만들 수 있어야 하는데 최빈값이나 「서로 다른 값의 개수」는 그것이 안 됩니다. 평방 분할은 버킷마다 통계를 통째로 들고 있으면 되므로 그런 연산도 다룰 수 있습니다.

연산에 따라 다릅니다. 합처럼 되돌릴 수 있으면 원소를 고치고 버킷 요약값에서 옛 값을 빼고 새 값을 더하면 되어 O(1)입니다. 최솟값·최댓값은 지운 값이 그 버킷의 최솟값이었으면 다음 최솟값을 알 길이 없어 버킷을 다시 훑어야 하므로 O(b)입니다.

됩니다. 이 점이 차분 배열과 다릅니다. 차분 배열은 갱신을 전부 받고 마지막에 한 번 읽는 경우에만 이기지만, 평방 분할은 버킷 요약값을 그때그때 고칠 수 있어 질의와 갱신이 섞여 들어와도 각각 O(√n) 안팎으로 처리합니다.

요약값을 쓸 수 없어 원소를 하나씩 봅니다. 이때 비용이 최대 b라 전체 최악값에는 영향을 주지 않지만, 구현에서 이 경우를 따로 처리하지 않으면 왼쪽 자투리와 오른쪽 자투리가 겹쳐 같은 원소를 두 번 세게 됩니다. 이 도구는 그 경우를 나눠 처리합니다.

경진 프로그래밍에서 구간 질의를 빠르게 짜야 할 때, 특히 세그먼트 트리로 표현하기 어려운 연산일 때 씁니다. Mo's 알고리즘처럼 질의를 미리 다 받아 정렬하는 기법도 같은 √n 발상 위에 서 있고, 데이터베이스의 블록 단위 통계(존 맵)도 본질적으로 같은 구조입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.