我有一个问题,以及一个还算可以的解决方案。我希望能找到更好的解决方案。
问题
我有一个包含约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(a, 2, 7) == quarters[1] + halves[1]。