找到前缀和变化的 O(n) 解

Question

我知道这个问题是前缀和的变体，我只是在设置它时遇到了一些困难。

Answer 1

计算两个数组呢： Lefts[i] 等于前 i 个元素的总和，:

Lefts[i] = A[0]+A[1]+A[2]..+A[i]

和 Rights[i] 等于最后 i 个元素的总和：

Rights[i] = A[n-1]+A[n-2]..+A[i]

然后S[i] = Left[i-1]+Rigt[i+1].

Answer 2

我提出的想法归结为其他答案中已经提出的建议。但是我想提出一个具有恒定内存开销的实现：

initialize S with 0
for i = 2 to n {
  S[i] = S[i -1] + A[i - 1] // somewhat similar to prefix sum array
}

help = 0 // a single variable - constant memory overhead
for i = n to 1 {
  S[i] += help
  help += A[i]
}

在第一次迭代后，S[i] 存储索引小于 i 的所有值的总和。在第二次迭代中，我将值的总和添加到当前值的右侧。

Answer 3

定义：

P[i] = A[i+1] + A[i+2] + ... + A[n]
Q[i] = A[1] + ... + A[i-1]

然后，S[i] = P[i] + Q[i]

Answer 4

定义 B[i] = A[1] + ... A[i-1] 和 C[i] = A[i+1] + ... + A[n] 然后 S[i ] = B[i] + C[i].

您可以在线性时间内计算这两个数组。您需要向后迭代以在线性时间内计算 C。

加法总数为3N - 2（每个位置加法一次，预计B中第一个，C中最后一个）。

找到前缀和变化的 O(n) 解

Find O(n) solution to variation of prefix sum

algorithm

complexity-theory