为何区间更新与查询需两棵Fenwick树？单树方案存何问题？

你的单树做法只能处理「区间加、单点查询」的场景，但要实现「区间加、区间和查询」就会出错，核心问题是混淆了单点值和区间和的计算逻辑，遗漏了区间和所需的另一项关键前缀和维护。

先拆解你的单树逻辑 #

当你执行update(l, v)和update(r+1, -v)时，这棵Fenwick树维护的是原数组差分数组的前缀和，换句话说，query(x)返回的是原数组第x个位置的单点值（即a[x]）。这时候查某个位置的数值，直接调用query(x)是对的，但如果用query(r) - query(l-1)，得到的是a[r] - a[l-1]——这显然不是区间[l,r]的数值和，而是两个单点值的差，完全不符合需求。

区间和查询需要的数学逻辑 #

要计算区间[l,r]的和，本质是求前缀和S(r) - S(l-1)，其中S(x) = sum_{i=1}^x a[i]。当我们对[l,r]加v后，前缀和S(x)的增量可以拆解为：

• 若x <= r：增量为v*(x - l + 1)
• 若x > r：增量为v*(r - l + 1)

把这个增量用差分数组d（d[1] = a[1]，d[i] = a[i] - a[i-1]，区间加v等价于d[l]+=v、d[r+1]-=v）推导，最终可得：

S(x) = (x+1)*sum(d[1..x]) - sum(k*d[k] from 1 to x)

这里需要两个关键前缀和：

1. sum(d[1..x])：差分数组的前缀和（你的单树刚好维护了这个）
2. sum(k*d[k] from 1 to x)：每个差分数组元素乘以其下标后的前缀和（你的单树完全没维护这个）

为什么需要两棵Fenwick树 #

区间和的计算依赖上述两个前缀和的组合，单棵树只能维护其中一个，所以必须用两棵树分别维护这两个值，才能正确计算出S(x)，进而得到S(r)-S(l-1)即区间[l,r]的和。

内容的提问来源于stack exchange，提问作者Rupasai Rangaraju