能否在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}

e.g.

{ 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

- Micro Optimizer

Answer 1

尽管你无法在线性时间内产生O(n²)数量的数据，但你可以在线性时间内构建一个数据结构，使你能够在O(1)时间内计算出每个f(x,y)。

为此，你需要构建一个数组s，其中s_i表示从0到i（包括两端）的a的和。

你可以通过设置s[0] = a[0]，然后对于每个大于零的i设置s[i] = s[i-1] + a[i]来构建一个部分和数组。

有了部分和数组，你就可以计算出每个f(x,y)。

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

- Sergey Kalinichenko

---

这可以在不使用任何辅助数据结构的情况下完成。 - A. Mashreghi

@A.Mashreghi 这要看你所说的“这”具体指什么。 - Sergey Kalinichenko