首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >【算法提高篇】(十)树状数组模板题全解析:从基础到进阶,刷完这 6 道吃透 BIT

【算法提高篇】(十)树状数组模板题全解析:从基础到进阶,刷完这 6 道吃透 BIT

作者头像
_OP_CHEN
发布2026-03-01 08:45:36
发布2026-03-01 08:45:36
1930
举报
文章被收录于专栏:C++C++

前言

树状数组(BIT)作为算法竞赛中处理区间统计的利器,凭借代码简洁、时间效率高的特点,成为了笔试面试和竞赛中的高频考点。而掌握树状数组的核心,就是吃透各类经典模板题 —— 从最基础的单点修改 + 区间查询,到二维的区间修改 + 区间查询,每一道模板题都是对树状数组核心思想的落地实践。 本文将围绕 6 道经典的树状数组模板题展开,涵盖一维基础、一维进阶、二维基础、二维进阶全类型,每道题都包含题目解析、核心思路、完整 C++ 代码、代码详解,从题目到实现一步到位。刷完这 6 道题,你能彻底掌握树状数组的各类用法,面对同类问题再也不用愁!下面就让我们正式开始吧!


一、模板题 1:树状数组 1 - 单点修改,区间查询

题目链接:https://loj.ac/p/130

题目信息

  • 来源:LibreOJ 130
  • 难度:★★★
  • 核心考点:一维树状数组最基础用法,单点修改 + 区间和查询

题目描述

给定数列 a1​,a2​,...,an​,依次进行 q 个操作,操作分两类:

  1. 1 i x:将 ai​ 加上 x;
  2. 2 l r:求区间 [l,r] 的所有元素和,即 ∑i=lr​ai​。

输入要求:1≤n,q≤106,∣ai​∣,∣x∣≤106,1≤l≤r≤n。

输出要求:对于每个第二类操作,输出对应的区间和。

核心思路

这是树状数组的入门必刷题,直接考察树状数组的两个核心操作:

  1. 单点修改:位置 x 增加 k,从 x 开始沿父节点(i+=lowbit(i))向上更新树状数组节点;
  2. 区间查询:利用前缀和思想,区间 [l,r] 的和 = 前缀和 [1,r] - 前缀和 [1,l−1],而前缀和通过 i−=lowbit(i) 向前跳累加得到。

关键注意:数据范围达到 106,必须用long long存储树状数组和结果,防止 int 溢出;同时需要加速 C++ 的输入输出,避免超时。

完整 C++ 代码

代码语言:javascript
复制
#include <iostream>
using namespace std;

// lowbit操作:保留二进制最右边的1
#define lowbit(x) (x & -x)
// 数据范围1e6+10,用long long防止溢出
typedef long long LL;
const int N = 1e6 + 10;

int n, q;
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 sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

int main() {
    // 加速输入输出,处理1e6级数据必备
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    // 初始化树状数组:读入每个数,相当于单点修改加a[i]
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        modify(i, x);
    }
    
    // 处理q次操作
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            // 操作1:单点修改,位置x加y
            modify(x, y);
        } else {
            // 操作2:区间查询,[x,y]的和 = query(y) - query(x-1)
            cout << query(y) - query(x - 1) << endl;
        }
    }
    
    return 0;
}

代码详解

  1. lowbit 宏定义x & -x 是树状数组的核心,利用补码特性快速获取最右侧的 1;
  2. 数据类型LL 别名long long,树状数组tree和查询结果都用其存储,避免大数溢出;
  3. 输入输出加速ios::sync_with_stdio(false); cin.tie(0); 关闭 cin 与 stdio 的同步,解除 cin 和 cout 的绑定,大幅提升输入速度;
  4. 初始化:树状数组初始为 0,读入原数组的每个元素a[i],等价于对位置i执行单点修改加a[i]
  5. 操作处理:根据操作类型分支,单点修改直接调用modify,区间查询通过两个前缀和的差得到结果。

二、模板题 2:树状数组 2 - 区间修改,单点查询

题目链接:https://loj.ac/p/131

题目信息

  • 来源:LibreOJ 131
  • 难度:★★★
  • 核心考点:一维树状数组 + 差分思想,区间修改 + 单点值查询

题目描述

给定数列 a1​,a2​,...,an​,依次进行 q 个操作,操作分两类:

  1. 1 l r x:将区间[l,r]的所有元素都加上x;
  2. 2 i:求ai​的当前值。

