复杂度为 O(1) 的一系列索引中的求和值

Question

我们得到一个整数向量（V[]）和两个索引值，A 和 B。我们需要对 V[A] 和 V[B] 之间的所有整数求和。

例如，

V[] == {0, 1, 2, 0, 4, 0, 3}, A == 2, B == 6
Sum == V[3] + V[4] + V[5] == 4

是否可以解决 O(1) 的复杂性？我考虑过使用内存地址操作，但我仍然不确定它是如何工作的（类似于：对 &V[A] 中的下一个 (B-A) 地址值求和）

Answer 1

O(1) Space：没问题。但是 "random" 个数字总是需要 O(n) 时间。

Answer 2

如果允许预处理，这可以用辅助阵列完成。

第二个数组的每个元素将包含相应元素和所有前面元素的总和。这个一次性预处理是O(n)次，O(n)space.

例如：

int Vsum[7];
Vsum[0] = V[0];
for (int i=1; i<7; i++) {
    Vsum[i] = Vsum[i-1] + V[i];
}

因此对于给定的数组，相应的求和数组 Vsum 将包含：

{0, 1, 3, 3, 7, 7, 10}

有了这个之后，您只需执行 2 次查找：一次查找上限，一次查找下限。所以经过预处理，每次执行得到范围和都是O(1)。

对于 A==2 和 B==6 的示例，您将计算 Vsum[B-1] - Vsum[A] == 7 - 3 == 4

sum values in a range of indices with O(1) complexity