01先把问题说具体
静态前缀和查询快,但单点更新会影响很多前缀。如何同时支持单点加和前缀求和?
02一步步得到方法
每个位置只保存一段特定区间
使用一基下标。tree[i] 保存区间 (i−lowbit(i),i] 的和,其中 lowbit(i)=i&−i 是二进制最低有效 1 对应的数值。例如 i=6=110₂,lowbit=2,保存位置 5、6。
查询前 i 个元素时,先取 tree[i],再令 i-=lowbit(i),跳过刚覆盖的一段。每步清除一个二进制 1,若干互不重叠区间拼成完整前缀。
更新走向所有包含当前位置的区间
单点 i 增加 delta 时,tree[i] 必须增加,接着 i+=lowbit(i) 找到更大的包含区间,直到超过 n。查询是拆前缀,更新是找祖先,两条路径方向相反。
外部接口仍可以零基:更新下标 index 时先加 1;prefix(end) 表示半开 [0,end)。一致的接口约定比背诵 i+=i&−i 更重要。
每个格子负责哪一段
内部下标 i 保存长度 lowbit(i) 的后缀块,例如 i=12 的二进制为1100,lowbit=4,负责位置9到12。查询不断清掉最低有效1,正好把目标前缀拆成互不相交的块。
更新向上加 lowbit,跳到也覆盖当前元素的更大负责块。外部0下标与内部1下标应只在入口转换一次;若把内部 i 初始化为0,lowbit(0)=0 会让更新死循环。
03把一个小例子完全算清楚
原数组 [1,2,3,4,5,6],查询前 6 项,再给第 2 项(零基 1)加 3。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| tree 区间 | tree[6]=5+6=11,tree[4]=1+2+3+4=10 | 6 的查询路径为 6→4→0 |
| 查询 | 11+10=21 | 两个区间不重叠 |
| 更新 index=1 | 内部位置 2→4 | 两个包含该点的区间各加 3 |
| 再次查询 | 11+13=24 | 变化只计入一次 |
窄屏可左右滑动表格,阅读完整计算与理由。
一个节点不是某一位置的值,而是由最低位决定的区间和。
04为什么这个方法成立
- 查询每次去掉前缀最右端 lowbit 长度区间,剩余仍是一个更短前缀。
- 所取区间不重叠且覆盖完整查询范围,所以和正确。
- 更新恰好经过保存了该点贡献的节点,因而保持每个节点的区间定义。
05把推导翻译成代码
Python · 可独立运行的教学实现
class Fenwick:
def __init__(self, a):
self.n = len(a)
self.tree = [0]*(self.n+1)
for i,x in enumerate(a):
self.add(i,x)
def add(self, index, delta):
assert 0 <= index < self.n
i = index + 1
while i <= self.n:
self.tree[i] += delta
i += i & -i
def prefix(self, end):
assert 0 <= end <= self.n
result = 0
while end:
result += self.tree[end]
end -= end & -end
return result
def range_sum(self, left, right):
return self.prefix(right) - self.prefix(left)逐个理解关键决定
i = index + 1- 内部不能从 0 开始,否则 lowbit(0)=0 会使更新死循环。
self.prefix(right) - self.prefix(left)- 沿用半开区间前缀相减。
06时间、空间与实现范围
查询与单点加 O(log n),空间 O(n)。这里逐点建树 O(n log n),也存在 O(n) 建树方法。
求和可通过相减恢复区间,最小值没有同样的逆运算,不能直接把 + 改成 min 就得到任意区间查询。
07改变条件,检查哪里会出错
把 add(index,x) 当赋值
它表示增加 delta;赋新值要先知道旧值,再加 new−old。
把区间最大值直接写成两个前缀最大值相减
区间和利用了可逆的减法;max 不具有相同逆操作,不能照搬这个查询公式。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
i=12 保存哪段?
需要一点提示
12=1100₂,lowbit=4。
查看解析与答案
内部下标 9..12,即 (8,12]。
prefix(0) 为什么是 0?
需要一点提示
空前缀无需取节点。
查看解析与答案
while 不进入,返回加法单位元 0。
区间加、单点查怎样组合差分?
需要一点提示
维护变化事件的前缀。
查看解析与答案
在差分数组上用 Fenwick 做两次单点加,查询某位置用差分前缀和。