Module: 루트 분해


Problem

1 /6


세그먼트의 합계 - 1

Theory Click to read/hide

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

Problem

<사업부>

길이 n(\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). 또한 주어진 m (\(1 <= m <= 500\)) 쿼리는 l과 같습니다. r (\(1 <= l <= r <= n\)).

각 검색어에 대해 l과 r 사이의 숫자 합계를 인쇄합니다. 요소는 1에서 n로.

 

예
<헤드> <일># <몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

입력 출력
1 <사업부>4
1 2 3 4
<사업부>2
1 4
<사업부>1 1 		10
1
2
5
5 5 5 5
<사업부>1
5 5
 5