困难通用11 分钟3,749 字

树状数组的原理(lowbit运算)

树状数组(Fenwick Tree,也叫 Binary Indexed Tree)是一种专门用来快速计算数组前缀和​的数据结构。简单来说,如果你有一排数字(比如全班同学的考试分数),经常需要问“前10个同学总分是多少?”或者“第5个同学分数增加了3分,怎么更新所有相关统计?”,用普通的数组每次都要从头加一遍,非常慢。树状数组就像一个聪明的“分组记账本”,把数字按照二进制规律分成一块一块的小组,这样无论是查询​还是修改​​,都只需要操作几个小组,速度从 O(n) 降到了 O(log n)。

它的核心秘密道具就是 lowbit 运算​——一个神奇的位运算,能告诉我们每个“小组长”到底负责几个人的数据。


1. 生活中的例子:小伙伴分组管理零花钱

假设你是一个班级的生活委员,负责统计全班40个同学的零花钱总额。老师经常要查“前 m 个同学一共带了多少零花钱”。如果直接挨个数,每次查都要花很多时间。聪明一点的做法是:让几个同学当“小组长”,每个小组长只负责记录自己身后的几个同学的数据。

但是怎么分组最方便呢?我们让编号的二进制规律​来帮忙:

  • 1号同学只负责自己(二进制 1,lowbit=1)
  • 2号同学负责1号和2号(二进制 10,lowbit=2)
  • 3号同学只负责自己(二进制 11,lowbit=1)
  • 4号同学负责1到4号(二进制 100,lowbit=4)
  • 5号同学只负责自己(二进制 101,lowbit=1)
  • 6号同学负责5和6号(二进制 110,lowbit=2)
  • 7号同学只负责自己(二进制 111,lowbit=1)
  • 8号同学负责1到8号(二进制 1000,lowbit=8)
  • ……

这样,当你想知道前10个同学的总零花钱时,只需要找:8号同学(他知道前8人)、10号同学(他知道9和10两人),两个数字加起来就得到前10人的总和!不需要再把1到10全算一遍。

这个“分组”的规律就是:​编号为 i 的同学,负责从 i – lowbit(i) + 1 到 i 这一段连续的同学​​。lowbit(i) 就是 i 的二进制中最低位的1所代表的数值。


2. lowbit 运算到底是什么?

2.1 直观理解

对于一个正整数 x,把它写成二进制,找到最右边(最低位)的1,这个1及其右边所有的0组成的数,就是 lowbit(x)。例如:

x 二进制 最低位1的位置 lowbit(x) 说明
5 101 第1位(2^0) 1 最低位1,后面无0
6 110 第2位(2^1) 2 最低位1右边有一个0
8 1000 第4位(2^3) 8 最低位1右边有三个0
12 1100 第3位(2^2) 4 最低位1右边有两个0

2.2 计算机里的魔法公式:x & (-x)

在编程中,计算 lowbit 最简单的方法就是 x & (-x)。为什么可以这样?

  • 正数 x 的负数 -x 在计算机里用补码​表示:把 x 的二进制按位取反,再加1。
  • 例如 x=6(二进制 110),取反得 001,加1得 010(即2)。
  • 你会发现,x 和 -x 的二进制: x = ...0110 -x = ...1010 (补码) & = ...0010 → 2
  • 只有 lowbit 那一位,x 和 -x 同时为1,其他位都相反,按位与之后只剩下 lowbit 那一位。

用代码验证:​

python
print(6 & -6)   # 输出 2
print(8 & -8)   # 输出 8
print(5 & -5)   # 输出 1

⚠️ 注意:这个公式对负整数也成立,但树状数组只用到正整数下标,所以我们只需关心正数。


3. 树状数组的存储结构:每个“小组长”管一段

树状数组用另一个数组 tree[] 来存储分组后的和。规定:

tree[i] = 原数组 a 中从下标 i - lowbit(i) + 1 到 i 的所有元素之和

也就是说,​下标 i 对应的管理者只负责一段长度为 lowbit(i) 的连续区间​​。

我们可以画一个表来更清楚:

