1. 前缀和与差分的对比应用中前缀和 O(1) 查询区间和但修改 O(n)，差分 O(1) 区间加但查询 O(n)，两者如何与树状数组结合？
问题
请对比前缀和与差分的应用：前缀和 O(1) 查询区间和但修改 O(n)，差分 O(1) 区间加但查询 O(n)，并说明两者如何与树状数组结合？
考察点
- 前缀和的查询快、修改慢特性
- 差分的区间加快、查询慢特性
- 树状数组同时支持区间加与区间查询
答案
前缀和 pre[i] 表示前 i 项和，可用 O(1) 求任意区间和（pre[r]-pre[l-1]），但修改一个元素需 O(n) 更新前缀和数组。差分 d[i]=a[i]-a[i-1] 使区间 [l,r] 整体加 v 只需 d[l]+=v、d[r+1]-=v，O(1) 完成，但单点查询要累加差分前缀 O(n)。两者互补：查询密集用前缀和，修改密集用差分。树状数组（BIT）用差分思想把"区间加"变成两个单点更新，同时用 BIT 维护前缀和实现 O(log n) 区间查询，从而同时支持"区间加 + 区间查询"均为 O(log n)。具体地，用两个 BIT 分别维护 d[i] 与 i·d[i] 即可实现区间加、区间和查询。
解析
前缀和与差分是"字面相反"的两种预处理，各自牺牲一个方向换取另一个方向的 O(1)。树状数组通过维护差分及其加权前缀，把两个方向的复杂度都降到 O(log n)，是两者的统一与增强。
示例代码
// 两个 BIT 实现区间加 + 区间和查询
void rangeAdd(int l, int r, long v) { add(bit1, l, v); add(bit1, r+1, -v); add(bit2, l, v*(l-1)); add(bit2, r+1, -v*r); }
long prefixSum(int x) { return sum(bit1, x) * x - sum(bit2, x); }
long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l-1); }