输入要求:1≤n,q≤106,∣ai​∣,∣x∣≤106,1≤l≤r≤n。

输出要求:对于每个第二类操作,输出对应的元素值。

核心思路

树状数组本身不直接支持区间修改,需要结合一维差分思想做转化,这是树状数组的经典进阶用法:

  1. 差分性质:对原数组a的区间[l,r]加x,等价于对差分数组d执行:d[l]+=x,d[r+1]−=x(若r+1≤n)
  2. 单点查询转化:原数组的单点值a[i],等价于差分数组d的前缀和[1,i];
  3. 树状数组维护对象:用树状数组维护差分数组d,则原问题的区间修改转化为树状数组的两次单点修改,原问题的单点查询转化为树状数组的前缀和查询

完整 C++ 代码

代码语言:javascript
复制
#include <iostream>
using namespace std;

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

int n, q;
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] = 原数组a[x]的值
LL query(int x) {
    LL sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

// 原数组区间[l,r]加k:转化为差分数组的两次单点修改
void interval_modify(int l, int r, LL k) {
    modify(l, k);
    if (r + 1 <= n) {
        modify(r + 1, -k);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    // 初始化:原数组a[i] = 差分数组前缀和,等价于对[i,i]区间加a[i]
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        interval_modify(i, i, x);
    }
    
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 操作1:区间修改[L,R]加x
            int l, r;
            LL x;
            cin >> l >> r >> x;
            interval_modify(l, r, x);
        } else {
            // 操作2:单点查询a[x]
            int x;
            cin >> x;
            cout << query(x) << endl;
        }
    }
    
    return 0;
}

代码详解

  1. 区间修改封装:将差分数组的两次单点修改封装为interval_modify,增加代码可读性,同时判断r+1≤n,避免下标越界;
  2. 初始化技巧:原数组的每个元素a[i],可以看作是对差分数组执行区间[i,i]加a[i],直接调用interval_modify即可完成初始化;
  3. 单点查询:直接调用query(x),得到的差分数组前缀和就是原数组a[x]的当前值。

三、模板题 3:树状数组 3 - 区间修改,区间查询

题目链接:https://loj.ac/p/132

题目信息

  • 来源:LibreOJ 132
  • 难度:★★★
  • 核心考点:一维树状数组 + 差分 + 数学推导,区间修改 + 区间和查询(树状数组一维最高阶用法)

题目描述

给定数列 a1​,a2​,...,an​,依次进行 q 个操作,操作分两类:

  1. 1 l r x:将区间[l,r]的所有元素都加上x;
  2. 2 l r:求区间[l,r]的所有元素和。

输入要求:1≤n,q≤106,∣ai​∣,∣x∣≤106,1≤l≤r≤n。

输出要求:对于每个第二类操作,输出对应的区间和。

核心思路

这是一维树状数组的最高阶模板题,需要结合差分 + 数学公式推导,用两个树状数组分别维护不同的信息,是竞赛中的高频考点。

关键数学推导

设原数组为a,差分数组为d(

),原数组的前缀和

,将a[j]用差分数组展开并化简:

令:

则原数组前缀和

,原数组区间和

实现思路

  1. 定义两个树状数组,分别维护d[k]和d[k]×(k−1);
  2. 原数组区间[l,r]加x,转化为差分数组的两次单点修改,同步更新两个树状数组;
  3. 先求前缀和S[r]和S[l−1],再做差得到区间[l,r]的和。

为了代码复用,将树状数组封装为结构体,是竞赛中的常用写法。

完整 C++ 代码

代码语言:javascript
复制
#include <iostream>
using namespace std;

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

int n, q;
LL d[N]; // 差分数组

// 封装树状数组结构体,复用modify和query操作
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 sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }
} 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 >> q;
    // 初始化原数组,构建差分数组d
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        d[i] += x;
        d[i + 1] -= x;
    }
    // 用差分数组初始化两个树状数组
    for (int i = 1; i <= n; i++) {
        A.modify(i, d[i]);
        B.modify(i, d[i] * (i - 1));
    }
    
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            // 操作1:区间[l,r]加k
            LL k;
            cin >> k;
            interval_modify(l, r, k);
        } else {
            // 操作2:查询区间[l,r]的和
            cout << interval_query(l, r) << endl;
        }
    }
    
    return 0;
}

