专题进阶 · 树与范围查询推荐总顺序 · 第 53 / 148 课

从 lowbit 所代表的区间长度推导树状数组的查询与更新路径。

先学会这些,再进入本课 前缀和 差分
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

树状数组Fenwick Tree

用 lowbit 分解前缀区间,单点修改和前缀和都为 O(log n)。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

从 lowbit 所代表的区间长度推导树状数组的查询与更新路径。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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=106 的查询路径为 6→4→0
查询11+10=21两个区间不重叠
更新 index=1内部位置 2→4两个包含该点的区间各加 3
再次查询11+13=24变化只计入一次

窄屏可左右滑动表格,阅读完整计算与理由。

一个节点不是某一位置的值,而是由最低位决定的区间和。

04为什么这个方法成立

  1. 查询每次去掉前缀最右端 lowbit 长度区间,剩余仍是一个更短前缀。
  2. 所取区间不重叠且覆盖完整查询范围,所以和正确。
  3. 更新恰好经过保存了该点贡献的节点,因而保持每个节点的区间定义。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

i=12 保存哪段?

需要一点提示

12=1100₂,lowbit=4。

查看解析与答案

内部下标 9..12,即 (8,12]。

练习 2 · 边界与辨析

prefix(0) 为什么是 0?

需要一点提示

空前缀无需取节点。

查看解析与答案

while 不进入,返回加法单位元 0。

练习 3 · 变式与迁移

区间加、单点查怎样组合差分?

需要一点提示

维护变化事件的前缀。

查看解析与答案

在差分数组上用 Fenwick 做两次单点加,查询某位置用差分前缀和。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。