找到任意子数组中所有项的总和的最佳算法是什么

Question

我有一个问题,一个OK-ish解决方案.我希望那里有更好的解决方案.

问题

我有一个大约200,000个整数的数组.给定两个索引i1和i2,我需要计算i1和i2之间所有元素的总和.数组中的每个整数都介于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] + halfves [1].

Answer 1

引入包含累积和的辅助数组.也就是说,i辅助阵列的元素i具有原始数组的元素0到的总和.然后,子阵列总和只是辅助阵列中两个元素的差异.这将在恒定的时间内给出结果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.subsection_sum(a, 0, i)对于所有人来说,辅助数组可以被视为缓存来自零的和的值i.