代码详解

  1. 结构体封装:将树状数组的modifyquery封装为BIT结构体,A 和 B 两个树状数组直接复用,避免重复代码;
  2. 差分数组初始化:先手动构建差分数组d,再分别将d[i]和d[i]∗(i−1)插入两个树状数组;
  3. 区间修改同步更新:对 A 和 B 执行两次单点修改,其中 B 的修改值需要计算k∗(x−1)−k∗y,严格遵循推导公式;
  4. 前缀和计算:强制转换(LL)i,避免 int 和 long long 混合运算导致的溢出。

四、模板题 4:二维树状数组 1 - 单点修改,区间查询

题目链接:https://loj.ac/p/133

题目信息

  • 来源:LibreOJ 133
  • 难度:★★★
  • 核心考点:二维树状数组基础用法,单点修改 + 子矩阵和查询

题目描述

给出一个n×m的零矩阵A,完成若干操作,操作分两类:

  1. 1 x y k:将元素Ax,y​自增k;
  2. 2 a b c d:查询左上角为(a,b)、右下角为(c,d)的子矩阵内所有数的和。

输入要求:输入操作直到文件结束,矩阵下标从 1 开始。

输出要求:对于每个第二类操作,输出对应的子矩阵和。

核心思路

二维树状数组是一维树状数组的二维拓展,核心思路是二维循环,分别对行和列执行 lowbit 操作,本质还是前缀和思想:

  1. 单点修改:对位置(x,y)加k,行i+=lowbit(i),列j+=lowbit(j),双重循环更新树状数组;
  2. 二维前缀和查询:查询(1,1)到(x,y)的前缀子矩阵和,行i−=lowbit(i),列j−=lowbit(j),双重循环累加;
  3. 子矩阵和查询:利用二维前缀和公式,子矩阵(a,b)−(c,d)的和 =query(c,d)−query(a−1,d)−query(c,b−1)+query(a−1,b−1)(容斥原理,减去多余部分,加回重复减去的部分)。

完整 C++ 代码

代码语言:javascript
复制
#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
// 二维数组大小根据题目调整,4200满足大部分测试用例
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 sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            sum += tree[i][j];
        }
    }
    return sum;
}

// 查询子矩阵和:(a,b) -> (c,d)
LL matrix_query(int a, int b, int c, int d) {
    return query(c, d) - query(a-1, d) - query(c, b-1) + query(a-1, b-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    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:查询子矩阵(a,b)-(c,d)的和
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            cout << matrix_query(a, b, c, d) << endl;
        }
    }
    
    return 0;
}

代码详解

  1. 二维数组大小:设为 4200,满足 LibreOJ 该题的所有测试用例,可根据实际题目调整;
  2. 双重循环:所有操作都是行和列的双重循环,严格遵循一维树状数组的操作逻辑,只是增加了一个维度;
  3. 容斥公式matrix_query严格实现二维前缀和的容斥原理,是二维子矩阵查询的核心,必须牢记;
  4. 零矩阵初始化:题目中矩阵初始为 0,树状数组默认初始化为 0,无需额外操作。

五、模板题 5:二维树状数组 2 - 区间修改,单点查询

题目链接:https://loj.ac/p/134

题目信息

  • 来源:LibreOJ 134
  • 难度:★★★
  • 核心考点:二维树状数组 + 二维差分,区间修改 + 单点值查询

题目描述

给出一个n×m的零矩阵A,完成若干操作,操作分两类:

  1. 1 a b c d k:将左上角为(a,b)、右下角为(c,d)的子矩阵内所有数自增k;
  2. 2 x y:查询元素Ax,y​的当前值。

输入要求:输入操作直到文件结束,矩阵下标从 1 开始。

输出要求:对于每个第二类操作,输出对应的元素值。

核心思路

与一维区间修改 + 单点查询的思路一致,结合二维差分思想将区间修改转化为单点修改,是二维树状数组的经典进阶用法。

二维差分核心性质

对原矩阵A的子矩阵(a,b)−(c,d)加k,等价于对二维差分数组diff执行四次单点修改

原矩阵的单点值Ax,y​,等价于二维差分数组diff的前缀子矩阵和(1,1)−(x,y)。

实现思路

  1. 用二维树状数组维护二维差分数组diff
  2. 原矩阵的区间修改转化为树状数组的四次单点修改
  3. 原矩阵的单点查询转化为树状数组的二维前缀和查询

完整 C++ 代码

代码语言:javascript
复制
#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]; // 二维树状数组维护二维差分数组