下标 i lowbit(i) 管理的区间(左闭右闭)
1 1 [1, 1]
2 2 [1, 2]
3 1 [3, 3]
4 4 [1, 4]
5 1 [5, 5]
6 2 [5, 6]
7 1 [7, 7]
8 8 [1, 8]
9 1 [9, 9]
10 2 [9, 10]
11 1 [11, 11]
12 4 [9, 12]
13 1 [13, 13]
14 2 [13, 14]
15 1 [15, 15]
16 16 [1, 16]

观察一下:管理范围跟二进制有关,​下标是2的幂次时(如1,2,4,8,16)​​​,它们管理的范围是前缀,覆盖从1到自己。其他下标只管理一小段。

关键规律:更新和查询的“跳跃”路径

  • 更新​​(修改某个元素 a[k]):从 k 开始,每次加上自己的 lowbit,得到下一个需要更新的 tree 节点。比如修改 a[3],需要更新 tree[3](自己)、tree[4](因为 3+lowbit(3)=4,tree[4] 包含 [1,4])、tree[8](4+4=8,包含[1,8])……直到超过数组长度。
  • 查询前缀和​​(求 a[1] 到 a[k] 的和):从 k 开始,每次减去自己的 lowbit,累加对应的 tree 节点,直到变成0。比如求前10个元素的和,先加 tree[10](管理[9,10]),然后 10-2=8,加 tree[8](管理[1,8]),然后 8-8=0,结束。结果就是 tree[10]+tree[8]。

这种“跳跃”每次正好跳过一段区间,而跳跃次数等于二进制中1的个数,最多 log₂n 次,所以速度飞快。


4. 树状数组的基本操作:add 和 sum

我们通常把树状数组封装成一个类,包含两个核心方法:add(单点更新)和 sum(前缀和查询)。

4.1 add(给某个位置加值)

void add(int idx, int delta) {
    while (idx <= n) {
        tree[idx] += delta;
        idx += lowbit(idx);
    }
}

举例​​:给 a[3] 增加 5。执行步骤:

  1. idx=3,lowbit(3)=1 → tree[3] += 5,idx=4
  2. idx=4,lowbit(4)=4 → tree[4] += 5,idx=8
  3. idx=8,lowbit(8)=8 → tree[8] += 5,idx=16
  4. 假设 n=10,16>10,停止。

这样就更新了所有包含 a[3] 的管理者。

4.2 sum(求前缀和)

int sum(int idx) {
    int res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= lowbit(idx);
    }
    return res;
}

举例​​:求前7个元素的和。

  1. idx=7,lowbit(7)=1 → 加上 tree[7](管理[7,7]),idx=6
  2. idx=6,lowbit(6)=2 → 加上 tree[6](管理[5,6]),idx=4
  3. idx=4,lowbit(4)=4 → 加上 tree[4](管理[1,4]),idx=0
  4. 结果 = tree[7]+tree[6]+tree[4]

4.3 区间查询

利用前缀和,求 [l, r] 的和就是 sum(r) - sum(l-1)。


5. 新手常见错误(避坑指南)

  1. 下标从0还是1开始?​ 树状数组通常要求下标从1开始,因为 lowbit(0)=0 会导致死循环。如果你的原数组从0开始,可以整体偏移一位,或者在最前面加一个无用元素(比如 a[0]=0)。
  2. 忘记 lowbit 的计算方式 有的人会写成 x & (x-1) 或 x - (x & (x-1)),这些得到的是别的值。一定要记住:x & (-x) 才是正确的 lowbit。
  3. 更新时循环条件写错 add 里要写成 while (idx <= n) 而不是 while (idx > 0),否则会跳过一些节点。查询时正好相反,用 while (idx > 0)。
  4. 区间查询时忘记减1 rangeSum(l, r) = sum(r) - sum(l-1),注意 l-1 可能等于0,此时 sum(0) 应返回0(我们的 sum 函数在 idx<=0 时会跳过循环,返回0,没问题)。
  5. 多组数据时忘记重置 tree 数组 如果多次使用,记得把 tree 全部清零,或者重新构造对象。
  6. 在 Python 中使用 x & -x 时,x 是负数会怎样?​ 树状数组只用正数下标,所以不用担心。

