小编mar*_*ati的帖子

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

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

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

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

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