【算法提高篇】（九）树状数组入门：从原理到实战，一篇吃透 BIT

_OP_CHEN

发布于 2026-02-26 08:26:20

1040

文章被收录于专栏：C++C++

前言

在算法学习中，处理单点修改和区间查询问题时，你是否还在为线段树的冗长代码头疼？是否想找一个效率相当、实现更简洁的数据结构？今天要介绍的树状数组（Binary Indexed Tree，简称 BIT） 就是你的最优解！树状数组是一种专为区间统计设计的高效数据结构，修改和查询的时间复杂度均为O(logN)，代码量只有线段树的 1/3，时间效率常数也更小。它能解决线段树的部分核心问题，是算法竞赛、笔试面试中处理区间问题的 “利器”。本文将从原理到实战，由浅入深讲解树状数组，包括一维、二维的各种操作，让你从零开始吃透树状数组！下面就让我们正式开始吧！

一、树状数组的引入

1.1 树状数组的定位

树状数组是一种仅支持单点修改和区间查询的线性数据结构，核心解决的是序列的区间统计问题（如区间和、区间乘积），其所有操作的时间复杂度均为O(logN)，在数据量达到106甚至107时仍能高效运行。

它和线段树的关系可以用一句话概括：树状数组能解决的问题，线段树一定能解决；但线段树能解决的问题，树状数组不一定能解决。树状数组是线段树的 “简化版”，舍弃了部分通用性，换来了极致的简洁和效率。

1.2 树状数组的适用场景

树状数组维护的信息需要满足两个核心条件：

结合律：如区间和中(a+b)+c = a+(b+c)，区间乘积中(a*b)*c = a*(b*c)；
可差分（可减性）：能通过前缀信息相减得到任意区间的信息，比如区间和可以用[1,r] - [1,l-1]得到[l,r]的和。

注意：如果信息不满足可差分，树状数组就无法维护，比如区间最值、区间 GCD，这类问题还是需要用线段树解决。

1.3 树状数组的学习价值

可能有同学会问：既然线段树更通用，为什么还要学树状数组？

代码极简：树状数组的核心操作（修改、查询）只有几行循环，远少于线段树的结构体 + 递归 / 非递归实现；
常数更小：树状数组是连续的数组存储，没有线段树的节点冗余，缓存命中率更高，运行速度更快；
应用广泛：算法竞赛中 80% 的区间统计问题都是树状数组能解决的，比如逆序对、区间和修改查询、二维子矩阵统计等。

二、树状数组维护信息的方式及核心性质

为了更好理解树状数组的设计思路，我们先从线段树入手，看看树状数组是如何对线段树做 “精简” 的。

2.1 从线段树到树状数组的精简

假设我们有一个长度为 8 的序列，用线段树维护区间和时，节点结构是这样的：

线段树的每个节点都维护一个区间和，但实际上，很多区间的信息可以通过前缀和相减推导出来，比如[3,5]的和可以用[1,5]-[1,2]得到，这些冗余的节点完全可以舍弃。

可以看到，树状数组仅保留了线段树中必要的节点，用一个普通数组就能存储，这就是树状数组的核心设计思路。

补充：树状数组的原始设计并非来自线段树精简，而是通过二进制拆分区间实现的 —— 将任意区间[1,x]拆分成若干个无交集的区间，每个区间的长度为lowbit(x)。两种思路殊途同归，线段树精简的方式更易理解，二进制拆分则是树状数组的本质。

2.2 树状数组的核心性质（下标从 1 开始！）

树状数组的下标必须从 1 开始（这是由 lowbit 操作的特性决定的，x=0 时 lowbit (0) 无意义），其所有操作都围绕lowbit展开，核心有 3 个性质，这是理解和实现树状数组的关键！

先定义：lowbit(x) = x & -x，作用是保留 x 的二进制中最右边的 1，比如x=6（110），lowbit(6)=2（10）；x=8（1000），lowbit(8)=8（1000）。

