假设我有一个很长的，可能是无限的序列$x := [x_1, x_2, ...]$，我想用它来计算另一个序列$y:=[y_1, y_2, ...]$其中每个元素是输入序列的最后 K 个元素的总和。IE

$y_i = \sum_{j=max(1, i-K)}^i x_j$

天真、低效的方法（在 Python 中）是：

def sum_of_last_k(x: Sequence[float], k: int):
    buffer = [0. ] * k  # Initialize a buffer of k zeros
    for i, xi in enumerate(x):
        buffer[i % k] = xi  # Where % is modulo
        yield sum(buffer)

......哪个会有$\mathcal O(K)$每次迭代的效率。但是，我想在线高效地进行操作。我们可以做到这一点$\mathcal O(1)$通过保持流动总和：

def sum_of_last_k(x: Sequence[float], k: int):
   buffer = [0. ] * (k-1)  # Initialize a buffer of k-1 zeros
   running_sum = 0
   for i, xi in enumerate(x):
       ix_wrapped = i % (k-1)
       old_value = buffer[ix_wrapped]
       buffer[ix_wrapped] = xi
       running_sum = running_sum + xi - old_value
       yield running_sum

这有$\mathcal O(1)$效率，但仍然存在一个问题：由于浮点精度误差，可能存在running_sum随时间累积的舍入误差。

现在我知道我可以通过running_sum每 M 次迭代从头开始重新计算来解决这个问题，其中 M 是一个很大的数字，并且平均运行时间为$\mathcal O((M-1+K)/M)$这可能非常接近 1 ......但我希望最坏情况下的运行时间是$\mathcal O(1)$， 不是$\mathcal O(K)$.

那么，有没有办法计算这个$\mathcal O(1)$每次迭代的时间，同时仍保持数值稳定？