// 单点修改:(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;
        }
    }
}

// 查询二维前缀和 = 原矩阵A[x][y]的值
LL query(int x, int y) {
    LL sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            sum += tree[i][j];
        }
    }
    return sum;
}

// 原矩阵子矩阵(a,b)-(c,d)加k,转化为四次单点修改
void matrix_modify(int a, int b, int c, int d, LL k) {
    modify(a, b, k);
    if (d + 1 <= m) modify(a, d + 1, -k);
    if (c + 1 <= n) modify(c + 1, b, -k);
    if (c + 1 <= n && d + 1 <= m) modify(c + 1, d + 1, k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    int op;
    while (cin >> op) {
        if (op == 1) {
            // 操作1:子矩阵(a,b)-(c,d)加k
            int a, b, c, d;
            LL k;
            cin >> a >> b >> c >> d >> k;
            matrix_modify(a, b, c, d, k);
        } else {
            // 操作2:单点查询A[x][y]
            int x, y;
            cin >> x >> y;
            cout << query(x, y) << endl;
        }
    }
    
    return 0;
}

代码详解

  1. 四次单点修改封装:将二维差分的四次修改封装为matrix_modify,增加代码可读性,同时对边界进行判断,避免下标越界;
  2. 单点查询:直接调用query(x,y),得到的二维前缀和就是原矩阵Ax,y​的当前值;
  3. 零矩阵初始化:树状数组默认初始化为 0,无需额外操作,符合题目中零矩阵的要求。

六、模板题 6:二维树状数组 3 - 区间修改,区间查询

题目链接:https://loj.ac/p/135

题目信息

  • 来源:LibreOJ 135
  • 难度:★★★★
  • 核心考点:二维树状数组 + 二维差分 + 数学推导,区间修改 + 子矩阵和查询(树状数组二维最高阶用法)

题目描述

给定一个N×M的零矩阵,完成若干操作,操作分两类:

  1. 1 a b c d x:将左上角为(a,b)、右下角为(c,d)的子矩阵全部加上x;
  2. 2 a b c d:查询左上角为(a,b)、右下角为(c,d)的子矩阵内所有数的和。

输入要求:输入操作直到文件结束,矩阵下标从 1 开始。

输出要求:对于每个第二类操作,输出对应的子矩阵和。

核心思路

这是二维树状数组的最高阶模板题,难度比一维更高,需要结合二维差分 + 复杂的数学公式推导,用四个二维树状数组分别维护不同的信息,是竞赛中的难点也是重点。

关键数学推导

设原矩阵为A,二维差分数组为d(

),原矩阵的前缀子矩阵和

,将A[x][y]用差分数组展开并化简,最终得到:

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

实现思路

  1. 定义四个二维树状数组,分别维护:d[x][y]、d[x][y]×x、d[x][y]×y、d[x][y]×x×y;
  2. 原矩阵的子矩阵修改,转化为二维差分数组的四次单点修改,同步更新四个树状数组;
  3. 先求原矩阵的前缀子矩阵和S[i][j],再利用二维容斥公式求任意子矩阵的和。

同样将二维树状数组封装为结构体,简化代码。

完整 C++ 代码

代码语言:javascript
复制
#include <iostream>
using namespace std;

#define lowbit(x) (x & -x)
typedef long long LL;
// 二维数组大小调整为2060,满足题目测试用例
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 sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
} 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);
}