性质 1：向上爬公式（找父节点）

节点编号为 x 时，父节点编号为x + lowbit(x)。树状数组是一棵 “不完全的树”，每个节点都有对应的父节点，修改操作时需要沿着父节点一路向上更新，因为父节点维护的区间包含当前节点。

性质 2：向前跳公式（找前一个相邻区间）

节点编号为 x 时，前一个相邻区间的编号为x - lowbit(x)。查询前缀和[1,x]时，需要通过这个公式不断向前跳，累加每个区间的和，直到跳至 0 为止。

性质 3：节点维护的区间范围

节点编号为 x 时，该节点维护的区间是 [x - lowbit(x) + 1, x]。这是树状数组的核心，每个节点都有明确的区间管辖范围，比如：

x=5（101），lowbit (5)=1，维护区间[5,5]；
x=6（110），lowbit (6)=2，维护区间[5,6]；
x=8（1000），lowbit (8)=8，维护区间[1,8]。

2.3 树状数组的结构示例（n=8）

结合上述性质，我们给出 n=8 时树状数组的完整节点分布，每个节点的编号、lowbit 值、维护区间一目了然：

节点 x	1(001)	2(010)	3(011)	4(100)	5(101)	6(110)	7(111)	8(1000)
lowbit(x)	1	2	1	4	1	2	1	8
维护区间	[1,1]	[1,2]	[3,3]	[1,4]	[5,5]	[5,6]	[7,7]	[1,8]

通过这个表格，你可以清晰看到：树状数组的每个节点都只维护一段连续的区间，且区间长度恰好是lowbit(x)。

三、一维树状数组：核心操作与实战

一维树状数组是树状数组的基础，也是最常用的形式，核心解决序列的单点修改 + 区间查询、区间修改 + 单点查询、区间修改 + 区间查询三类问题，下面逐一讲解，每个问题都给出原理和完整 C++ 代码。

3.1 基础版：单点修改 + 区间查询

这是树状数组的最基础用法，解决的问题是：给定一个长度为 n 的序列，执行 m 次操作，要么修改某个位置的数值，要么查询某个区间[l,r]的和。

核心思路

单点修改：当位置 x 的数值增加 k 时，所有包含 x 的树状数组节点都需要更新，沿着父节点x += lowbit(x)一路向上，直到超过 n；
区间查询：利用前缀和思想，先查询[1,r]的和，再查询[1,l-1]的和，两者的差就是[l,r]的和；
树状数组的创建：初始时树状数组全为 0，读入序列的每个元素a[i]，相当于对位置 i 执行单点修改（加 a [i]）。

核心代码实现

#include <iostream>
using namespace std;

// 定义lowbit操作，宏定义更高效
#define lowbit(x) (x & -x)
// 数据范围根据题目调整，一般开1e5+10或1e6+10
typedef long long LL; // 防止溢出，区间和建议用long long
const int N = 1e6 + 10;

int n, m;
LL tree[N]; // 树状数组的存储数组

// 单点修改：位置x增加k
void modify(int x, LL k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}

// 前缀和查询：查询[1,x]的和
LL query(int x) {
    LL res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}

// 区间查询：查询[l,r]的和
LL interval_query(int l, int r) {
    return query(r) - query(l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // 加速cin，处理大数据必备

    cin >> n >> m;
    // 初始化树状数组：读入原序列，逐个单点修改
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        modify(i, x);
    }

    // 处理m次操作
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 操作1：单点修改，位置x加k
            int x;
            LL k;
            cin >> x >> k;
            modify(x, k);
        } else {
            // 操作2：区间查询，查询[l,r]的和
            int l, r;
            cin >> l >> r;
            cout << interval_query(l, r) << endl;
        }
    }

    return 0;
}

代码说明

