CC++ & Algorithm

树状数组的原理（lowbit运算）

困难4
语言版本：通用
概述：树状数组是一种高效维护前缀和的数据结构，它的核心思想是利用「lowbit」运算来组织数据的存储和查询，就像给班级同学分组管理一样，每个小组长只负责管理自己身后的几个同学。

树状数组原理与 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)说明
5101第1位（2^0）1最低位1，后面无0
6110第2位（2^1）2最低位1右边有一个0
81000第4位（2^3）8最低位1右边有三个0
121100第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 那一位。

用代码验证：

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) 的连续区间。

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

下标 ilowbit(i)管理的区间（左闭右闭）
11[1, 1]
22[1, 2]
31[3, 3]
44[1, 4]
51[5, 5]
62[5, 6]
71[7, 7]
88[1, 8]
91[9, 9]
102[9, 10]
111[11, 11]
124[9, 12]
131[13, 13]
142[13, 14]
151[15, 15]
1616[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++ 实现

#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 实现

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) 时间内优雅地统计前缀和。现在你可以自己动手，用树状数组来管理班级的成绩、商店的库存、游戏中的经验值……任何需要快速求和和单点更新的场景，它都能大显身手。

例题精讲

1单选题

在树状数组中，lowbit运算定义为 lowbit(x) = x & (-x)。已知 x = 10（十进制），则 lowbit(10) 的值是？

A1
B2
C4
D8
2判断题

树状数组中，数组c[i]存储的是原数组a中从下标 i - lowbit(i) + 1 到 i 的所有元素之和。

3填空题
下面是树状数组中计算lowbit的函数实现，请补充空缺处的代码。

int lowbit(int x) {
    return ___;
}
4单选题

当使用树状数组进行单点更新（给a[i]增加一个值）时，需要依次更新c[i]、c[i+lowbit(i)]、……，直到下标超出数组范围。假设当前下标为i，那么下一个需要更新的下标是？

Ai + lowbit(i)
Bi - lowbit(i)
Ci + 1
Di + 2 * lowbit(i)
5判断题

树状数组中，查询前缀和 sum(1..k) 的过程是：从下标k开始，累加c[k]，然后令 k = k - lowbit(k)，重复直到k变为0。