algorithm - 对于序列中的每个元素，对序列的其余部分求和

Question

标题有点误导:我想做的有点复杂，但我不知道如何在标题中描述它。

我有两个数字序列(向量、数组、列表)p 和 q。我对 p 中除第一个元素之外的所有数字求和，然后执行测试。如果失败，我将 p 的第一个元素替换为 q 的第一个元素，然后从第二个元素重新开始:对 p 的所有元素求和em> 除了第二个(包括从 q 复制的新元素)。如果第二次测试失败，将p中的第二个元素替换为q中的第二个元素，并用第三个元素再次进行。测试总是在某些元素上成功。伪代码:

i = 0
if test(sum_except p i) then exit loop
else p[i] := q[i], and run again with i+1

这意味着如果我有 1000 个元素，我会对其中的 999 个求和，然后下一次我对其中的 998 个求和再加上一个新元素，依此类推。随着这个过程的进行，我也在 q 中总结了越来越多的元素，而不是从原始的 p 中总结，但我之前也会总结其中的大部分.因此，在每一步中，我都会对已经加在一起的一堆数字求和。这看起来效率很低，但我还没有想出更明智的写法。

如果重要的话，测试所做的是检查 p 中除 i 处的元素外的值之和是否加上 q 的值 在 i 处，大于或等于 1(或小于或等于 1——有两种变体)。即:

(sum_except p i) + q[i] > 1

这一切都发生在一个内部循环中，序列长度可能在 500 到 5000 之间，尽管更大的数字也是可能的。

(我的代码实际上是在 OCaml 中，fwiw。)

Answer 1

计算开始处所有数字的总和(以下称为sum)。 sum_except p i 等同于 sum - p[i]。

当您更新列表中的项目时，也会更新总和，这样您就不必每次都通过遍历 p 中的每个元素来重新计算它。

// Remove old value
sum := sum - p[i]
p[i] := q[i]
// Add new value
sum := sum + p[i]

由于您一次最多修改列表中的一个值，您可以简单地手动更新总和以反射(reflect)更改，而不是再次对列表中的所有元素求和，这使得循环体以恒定时间运行。