为什么用long long？：当 n 达到106，每个元素为106时，区间和会达到1012，超出 int 的范围（2×109），因此必须用 long long 防止溢出；
输入加速：ios::sync_with_stdio(false); cin.tie(0);是 C++ 处理大数据的常用技巧，避免 cin 因同步 stdio 导致的速度变慢；
操作封装：将区间查询封装为interval_query，代码更易读。

3.2 进阶版 1：区间修改 + 单点查询

如果问题变成将区间[x,y]的所有数加 d，查询某个位置 i 的数值，直接用基础版树状数组无法实现，此时需要结合差分思想。

核心思路

回顾差分的性质：

对原数组 a 的区间[x,y]加 d，等价于对差分数组 diff 的x 位置加 d，y+1 位置减 d；
原数组的某个位置 i 的数值，等价于差分数组 diff 的前缀和[1,i]。

因此，区间修改 + 单点查询的问题可以转化为：用树状数组维护差分数组 diff，将原问题的区间修改变为树状数组的两次单点修改，原问题的单点查询变为树状数组的前缀和查询。

核心代码实现

#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 1e6 + 10;

int n, m;
LL tree[N]; // 树状数组维护差分数组diff

void modify(int x, LL k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}

LL query(int x) { // 查询差分数组的前缀和[1,x]，即原数组a[x]的值
    LL res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}

// 区间修改：原数组[a,b]的所有数加k
void interval_modify(int a, int b, LL k) {
    modify(a, k);
    if (b + 1 <= n) {
        modify(b + 1, -k);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    // 初始化：原数组a[i]，转化为差分数组的单点修改
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        interval_modify(i, i, x); // 对[i,i]加x，等价于diff[i]+x
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 操作1：区间修改，[l,r]加k
            int l, r;
            LL k;
            cin >> l >> r >> k;
            interval_modify(l, r, k);
        } else {
            // 操作2：单点查询，查询a[x]的值
            int x;
            cin >> x;
            cout << query(x) << endl;
        }
    }

    return 0;
}

代码说明

初始化技巧：原数组的每个元素a[i]可以看作是对差分数组执行interval_modify(i,i,a[i])，即对区间[i,i]加 a [i]；
边界判断：执行modify(b+1,-k)时，需要判断b+1 <=n，避免下标越界。

3.3 进阶版 2：区间修改 + 区间查询

这是一维树状数组的最高阶用法，解决的问题是：将区间[x,y]的所有数加 k，查询区间[l,r]的和。该问题需要结合差分 + 数学推导，用两个树状数组维护不同的信息。

核心推导

设原数组为 a，差分数组为 d，满足a[i]=∑j=1id[j]。

我们需要求原数组的前缀和S[i] = a[1]+a[2]+...+a[i]，将 a [j] 用差分数组表示并展开：

令：

sum1[i] = \sum_{k=1}^i d[k]（d 数组的前缀和）
sum2[i] = \sum_{k=1}^i d[k]×(k-1)（d [k]×(k-1) 的前缀和）

则原数组的前缀和S[i]=i×sum1[i]−sum2[i]。

原数组的区间和[l,r] = S[r] - S[l-1]，因此只需用两个树状数组分别维护d[k]和d[k]×(k-1)，即可实现区间修改 + 区间查询。

核心思路

用树状数组 A 维护d[k]，树状数组 B 维护d[k]×(k-1)；
对原数组区间[x,y]加 k，等价于对差分数组 d 执行：d[x]+k、d[y+1]-k，因此对 A 和 B 分别执行两次单点修改：
- A.modify(x, k)、A.modify(y+1, -k)
- B.modify(x, k×(x-1))、B.modify(y+1, -k×y)
求原数组前缀和 S [i]：i * A.query(i) - B.query(i)；
求原数组区间和[l,r]：S[r] - S[l-1]。

核心代码实现

为了让代码更易读，我们将树状数组封装为结构体：

#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 1e6 + 10;

int n, m;

