如何提高该算法的时间复杂度

Question

这是一个简单的问题:我有一个长度为N的数组,给定2个边界(a,b)的函数返回a和b之间数组中所有元素的总和.

现在,这显然是O(N)时间复杂度......但是如果我想使它更有效(如log(N)),使用存储部分和的第二个数据结构,我该如何实现它？

我在考虑二叉树,但找不到算法.当然我可以创建一个NxN矩阵,但它太多了.我想要一些不需要太多空间的东西,让我有一个对数时间复杂度; 任何的想法？

更新:我没有明确说明..但是:

1. 边界在数组的索引上,而不是值
2. 数组是动态的,值可以改变,我不希望线性复杂度来改变值!因此,部分和的简单算法不起作用,我想..
3. 没有并发编程(1个CPU)

Answer 1

好吧,您可以使用另一个相同大小的数组来存储部分总和.然后,无论何时给定边界,您都可以减去部分和,并获得该间隔中元素的总和.例如:

Elements:    1 2 3 4  5  6
Partial_Sum: 1 3 6 10 15 21

让我们说,数组从index = 0开始,你想要包含区间[1,3]中元素的总和:

// subtract 1 from the index of the second sum, because we
// want the starting element of the interval to be included.
Partial_Sum[3] - Partial_Sum[1-1] = 10 - 1 = 9