作为我正在解决的一个更大问题的一部分，我很好奇在线性时间内是否有可能
{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
最佳答案
虽然不能在线性时间内生成O（n2）数量的数据，但可以在线性时间内构建一个数据结构，以便计算O（1）中的每个f(x,y)。
为此，您需要构建一个数组s，使si表示从零到a的总和，包括两端。
您可以通过设置i来构建一个部分和数组，然后将每个s[0] = a[0]的s[i] = s[i-1] + a[i]设置为大于零。
使用部分和数组可以计算
f(x,y) = s[y] - (x==0 ? 0 : s[x-1])
关于algorithm - 是否有可能在O(n)时间内获得所有连续子数组的总和？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40311407/