// 封装树状数组结构体，复用代码
struct BIT {
    LL tree[N];
    // 单点修改
    void modify(int x, LL k) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tree[i] += k;
        }
    }
    // 前缀和查询
    LL query(int x) {
        LL res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            res += tree[i];
        }
        return res;
    }
}A, B; // A维护d[k]，B维护d[k]*(k-1)

// 原数组区间[x,y]加k
void interval_modify(int x, int y, LL k) {
    A.modify(x, k);
    A.modify(y + 1, -k);
    B.modify(x, k * (x - 1));
    B.modify(y + 1, -k * y);
}

// 求原数组前缀和[1,i]
LL prefix_sum(int i) {
    return (LL)i * A.query(i) - B.query(i);
}

// 求原数组区间和[l,r]
LL interval_query(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    // 初始化原数组a[i]
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        interval_modify(i, i, x); // 对[i,i]加x，初始化差分数组
    }

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 操作1：区间修改，[l,r]加k
            int l, r;
            LL k;
            cin >> l >> r >> k;
            interval_modify(l, r, k);
        } else {
            // 操作2：区间查询，[l,r]的和
            int l, r;
            cin >> l >> r;
            cout << interval_query(l, r) << endl;
        }
    }

    return 0;
}

代码说明

结构体封装：将树状数组的 modify 和 query 封装为结构体，避免重复代码，A 和 B 两个树状数组直接复用；
数据类型：所有乘法操作都要强制转换为 long long，防止 int 溢出；
初始化：同样用interval_modify(i,i,x)初始化原数组，等价于差分数组的单点修改。

四、二维树状数组：从一维到二维的拓展

实际问题中，我们不仅需要处理一维序列的统计，还会遇到二维矩阵的统计问题，比如：修改矩阵中某个位置的数值、查询子矩阵的和、对某个子矩阵的所有数加 d 等。此时可以将一维树状数组拓展为二维树状数组，核心思想是二维循环，分别对行和列执行 lowbit 操作。

二维树状数组的下标同样从 (1,1) 开始，核心操作是单点修改 + 区间查询、区间修改 + 单点查询、区间修改 + 区间查询，拓展方式和一维一致，下面逐一讲解。

4.1 基础版：单点修改 + 子矩阵查询

解决的问题：给定 n×m 的二维矩阵，执行若干操作，要么修改矩阵中位置(x,y)的数值，要么查询左上角为(x1,y1)、右下角为(x2,y2)的子矩阵的和。

核心思路

单点修改：对位置(x,y)加 k，需要对行和列分别执行向上爬操作，即行i += lowbit(i)，列j += lowbit(j)，直到超过 n 和 m；
前缀和查询：查询从(1,1)到(x,y)的前缀子矩阵和，行i -= lowbit(i)，列j -= lowbit(j)，累加所有节点的和；
子矩阵查询：利用二维前缀和思想，子矩阵(x1,y1)-(x2,y2)的和为：

sum(x2,y2)−sum(x1−1,y2)−sum(x2,y1−1)+sum(x1−1,y1−1)

其中sum(x,y)表示(1,1)到(x,y)的前缀和。

核心代码实现

#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
// 二维数组的大小根据题目调整，比如4200、2060等
const int N = 4200;

int n, m;
LL tree[N][N]; // 二维树状数组

// 单点修改：位置(x,y)加k
void modify(int x, int y, LL k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tree[i][j] += k;
        }
    }
}

// 前缀和查询：(1,1)到(x,y)的和
LL query(int x, int y) {
    LL res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            res += tree[i][j];
        }
    }
    return res;
}

// 子矩阵查询：(x1,y1)到(x2,y2)的和
LL matrix_query(int x1, int y1, int x2, int y2) {
    return query(x2, y2) - query(x1-1, y2) - query(x2, y1-1) + query(x1-1, y1-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    // 初始化二维矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            LL x;
            cin >> x;
            modify(i, j, x);
        }
    }

    // 处理操作，直到文件结束
    int op;
    while (cin >> op) {
        if (op == 1) {
            // 操作1：单点修改，(x,y)加k
            int x, y;
            LL k;
            cin >> x >> y >> k;
            modify(x, y, k);
        } else {
            // 操作2：子矩阵查询
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << matrix_query(x1, y1, x2, y2) << endl;
        }
    }

    return 0;
}

