O(n) 미만 점근법에서 정적 배열 a의 간격 l...r에 대한 합계를 빠르게 계산하는 방법에 대한 문제가 있습니다.
배열 a를 같은 크기의 k개 블록으로 나누고 먼저 각각에 대한 요소의 합을 계산해 봅시다.
이제 요청에 응답할 때 배열 a의 요소를 살펴보고 결과에 추가할 수 있습니다. 또한 블록 중 하나가 세그먼트 내부에 있는 경우 해당 합계를 결과에 추가하고 이 블록의 요소입니다.
이 알고리즘의 쿼리당 최대 작업 수는 n / k + k이므로 최적의 k는 n의 제곱근과 같습니다.