如何在恒定时间内从给定的索引间隔（i，j）中找到元素的总和？

一尘不染

algorithm

给定一个数组。我们如何(i, j)在恒定时间内找到索引间隔中的元素总数。允许您使用额外的空间。
示例：
A：3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1
长度= 14

int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);

固定时间之和应为10。

阅读 274

2020-07-28

共1个答案

一尘不染

如果您可以花费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) 您都应该扫描整个阵列；至少需要线性时间。

2020-07-28