c++树形数据结构——树状数组，算法必看哟！！！
以最浅显易懂的语言深入讲解树状数组，配有例题加强练习（有代码详解）！参加算法比赛或对算法感兴趣的兄弟集美必看哟！
目录
注：本文题目均来自蓝桥杯官网公开题目，仅用于算法学习和技术讨论。
一，简介
树状数组（Fenwick Tree）是一种高效的数据结构，主要用于解决区间查询和单点更新问题，时间复杂度均为 O(logn)，适用于数组长度固定且需要频繁进行这两种操作的场景。是一种可以“动态求区间和”的树形数据结构，但并没有真正的构造出边来，所以是“树状的”。
以下是其核心知识点：
1. 基本原理
（1）结构特点：树状数组通过将数组元素按照二进制低位的 “1” 进行分层存储，形成一个树形结构（非传统二叉树），每个节点负责存储特定区间的前缀和。
2，核心操作：
（1）单点更新：修改某个元素的值，并更新其所有相关父节点。
（2）前缀和查询：计算从数组第一个元素到指定位置的前缀和，进而推导出区间和。
二，区分与前缀和的区别和联系
1. 时间复杂度
操作 前缀和 树状数组
初始化 O(n) O(nlogn)或 O(n)
单点修改O(n) O(logn)
区间查询O(1) O(logn)
区间修改O(n)(需配合差分) O(logn)
2. 空间复杂度
前缀和：
O(n) （需要额外存储前缀和数组）。
树状数组：
O(n) （直接在原数组基础上维护树状结构）。
3. 适用场景
前缀和：适合静态数组（不涉及修改），频繁查询区间和。
例如：多次查询数组中任意子数组的和。
树状数组：适合动态数组（需频繁修改和查询）。
例如：单点修改后快速查询前缀和、区间修改与查询（需配合差分）。
4. 实现灵活性
前缀和：仅支持区间和查询，难以扩展到其他操作（如区间最大值）。
树状数组：可扩展支持多种操作，如区间最大值 / 最小值（需调整更新策略）。
三，基本步骤演示
1，lowbit操作
是一种位运算操作，用于计算出数字的二进制表达中的最低位的1以及后面所有的0
int lowbit(int x){return x&-x}; o(1)
int lowbit(int x)//用于快速计算一个整数在二进制表示下最低位的 1 所对应的值
{
return x & -x;
}
/*x = 6 → 二进制: 0000 0110
~x → 二进制: 1111 1001
~x + 1 = -x → 二进制: 1111 1010
x & (-x) → 二进制: 0000 0010 → 十进制: 2*/
//lowbit(x) 的值等于 2^k，其中 k 是 x 的二进制末尾连续 0 的个数2，lowbit和树状数组t[]的联系
int t[](tree),大小和我们需要维护的数组大小一样即可
树状数组的结构：t[i]存储a[i]中一段区间和：
定义t[i]存储以i结尾，且区间大小为lowbit(i)的区间和
t[j]=sigma(j=(i-lowbit(i)+1)~~~i)a[j],可以将[i-lowbit(i)+1,i]称为“管辖区间”
例子：a1 a2 a3 a4.....................an(分别为1 2 3 4 ..........n)
t1-->1 t2-->[1,2] t3-->3 t4-->[1,4] t5-->5 t6-->[5,6] t7-->7 t8-->[1,8]
如何进行单点修改？举个例子：假设要修改a[3],包含a[3]的区间有t3 t4 t8,所以应该修改这3个节点
只需进行+lowbit操作即可（二进制性质）
3+lowbit(3)=4 4+lowbit(4)=8......就是原来的编号加上他所管辖的区域等于后面与之相连的编号！！！
怎么进行区间查询？
第一步：将其拆为两个区间的差，例子：假设要查询[3,7]的和，就要拆分为sum[1,7]-sum[1,2]
由上图，我们要求sum[1,7],结果为t[7]+t[6]+t[4],通过lowbit即可得到：
7-lowbit(7)=6 6-lowbit(6)=4 就是原来的编号减去他所管辖的区域等于前面与之相连的编号！！！
于是可以直接得到树状数组最重要的两个函数update()和getpre()！
1，update函数
//给a[k]增加x
void update(int k, int x)
{
for (int i = k; i <= n; i += lowbit(i))t[i] += x;
//解释：把a[k]增加x，相当于把与a[k]相关的几个区间和都要加上x。所以t[i]要加上x
}2，getprefix函数
//返回区间[1,k]的和
int getprefix(int k)
{
int res = 0;
for (int i = k; i >=1; i -= lowbit(i))res += t[i];
//以管辖区间为单位依次向前加上t[i]!!!就返回的是区间[1,k]的和！
}四，例题详解
例题1：蓝桥杯官网——殷老师排队
问题描述
体育课上，殷老师正在给学生们排队，排完队后他发现这些学生有些不同。每个学生都有一个魅力值 ai 和愉悦值 bi，愉悦值的计算公式如下：
作为一名优秀的教师他一眼就可以看出学生们的魅力值，但随着时间的推移魅力值可能会发生变化，所以愉悦值也会发生变化。在排队的过程中会有 n 个事件，这 n 个事件共分为两种情况：
- 第 x 个学生的魅力值变为 y。
- 殷老师想查看第 x 个学生的愉悦值。
殷老师太忙了，所以你可以帮他计算某个学生的愉悦值吗？
输入格式
第一行包含两个整数 n,m，表示学生的个数和事件的个数。
第二行包含 n 个数表示每个学生的魅力值。
之后每一个操作的开头都输入一个数字 op 表示事件的类型，如果 op=1 则输入两个整数 x,z 表示将第 x 个学生的魅力值修改为 z；若 op=2 则输入一个整数 x 表示询问从第 x 个学生的愉悦值。
输出格式
对于每个操作 2 输出一个数字 ans 表示学生的愉悦值。
样例输入
10 10
74 56 25 77 55 36 50 89 42 15
1 2 38
2 8
2 1
2 1
1 3 11
2 1
2 6
2 8
1 5 47
2 3
样例输出
147
-239
-239
-253
-23
161
189
数据规模
对于所有评测数据，1≤n,m≤10^5，1≤op≤2，1≤x≤n，0≤z≤10^9。
代码详解！
方法一：正确方法，树状数组
#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], t[N], n, m;
//首先，可以将式子转换：
//bi=(i-1-1+1)ai-sigma(j=1 j=i-1)aj+sigma(j=i+1 j=n)aj-(n-i-1+1)ai
//bi=(2i-n-1)ai-sigma(j=1 j=i-1)aj+sigma(j=i+1 j=n)aj
int lowbit(int x)
{
return x & -x;
}
void update(int k, ll x)//单点修改,将a[k]加上x
{
a[k] += x;
for (int i = k; i <= n; i += lowbit(i))t[i] += x;
}
ll getprefix(int k)//求区间[1,k]的和
{
ll res = 0;
for (int i = k; i >= 1; i -= lowbit(i))res += t[i];
return res;
}
ll getsum(int l, int r)//求区间[l,r]的和
{
return getprefix(r) - getprefix(l - 1);
}
ll b(int i)//求愉悦值
{
return (2 * i - n - 1) * a[i] - getsum(1, i - 1) + getsum(i + 1, n);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int x; cin >> x;
update(i, x);
//cin>>a[i];update(i,a[i]);
}
while (m--)
{
int op; cin >> op;
if (op == 1)
{
ll x, y; cin >> x >> y;
update(x, -a[x] + y);//将a[x]加上-a[x]+y,即将a[x]变成y
}
else
{
int x; cin >> x;
cout << b(x) << '\n';
}
}
return 0;
}
///若改用直接输入数组的形式，则太麻烦了，还不如前者方便
#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], t[N], n, m, g[N];
//首先，可以将式子转换：
//bi=(i-1-1+1)ai-sigma(j=1 j=i-1)aj+sigma(j=i+1 j=n)aj-(n-i-1+1)ai
//bi=(2i-n-1)ai-sigma(j=1 j=i-1)aj+sigma(j=i+1 j=n)aj
int lowbit(int x)
{
return x & -x;
}
void update(int k, ll x) // 单点修改，将a[k]设为x
{
g[k] += x; // 更新a[k]
for (int i = k; i <= n; i += lowbit(i)) t[i] += x; // 更新树状数组
}
ll getprefix(int k)//求区间[1,k]的和
{
ll res = 0;
for (int i = k; i >= 1; i -= lowbit(i))res += t[i];
return res;
}
ll getsum(int l, int r)//求区间[l,r]的和
{
return getprefix(r) - getprefix(l - 1);
}
ll b(int i)//求愉悦值
{
return (2 * i - n - 1) * g[i] - getsum(1, i - 1) + getsum(i + 1, n);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
//int x;cin>>x;
//update(i,x);
cin >> a[i]; update(i, a[i]);
}
while (m--)
{
int op; cin >> op;
if (op == 1)
{
ll x, y; cin >> x >> y;
update(x, y - g[x]);//将a[x]加上-a[x]+y,即将a[x]变成y
}
else
{
int x; cin >> x;
cout << b(x) << '\n';
}
}
return 0;
}大家可能会好奇，树状数组的相关操作和前缀和差分具有相似之处。那么这题可以用普通的前缀和和差分方法做吗？其实是可以的。只是时间复杂度较大，只能通过80%的案例。
请看代码：
方法二，普通前缀和差分方法，时间复杂度高
#include <iostream>
#include<cstring>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], diff[N], prefix[N], n;
//求前缀和
void pre_fix()
{
memset(prefix, 0, sizeof(prefix));
for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
}
//update(i,k)将a[i]加上k
void update(int i, int k)
{
diff[i] += k;
diff[i + 1] -= k;
//前缀和还原
for (int i = 1; i <= n; i++) a[i] = a[i - 1] + diff[i];
pre_fix();
}
//前缀和：求[1,k]的和
ll getprefix(int k)
{
return prefix[k];
}
ll getsum(int l, int r)
{
return getprefix(r) - getprefix(l - 1);
}
ll b(int i)
{
return (2 * i - n - 1) * a[i] - getsum(1, i - 1) + getsum(i + 1, n);
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
//先初始差分数组：
for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1];
//初始前缀和数组
for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
while (m--)
{
int op; cin >> op;
if (op == 1)
{
int x, y; cin >> x >> y;
update(x, y - a[x]);
}
else if (op == 2)
{
int x; cin >> x;
cout << b(x) << '\n';
}
}
return 0;
}例题2：23年蓝桥杯真题——异或和
问题描述
给一棵含有 n 个结点的有根树，根结点为 1，编号为 i 的点有点权 ai（i∈[1,n]）。现在有两种操作，格式如下：
- 1 x y：该操作表示将点 x 的点权改为 y。
- 2 x：该操作表示查询以结点 x 为根的子树内的所有点的点权的异或和。
现有长度为 m 的操作序列，请对于每个第二类操作给出正确的结果。
输入格式
输入的第一行包含两个正整数 n,m，用一个空格分隔。
第二行包含 n 个整数 a1,a2,…,an，相邻整数之间使用一个空格分隔。
接下来 n−1 行，每行包含两个正整数 ui,vi，表示结点 ui 和 vi 之间有一条边。
接下来 m 行，每行包含一个操作。
输出格式
输出若干行，每行对应一个查询操作的答案。
样例输入
4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2
样例输出
4
5
6
评测用例规模与约定
对于 30% 的评测用例，n,m≤1000；
对于所有评测用例，1≤n,m≤100000，0≤ai,y≤100000，1≤ui,vi,x≤n。
代码详解！
方法一：树状数组
#include <iostream>
#include <vector>
using ll=long long;
using namespace std;
const int N=1e5+9;
ll a[N],t[N],idx[N],dfn[N],sz[N];
vector<int>g[N];
int n,m,tot=0;
int lowbit(int x)
{
return x & -x;
}
void update(int k,int x)
{
for(int i=k;i<=n;i+=lowbit(i)) t[i]^=x;
}
int query(int k)
{
int res=0;
for(int i=k;i>0;i-=lowbit(i)) res^=t[i];
return res;
}
void dfs(int x,int fa)
{
dfn[x]=++tot;
idx[dfn[x]]=x;
sz[x]=1;
for(const auto&y:g[x])
{
if(y==fa) continue;
dfs(y,x);
sz[x]+=sz[y];
}
}
int main()
{
int q; cin >> n >> q;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i < n; i++)
{
int u, v; cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)update(dfn[i], a[i]);
while (q--)
{
int op; cin >> op;
if (op == 1)//更新x为y
{
int x, y; cin >> x >> y;
int val = query(dfn[x]) ^ query(dfn[x] - 1);
//在初始状态（未进行任何更新操作时），query(dfn[x]) ^ query(dfn[x] - 1) 等于 a[x]；
// 但在经过更新操作后，它等于节点 x 当前的最新值（而非初始的 a[x]）！！！！！！
//val 表示的是 DFS 序中某一点的当前点权值
/*query(dfn[x]) 返回区间 [1, dfn[x]] 的异或和。
query(dfn[x]-1) 返回区间 [1, dfn[x]-1] 的异或和。
两者异或后，得到的 val 就是位置 dfn[x] 对应的点权（即节点 x 的当前值）。*/
update(dfn[x], val ^ y);//这一步的意思就是将dfn[x]所代表的点权（就是val）在和val^y进行异或运算
//val^vla^y=0^y=y，至此，val被替换成y！！！
}
else//求异或和
{
int x; cin >> x;
int l = dfn[x], r = dfn[x] + sz[x] - 1;
int ans = query(r) ^ query(l - 1);//类似prefix
//ans表示l到r的异或和
/*异或（XOR，符号为 ^）具有以下关键性质：
交换律：a ^ b = b ^ a
结合律：(a ^ b) ^ c = a ^ (b ^ c)
自反性：a ^ a = 0（任何数异或自身为 0）
单位元：a ^ 0 = a（任何数异或 0 等于自身）*/
//定义 prefix[i] 为前 i 个元素的异或和：
//prefix[i] = a[1] ^ a[2] ^ ... ^ a[i]
//则区间 [l, r] 的异或和可表示为：
//a[l] ^ a[l+1] ^ ... ^ a[r] = prefix[r] ^ prefix[l-1]
//前面的1到l-1部分由交换律a[i]^a[i]=0,都抵消了
cout << ans << '\n';
}
}
return 0;
}方法2：更加简单直观的方法
//////方法2：更加直观
//需要设置两个数组:in_[N]和out[N],in_[i]表示第i个结点的入序,out[i]表示第i个结点的出序
//对树进行一次dfs,在进入函数时更新入序,在退出函数时更新出序
//对于以结点x为根结点的子树,其所有子结点的dfs序都将位于[ in_[x],out[x] ]间
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>edge[N];//edge[i]存储第i个结点的邻接点
int in_[N], out[N];//in_[i]存储第i个结点的入序,out[i]存储第i个结点的出序
int weight[N];//weight[i]存储的第i个结点的值(原始数据)
int tot = 0;//记录dfs序的变量
int seq[N];//seq[i]为dfs序中第i个结点的权值
int n, m;
void dfs(int u, int father)//对结点u进行dfs,其父结点为father
{
in_[u] = ++tot;//进入函数,计算入序,tot先自加
seq[tot] = weight[u];//第tot个结点的权值是weight[u]
for (const auto& v : edge[u])//遍历u的邻接点v
{
if (v == father)continue;
dfs(v, u);
}
out[u] = tot;//退出函数,更新u的出序,tot无需自加
}
/*in_[u]：表示节点u在 DFS 遍历中首次被访问的时间戳（即进入节点u的时间）。
这个时间戳是唯一的，并且在整个 DFS 过程中严格递增。
out[u]：表示节点u的所有子树都被遍历完成后，退出节点u的时间戳。
由于 DFS 会递归遍历当前节点的所有子节点，
因此out[u]实际上等于当前节点及其所有子树的节点总数（从in_[u]开始的连续区间）。*/
/*入序（in_）：在递归进入节点u时立即记录，确保每个节点的入序唯一且递增。
出序（out）：在遍历完所有子节点后记录，此时的tot值恰好等于当前子树的最后一个节点的入序，
因此out[u]表示子树区间的右端点。*/
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &weight[i]);//输入n个结点的原始值
for (int i = 1; i < n; i++)//输入n-1条无向边
{
int u, v; scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1, 0);//从1号结点开始进行一次dfs,求出所有结点的dfs序,填写in_数组和out数组
//此后我们只按照dfs序处理结点,原始的weight不再使用
while (m--)
{
int op, x, y;
scanf("%d", &op);
if (op == 1)//把第x个结点的权值改为y
{
scanf("%d%d", &x, &y);
seq[in_[x]] = y;//转化为将第in_[x]个结点(dfs序下)的权值改为y
}
else if (op == 2)
{
scanf("%d", &x);//查询以x为根的子树的异或和
int ans = 0;
for (int i = in_[x]; i <= out[x]; i++)//转化为求区间[ in_[x],out[x] ]的异或和
{
ans = ans ^ seq[i];
}
printf("%d\n", ans);
//注意这里使用的是暴力求前缀和的方式而不是前缀和数组
//这是因为本题是一边修改一边查询,前缀和数组无法实现动态修改和查询
//如果要提高效率可以使用线段树,可在O(logn)时间复杂度内完成查询
//但对于本题,暴力求异或和即可通过全部测试点
}
}
return 0;
}okkkkkkkk了，制作不易，如果觉得不错，不要忘了点赞+关注+收藏哟！！！
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
15
0- 0
已为社区贡献6条内容
所有评论(0)