数组不变时，一次前缀和预处理就能让任意区间求和变成两次读取和一次相减。若每次查询前都有一个元素变化，维护全部后缀前缀值又会变得昂贵。Fenwick树和线段树减少的是一次更新影响的摘要数量，不是让任意聚合都能通过前缀相减得到。

本篇统一接口，才能让三种结构处理同一负载。输入整数数组A，长度n；add(i,delta)令A[i]增加delta，sum(l,r)返回半开区间A[l:r]之和。合法范围为0≤i<n、0≤l≤r≤n；空区间返回0，越界抛IndexError。空数组可构造，只有sum(0,0)合法。后续区间更新、静态查询和历史版本均沿用这套边界。

前缀相减为什么成立

定义P[0]=0，P[j]为前j个元素之和。因为A[0:r]可以拆成A[0:l]与A[l:r]，所以区间和为P[r]−P[l]。线性扫描构造P耗Θ(n)，每次查询常数次算术，空间Θ(n)。点更新A[i]会影响P[i+1]直到P[n]，最坏Θ(n)。

相减使用加法逆元。若P[j]改成前j个元素的最小值，两份前缀最小值无法恢复中间区间的最小值。例如 [1,5] 与 [1,9] 的两个非空前缀最小值都为1，却有不同的第二个元素。这不是精度问题，而是摘要丢失了无法恢复的信息。

抽象地说，整数加法具有结合律、单位元0和逆元，且可交换。区间拼接需要结合律，空区间需要单位元，前缀消去另需逆操作；标准Fenwick点增量的简洁更新还依赖交换性。不能把这些条件缩成一句“支持某种运算即可”。

Fenwick保存哪些块

内部使用1基下标。记lowbit(j)=j&(-j)，B[j]保存原数组中半开区间 [j-lowbit(j),j) 的和。每个位置只保存一段以自身右端点结尾、长度为2的幂的块。

求前r项之和时，从j=r开始累加B[j]，再令j减去lowbit(j)。刚取出的块紧贴未处理前缀的右端，块之间不相交；j降到0时恰好覆盖A[0:r]。每次清除j二进制最低的一个1，因此最多O(log(n+1))步。sum(l,r)仍由两个前缀结果相减。

点更新i时先设j=i+1，再不断令j增加lowbit(j)，把delta加到沿途B[j]。这些恰是包含位置i的上层块。可以把最低有效位看成当前块尺寸：跳到下一个覆盖块时，区间仍包含i，直到右端超出n；没有被访问的块不含i，因而不用修改。

例如n=8，更新0基下标5，对应内部位置6，修改B[6]与B[8]。查询前7项依次读取B[7]、B[6]、B[4]，分别覆盖 [6,7)、[4,6)、[0,4)，三块不重叠且无遗漏。下标混用会让更新位置0时错误地进入lowbit(0)=0的死循环，因此1基只限内部表示，外部契约保持0基。

标准点加更新把delta直接加到每个包含该点的块总和上，这利用了加法可交换性。对非交换群，修改块中间位置不能一般地在块总积末尾乘delta；即使查询可以用逆元取消前缀，这个更新规则仍可能错误。本文只实现整数加法，不用泛型命名掩盖这一限制。

线段树靠不相交区间组合

把叶子数补到不小于n的最小2次幂p，多出的叶子放单位元0。每个内部节点存左右孩子之和。由叶子的定义和结构归纳，每个节点都等于它覆盖区间的和；点更新后只需沿祖先链重新求和，高度O(log(n+1))。

查询时把目标区间分解成树上的不相交完整节点区间。每层最多保留左右两个未完全覆盖的边界，完整落在区间内的中间节点立即计入，不再下探。故每层只贡献常数个节点，总查询O(log(n+1))。不能用“对左右孩子递归”直接写出遍历整棵树的递推，再给对数结论；应分析边界路径数量。

迭代查询使用左右两个累加器。左侧节点按从左到右顺序追加，右侧节点按从右到左发现、向前插入，最后拼接左右结果。对求和来说交换顺序也可能得到相同答案，但若以后替换为字符串拼接或矩阵乘法，顺序就决定正确性。一般线段树只要求运算结合且有单位元，不要求交换或可逆。

把构造成本也列出来

三者逻辑空间均为O(n)，但保存的摘要不同。Fenwick构造若从零调用n次add，时间O(n log(n+1))；也可以先复制单点值，再把每个内部块向其直接父块传播一次，获得O(n)构造。本篇实现采用后一种线性构造。线段树由叶子向上pull，p<2n（n>0），所以构造O(n)。

结构 构造 点增量更新 区间和查询
前缀和 O(n) 最坏O(n) O(1)
Fenwick O(n)，线性构造 O(log(n+1)) O(log(n+1))
线段树 O(n) O(log(n+1)) O(log(n+1))

这些是确定性最坏运算次数界，不是摊还或随机保证。默认整数算术计单位成本；若值与累计和的位长增长，Python大整数相加还要乘入相应位运算成本。没有计时实验时，不从“数组更紧凑”推断某种结构在所有机器上更快。

同一负载怎样差分

运行 python3 examples/advanced-algorithms/check_range_sum.py。本次121个小数组的穷举检查共3834次add调用、56730次sum调用；随机长度1、3、7、17、32的负值负增量负载共1500次add、236643次sum；54项非法输入和200位整数检查也通过。计数是三个受测结构的API调用总数，不是内部算术次数；原始输出在 examples/advanced-algorithms/results/range_sum.json，配套区间契约可下载。独立参照直接修改列表并用sum(A[l:r])查询；每次更新后检查全部合法区间，能覆盖仅查总和遗漏的局部错误。负增量、非2次幂长度、空数组和右端点n都属于有效的边界用例。

例如只检查sum(0,n)，把一次更新错误地落到相邻叶子仍可能通过；检查所有小区间则能定位错位。有限差分证明受测实例一致，Fenwick块覆盖和线段树归纳才承担一般正确性论证。

练习

  1. 对数组 [3,-1,4,0,2] 写出全部Fenwick块。执行add(2,-5)，手算sum(1,5)，列出更新和查询分别访问的内部下标。
  2. 把线段树聚合改为字符串连接，单位元为空串。构造一个查询，使“右累加器向后追加”的错误被暴露；解释为什么整数求和测试不能检出这个错误。

参考资料