블록의 요약값
길이 n인 배열을 크기 B인 연속한 블록들로 나눈다. 마지막 블록은 더 짧을 수 있다. 합을 관리한다면 각 블록의 원소 합을 별도로 저장한다. 이렇게 하면 여러 블록 전체를 합할 때 블록 안의 원소를 매번 하나씩 읽지 않아도 된다.
중간 블록과 양 끝
질의 구간에 완전히 들어가는 블록은 저장된 합을 이용한다. 양 끝에서 일부만 들어가는 블록은 포함된 원소를 직접 더한다. 예를 들어 블록이 [0,3], [4,7], [8,11]이면 구간 [2,9]의 합은 2번과 3번, 가운데 블록의 합, 8번과 9번 원소를 결합해 구한다.
왜 제곱근인가
양 끝에서 직접 읽는 원소 수는 O(B)이고 전체 블록 수는 O(n/B)다. 따라서 질의 비용은 O(B+n/B)로 표현할 수 있다. 두 항을 비슷하게 만드는 B를 √n 정도로 정하면 O(√n)이 된다. 실제 최적 블록 크기는 연산 종류와 구현 상수에도 영향을 받는다.
값 변경과 연산의 차이
합을 저장한 경우 원소 하나가 Δ만큼 바뀌면 해당 블록 합에 Δ를 반영하면 된다. 그러나 최솟값을 저장한 블록에서 기존 최솟값이 커졌다면 블록 내부를 다시 살펴야 할 수 있다. 같은 블록 분할이라도 요약 정보의 종류에 따라 질의와 갱신 비용이 달라진다.