6. 完整可运行代码(含中文注释)

C++ 实现

cpp
#include <iostream>
#include <vector>
using namespace std;

class Fenwick {
private:
    int n;                 // 数组大小
    vector<int> tree;      // 树状数组,下标从1开始

    // lowbit运算:返回x二进制最低位1的值
    int lowbit(int x) {
        return x & -x;     // 位运算方式计算lowbit
    }

public:
    // 构造函数:初始化大小为n的树状数组,全部置为0
    Fenwick(int n) : n(n), tree(n + 1, 0) {}

    // 单点更新:给位置idx加上delta
    void add(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;   // 更新当前节点
            idx += lowbit(idx);   // 跳到下一个需要更新的节点
        }
    }

    // 前缀和查询:返回前idx个元素的和
    int sum(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];     // 累加当前节点值
            idx -= lowbit(idx);   // 跳到前一个区间
        }
        return res;
    }

    // 区间查询:[l, r] 的和
    int rangeSum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

int main() {
    // 示例:原数组 a[1..8] = {3,1,4,1,5,9,2,6}
    int a[] = {0,3,1,4,1,5,9,2,6}; // 下标从1开始,0弃用
    int n = 8;
    Fenwick ft(n);
    for (int i = 1; i <= n; ++i) {
        ft.add(i, a[i]);
    }

    cout << "前5个元素的和: " << ft.sum(5) << endl;   // 3+1+4+1+5=14
    cout << "区间[3,6]的和: " << ft.rangeSum(3,6) << endl; // 4+1+5+9=19

    // 单点修改:将a[4]增加10
    ft.add(4, 10);
    cout << "修改后前5个元素的和: " << ft.sum(5) << endl; // 14+10=24

    return 0;
}

Python 实现

python
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # 下标从1开始,0废弃

    def lowbit(self, x):
        return x & -x               # lowbit运算

    def add(self, idx, delta):
        """单点更新:给位置idx增加delta"""
        while idx <= self.n:
            self.tree[idx] += delta
            idx += self.lowbit(idx)

    def sum(self, idx):
        """前缀和查询:返回前idx个元素的和"""
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= self.lowbit(idx)
        return res

    def range_sum(self, l, r):
        """区间查询:[l, r]的和"""
        return self.sum(r) - self.sum(l - 1)

# 示例: 用零花钱的例子来测试
if __name__ == "__main__":
    # 假设8个同学每天的零花钱:3,1,4,1,5,9,2,6(单位元)
    money = [0, 3, 1, 4, 1, 5, 9, 2, 6]  # 下标从1开始
    n = 8
    ft = Fenwick(n)
    for i in range(1, n+1):
        ft.add(i, money[i])

    print("前5个同学的总零花钱:", ft.sum(5))           # 3+1+4+1+5=14
    print("第3到第6个同学的总零花钱:", ft.range_sum(3,6))  # 4+1+5+9=19

    # 第4个同学今天多带了10元
    ft.add(4, 10)
    print("修改后前5个同学的总零花钱:", ft.sum(5))     # 14+10=24

运行结果:​

前5个同学的总零花钱: 14
第3到第6个同学的总零花钱: 19
修改后前5个同学的总零花钱: 24

7. 相关指引与拓展思考

学完树状数组,你可能会想:

  • 如果既要查询前缀和,又要区间更新​​(比如把一段区间同时加上同一个数),怎么办?可以用差分数组 + 树状数组​实现(维护两个树状数组)。
  • 树状数组还能解决逆序对​问题(用树状数组统计每个数字出现的次数)。
  • 比树状数组更强大的是线段树​​,它支持区间更新和更复杂的操作(比如最大值、最小值),但代码更长。
  • 二维树状数组可以处理二维前缀和​​,比如矩阵中某个矩形区域的和。

一句话总结:​ lowbit 就是树状数组的灵魂,理解了它,你就掌握了如何在 O(log n) 时间内优雅地统计前缀和。现在你可以自己动手,用树状数组来管理班级的成绩、商店的库存、游戏中的经验值……任何需要快速求和和单点更新的场景,它都能大显身手。

同类知识点