4.2 进阶版 1：区间修改 + 单点查询

解决的问题：对 n×m 矩阵的子矩阵(x1,y1)-(x2,y2)的所有数加 d，查询矩阵中某个位置(x,y)的数值。同样需要结合二维差分思想。

二维差分的核心性质

对原矩阵 a 的子矩阵(x1,y1)-(x2,y2)加 d，等价于对二维差分数组 diff 执行四次单点修改：

原矩阵的位置(x,y)的数值，等价于二维差分数组 diff 的前缀和sum(1,1,x,y)。

因此，问题转化为：用二维树状数组维护二维差分数组 diff，原问题的区间修改变为树状数组的四次单点修改，原问题的单点查询变为树状数组的前缀和查询。

核心代码实现

#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 4200;

int n, m;
LL tree[N][N]; // 二维树状数组维护二维差分数组

void modify(int x, int y, LL k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tree[i][j] += k;
        }
    }
}

LL query(int x, int y) { // 查询diff的前缀和，即原矩阵a[x][y]的值
    LL res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            res += tree[i][j];
        }
    }
    return res;
}

// 区间修改：子矩阵(x1,y1)-(x2,y2)加k
void matrix_modify(int x1, int y1, int x2, int y2, LL k) {
    modify(x1, y1, k);
    if (y2 + 1 <= m) modify(x1, y2 + 1, -k);
    if (x2 + 1 <= n) modify(x2 + 1, y1, -k);
    if (x2 + 1 <= n && y2 + 1 <= m) modify(x2 + 1, y2 + 1, k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    // 初始化原矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            LL x;
            cin >> x;
            matrix_modify(i, j, i, j, x); // 单点初始化
        }
    }

    int op;
    while (cin >> op) {
        if (op == 1) {
            // 操作1：子矩阵加k
            int x1, y1, x2, y2;
            LL k;
            cin >> x1 >> y1 >> x2 >> y2 >> k;
            matrix_modify(x1, y1, x2, y2, k);
        } else {
            // 操作2：单点查询
            int x, y;
            cin >> x >> y;
            cout << query(x, y) << endl;
        }
    }

    return 0;
}

4.3 进阶版 2：区间修改 + 子矩阵查询

这是二维树状数组的最高阶用法，解决的问题是：对矩阵的子矩阵(x1,y1)-(x2,y2)加 k，查询另一个子矩阵(a1,b1)-(a2,b2)的和。该问题需要结合二维差分 + 数学推导，用四个二维树状数组维护不同的信息。

核心推导

设二维原矩阵为 a，二维差分数组为 d，满足

。

我们需要求原矩阵的前缀和S[i][j] = \sum_{x=1}^i \sum_{y=1}^j a[x][y]，将 a [x][y] 用差分数组表示并展开，最终推导可得：

其中所有求和的范围都是x=1到i，y=1到j。

因此，我们需要用四个二维树状数组分别维护：

d[x][y]
d[x][y]×x
d[x][y]×y
d[x][y]×x×y

核心代码实现

同样封装结构体复用代码，代码结构清晰：

#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
const int N = 2060; // 注意数组大小，根据题目调整

int n, m;

// 封装二维树状数组结构体
struct BIT2D {
    LL tree[N][N];
    void modify(int x, int y, LL k) {
        for (int i = x; i <= n; i += lowbit(i)) {
            for (int j = y; j <= m; j += lowbit(j)) {
                tree[i][j] += k;
            }
        }
    }
    LL query(int x, int y) {
        LL res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                res += tree[i][j];
            }
        }
        return res;
    }
}A, B, C, D;
// A: d[x][y]
// B: d[x][y] * x
// C: d[x][y] * y
// D: d[x][y] * x * y

