查找任意子数组中所有项目之和的最佳算法是什么

Question

我有一个问题，还有一个不错的解决方案。我希望有更好的解决方案。

问题

我有一个包含大约 200,000 个整数的数组。给定两个索引 i1 和 i2，我需要计算 i1 和 i2 之间所有元素的总和。数组中的每个整数都在 1 到 4 之间（含 1 和 4）。例如：

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

此操作将执行大约 200,000 次，因此需要非常快。 for 循环中的简单计数器是 O(n)，而且速度太慢。数组在构建后永远不会被修改，因此有一个相对昂贵的预处理阶段是可以的。

迄今为止我最好的解决方案

该算法的工作时间为 O(log n)：

首先用零填充原始数组，直到其长度为 2 的幂。接下来，将数组分成两个相等的部分并存储每个部分的总和。然后将数组分成四份并存储每份的总和。然后八分之一。继续这样做，直到数组被分成 2 个元素长的部分。对于上面的 8 元素数组，这需要两个步骤：

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

然后给定两个索引，现在可以在 O(log n) 时间内计算出 subsection_sum。例如，subsection_sum(a, 2, 7) ==quarters[1] + half[1]。

Answer 1

引入一个包含累积和的辅助数组。也就是说，辅助数组的元素 i 具有原始数组的元素 0 到 i 的总和。那么子数组的和就是辅助数组中两个元素的差。这将在常数时间内给出结果，O(1)。

这取决于问题中给出的 subsection_sum 函数的不变量：

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2)

我假设 i1 <= i2。重新排列，我们有：

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)

请注意，右侧的总和都是从 0 开始的。辅助数组可以被视为缓存所有 i 的从零开始的总和值，subsection_sum(a, 0, i)。

Answer 2

如果您可以负担 O(n) 额外存储空间，则可以创建一个查找表，其第 i 个元素是索引 0 处元素的总和> 到输入数组中的 i （包含）。在伪代码中：

def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i] + lookupTable[i-1]

    return lookupTable

然后您可以使用此表来计算 i1 和 i2 之间的 array 中所有元素的总和，方法是采用

lookupTable[i2] - lookupTable[i1]

常量的 差值时间。