c++ - 查找数组中所有元素的总和，不包括索引 L 到 R

Question

我们有一个数组arr[0 . . . n-1]。我们应该能够

1. 求从索引 L 到 R 的元素之和，其中 0 <= L <= R <= n-1 。
2. 更改数组中指定元素的值，arr[i] = x其中 0 <= i <= n-1。

这可以有效地使用分段树来解决。

但是如何解决与此相反的问题，即

1. 求从索引 0 到 n-1 的所有元素 (arr[i]) 的总和，不包括 L<= i <= R，其中给出了 L 和 R。
2. array arr[i] = x更改where 0 <= i <= n-1的指定元素的值。

如何像段树一样有效地解决上述问题？

Answer 1

假设您可以使用线段树轻松计算 sum(L,R)。

首先，计算整个数组的总和，称为它total。

对于arrat 位置 ith的变化

• 像往常一样更新段树。

• 更新total = total - oldValue + newValue。

对于每个查询，打印total - sum(L,R)

注意：我们也可以使用二叉索引树（又名Fenwick 树）来解决这个问题，IMO 更适合。