algorithm - 是否有可能在 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])