如何从给定的指数区间(i,j)中求出常数时间内元素的和?

如果你能花O(n)时间“准备”辅助信息,根据这些信息你就能计算出O(1)中的和,你就可以很容易地做到。

制备(O(N)):

aux[0] = 0;
foreach i in (1..LENGTH) {
  aux[i] = aux[i-1] + arr[i];
}

查询(o(1)), arr 是从 1 到 LENGTH :

sum(i,j) = aux[j] - aux[i-1];

我认为这是目的,因为,否则,这是不可能的:对于任何 length 计算 sum(0,length-1) 你应该扫描整个阵列;这至少需要线性时间。

它不能在固定的时间内完成,除非你 商店 信息。

您需要做一些类似于特别修改数组的操作,以便为每个索引存储数组开头和该索引之间的所有值的和,然后对范围使用减法来获得和的差。

但是,代码示例中似乎没有允许这样做。数组是由用户创建的(可以随时更改),您无法控制它。

任何需要扫描顺序未排序列表中一组元素的算法都是o(n)。

以前的答案对所问的问题来说是绝对正确的。我只是补充一点,如果这个问题有点像:

Find the sum of the interval, if the array gets changed dynamically.

如果数组元素发生更改,则必须重新计算存储在辅助数组中的任何和,如中所述@ Pavel Shved 的方法。 重新计算是o(n)操作,因此我们需要利用 Segment Tree .

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

已知的基于范围的查询有三种算法[l,r]

1.段树:总查询时间o(nlogn) 2.fenwick树:总查询时间o(nlogn) 3.MO算法(平方根分解)

前两个算法可以处理给您的列表/数组中的修改。第三个算法或MO的算法是离线算法,意味着所有的查询都需要事先给出。此算法不允许修改列表/数组。为了实现、运行和进一步阅读该算法,您可以查看 Medium 博客。它用代码解释。很少有人知道这种方法。

这个问题将解决o(n^2)时间,o(n)空间或o(n)时间,o(n)空间。

现在是这种情况下的最佳解(即o(n)时间,o(n)) 假设给定了[]={1,3,5,2,6,4,9} 如果我们创建一个数组(sum[]),在该数组中,我们将0个索引的和的值保留在该特定索引上。对于数组a[],sum数组将是sum[]={1,4,9,11,17,21,30};like {1,3+1,3+1+5……}这需要O(n)时间和O(n)空间。 当我们给出索引,然后它直接从sum数组中获取它意味着add(i,j)=sum[j]-sum[i-1];这需要o(1)次和o(1)个空格…… 所以,这个程序需要O(n)时间和O(n)空间。

int sum[]=新int[l];

    sum[0]=a[0];
    System.out.print(cumsum[0]+" ");
   for(int i=1;i<l;i++)
   {
       sum[i]=sum[i-1]+a[i];
       System.out.print(sum[i]+" ");
   }  

?*这给出了1,4,9,11,17,21,30,并取o(n)时间和o(n)空间*/

和(i,j)=和[j]-和[i-1]/ 这给出了从i到j的索引和,取o(1)时间和o(1)空间 /

所以,这个程序需要O(n)时间和O(n)空间。 强调文字