// 二维差分的四次修改，同步更新四个树状数组
void add(int x, int y, LL k) {
    A.modify(x, y, k);
    B.modify(x, y, k * x);
    C.modify(x, y, k * y);
    D.modify(x, y, k * x * y);
}

// 子矩阵(x1,y1)-(x2,y2)加k
void matrix_modify(int x1, int y1, int x2, int y2, LL k) {
    add(x1, y1, k);
    add(x1, y2 + 1, -k);
    add(x2 + 1, y1, -k);
    add(x2 + 1, y2 + 1, k);
}

// 求原矩阵(1,1)到(x,y)的前缀和
LL prefix_sum(int x, int y) {
    LL res = (LL)(x * y + x + y + 1) * A.query(x, y);
    res -= (LL)(y + 1) * B.query(x, y);
    res -= (LL)(x + 1) * C.query(x, y);
    res += D.query(x, y);
    return res;
}

// 求原矩阵子矩阵(a1,b1)-(a2,b2)的和
LL matrix_query(int a1, int b1, int a2, int b2) {
    return prefix_sum(a2, b2) - prefix_sum(a1-1, b2) - prefix_sum(a2, b1-1) + prefix_sum(a1-1, b1-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    // 处理操作，直到文件结束
    int op;
    while (cin >> op) {
        if (op == 1) {
            // 操作1：子矩阵加k
            int x1, y1, x2, y2;
            LL k;
            cin >> x1 >> y1 >> x2 >> y2 >> k;
            matrix_modify(x1, y1, x2, y2, k);
        } else {
            // 操作2：子矩阵查询
            int a1, b1, a2, b2;
            cin >> a1 >> b1 >> a2 >> b2;
            cout << matrix_query(a1, b1, a2, b2) << endl;
        }
    }

    return 0;
}

五、树状数组的核心总结

5.1 一维树状数组操作表

问题类型	核心思路	树状数组数量
单点修改 + 区间查询	直接维护原数组前缀和	1
区间修改 + 单点查询	维护差分数组，转化为单点操作	1
区间修改 + 区间查询	差分 + 数学推导，维护两个信息	2

5.2 二维树状数组操作表

问题类型	核心思路	树状数组数量
单点修改 + 子矩阵查询	直接维护二维前缀和	1
区间修改 + 单点查询	维护二维差分数组	1
区间修改 + 子矩阵查询	二维差分 + 数学推导，维护四个信息	4

5.3 关键注意事项

下标从 1 开始：这是树状数组的硬性要求，x=0 时 lowbit (0) 无意义；
防止溢出：所有区间和 / 矩阵和的操作都要用long long，避免 int 溢出；
lowbit 操作：核心是x & -x，仅在 C++ 中有效（负数以补码存储）；
差分的边界：执行y+1或x2+1的修改时，必须判断是否越界；
大数据加速：C++ 中用ios::sync_with_stdio(false); cin.tie(0);加速输入输出。

总结

树状数组是算法学习中性价比极高的一个数据结构，花少量的时间学习，就能解决大部分区间统计问题。其核心是lowbit 操作和前缀和 / 差分思想，从一维到二维的拓展只是维度的增加，核心逻辑完全一致。学习树状数组的关键是理解其核心性质，而不是死记代码。建议大家先手动推导 lowbit 的计算、节点的维护区间，再结合简单的例子（如 n=8）模拟修改和查询的过程，这样才能真正掌握树状数组的本质。掌握了树状数组后，你可以尝试解决这些经典问题：逆序对、楼兰图腾、HH 的项链等，这些问题都是树状数组的经典应用，能帮助你进一步巩固知识点。希望这篇文章能让你彻底吃透树状数组，在算法竞赛和笔试中轻松解决区间统计问题！如果有疑问，欢迎在评论区留言讨论～ 创作不易，点个赞再走吧！ 🚀

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-02-25，如有侵权请联系 cloudcommunity@tencent.com 删除

原理

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度