// 原矩阵子矩阵(a,b)-(c,d)加k,转化为四次add操作
void matrix_modify(int a, int b, int c, int d, LL k) {
    add(a, b, k);
    add(a, d + 1, -k);
    add(c + 1, b, -k);
    add(c + 1, d + 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;
}

// 求原矩阵子矩阵(a,b)-(c,d)的和,容斥原理
LL matrix_query(int a, int b, int c, int d) {
    return prefix_sum(c, d) - prefix_sum(a-1, d) - prefix_sum(c, b-1) + prefix_sum(a-1, b-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    int op;
    while (cin >> op) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (op == 1) {
            // 操作1:子矩阵加k
            LL k;
            cin >> k;
            matrix_modify(a, b, c, d, k);
        } else {
            // 操作2:查询子矩阵和
            cout << matrix_query(a, b, c, d) << endl;
        }
    }
    
    return 0;
}

代码详解

  1. 四个树状数组:严格对应推导公式中的四个维护项,命名 A、B、C、D 便于记忆;
  2. add 函数封装:将四次单点修改的同步更新封装为add,避免重复代码,减少出错概率;
  3. 前缀和计算:严格遵循推导公式,所有乘法操作强制转换为long long,防止溢出;
  4. 容斥原理:子矩阵查询的matrix_query与二维基础版一致,复用二维前缀和的容斥公式。

七、六大模板题核心总结

题型与树状数组数量对应表

题号

题型

维度

树状数组数量

核心思想

1

单点修改 + 区间查询

一维

1

直接维护原数组前缀和

2

区间修改 + 单点查询

一维

1

一维差分 + 维护差分数组

3

区间修改 + 区间查询

一维

2

一维差分 + 数学推导 + 双数组维护

4

单点修改 + 子矩阵查询

二维

1

二维前缀和 + 双重循环

5

区间修改 + 单点查询

二维

1

二维差分 + 四次单点修改

6

区间修改 + 子矩阵查询

二维

4

二维差分 + 数学推导 + 四数组维护

通用解题技巧

  1. 溢出处理:所有树状数组和结果优先用long long,尤其是数据范围≥1e5 的情况,避免 int 溢出;
  2. 输入输出加速:C++ 中处理 1e6 级数据时,必须加ios::sync_with_stdio(false); cin.tie(0);,否则会超时;
  3. 边界判断:差分操作中涉及r+1、d+1的位置,必须判断是否≤n/m,避免下标越界;
  4. 结构体封装:多树状数组场景下,封装为结构体可大幅减少重复代码,提升可读性;
  5. 公式牢记:一维 / 二维区间修改 + 区间查询的推导公式是核心,必须理解并牢记,而非死记硬背。

学习建议

  1. 由浅入深:先掌握一维基础(题 1),再学一维差分(题 2),最后攻克一维高阶(题 3),二维部分同理;
  2. 手动推导:不要直接抄代码,手动推导差分和前缀和的公式,理解每一步的含义;
  3. 调试测试:每道题都结合示例测试用例手动模拟执行,观察树状数组的更新和查询过程;
  4. 拓展练习:掌握这 6 道模板题后,可尝试洛谷的逆序对、楼兰图腾等题,将模板应用到实际场景。

总结

树状数组的模板题看似繁多,实则核心思想高度统一 ——lowbit 操作+前缀和 / 差分思想,所有的进阶用法都是这两个核心的延伸。这 6 道模板题覆盖了树状数组的所有经典用法,是打通树状数组的 “通关宝典”。 刷完这 6 道题,你不仅能掌握树状数组的各类实现,更能理解其背后的设计思想,面对竞赛和笔试中的区间统计问题,能快速选择最优的树状数组解法。建议大家把每道题的代码手写 2-3 遍,直到能独立默写并解释每一行的含义,真正做到吃透树状数组! 如果觉得这篇文章对你有帮助,欢迎点赞、收藏、关注~后续会继续更新树状数组的拓展应用题解析,敬请期待!🚀

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2026-02-26,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 一、模板题 1:树状数组 1 - 单点修改,区间查询
    • 题目信息
    • 题目描述
    • 核心思路
    • 完整 C++ 代码
    • 代码详解
  • 二、模板题 2:树状数组 2 - 区间修改,单点查询
    • 题目信息
    • 题目描述
    • 核心思路
    • 完整 C++ 代码
    • 代码详解
  • 三、模板题 3:树状数组 3 - 区间修改,区间查询
    • 题目信息
    • 题目描述
    • 核心思路
      • 关键数学推导
      • 实现思路
    • 完整 C++ 代码
    • 代码详解
  • 四、模板题 4:二维树状数组 1 - 单点修改,区间查询
    • 题目信息
    • 题目描述
    • 核心思路
    • 完整 C++ 代码
    • 代码详解
  • 五、模板题 5:二维树状数组 2 - 区间修改,单点查询
    • 题目信息
    • 题目描述
    • 核心思路
      • 二维差分核心性质
      • 实现思路
    • 完整 C++ 代码
    • 代码详解
  • 六、模板题 6:二维树状数组 3 - 区间修改,区间查询
    • 题目信息
    • 题目描述
    • 核心思路
      • 关键数学推导
      • 实现思路
    • 完整 C++ 代码
    • 代码详解
  • 七、六大模板题核心总结
    • 题型与树状数组数量对应表
    • 通用解题技巧
    • 学习建议
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档