是否有可能在O(n)时间内得到所有连续子阵列的总和？

Question

作为我正在解决的一个更大问题的一部分,我很好奇是否可以在线性时间内完成

{a_0, a_1, ..., a_n-1}

生成映射

f(i,j): sum of elements over range [i,j) for all i,j in {0, 1, ..., n - 1}

例如

{ 5, 1, 89, 0 }

----> 

f(0,1) = 5
f(0,2) = 5 + 1 = 6
f(0,3) = 5 + 1 + 89 = 95
f(0,4) = 5 + 1 + 89 + 0 = 95
f(1,2) = 1
f(1,3) = 1 + 89 = 90
f(1,4) = 1 + 89 + 0 = 90
f(2,3) = 89
f(2,4) = 89 + 0 = 89
f(3,4) = 0

Answer 1

虽然您无法在线性时间内生成O(n ²)数据量,但您可以在线性时间内构建数据结构,以便计算f(x,y)O(1)中的每一个.

为此,您需要构建一个数组s,使得s _i表示a从零到i包括两端的总和.

您可以通过设置s[0] = a[0]然后设置s[i] = s[i-1] + a[i]每个i零以上来构建一个部分和数组.

拥有一个部分和数组可以让你计算

f(x,y) = s[y] - (x==0 ? 0 : s[x-1])