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 的数组 a (\(1 <= n <= 2 \cdot 10^6\ ), \(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 5
1
5 5
 5