#创作计划 浅谈树状数组
2025-10-10 18:46:13
发布于:浙江
UPD:更新了树状数组倍增求 大值(并嘲讽了桶蕊 7),并修改了有序表问题。
前言
本文主要在洛谷发布,且本文非常完善,涵盖了你知道和不知道的东西。
强烈谴责某些用户写的树状数组文章纯纯误导我这种蒟蒻!
注:下文中的 数组即为树状数组, 为原数组。
概念
完了有点忘了怎么办。
本质就是将一个长度为 的数组用特别的方法分成不超过 段区间,用这些区间的已知信息做合并来拼凑出询问的信息,大概长下面这个样子:
其中,被标成蓝色的点就是管辖了其子节点所有信息的点。
那么该怎么分每个节点管辖的信息呢?
这是被定义的,定义如下:
设 是树状数组中下标为 的节点,那么它管辖的区间就是原数组中 内的元素的信息,其中, 是 lowbit(k)
,而 lowbit(k)
的意思是 在二进制表示中最低位的 及其后面的所有 所构成的数值,比如 lowbit(5)
的计算方法就是先将 转化为二进制,为 ,然后取出右边开始第一个 及其右侧的所有 组成的数值,即 ,转化为十进制就是 ,在代码中,lowbit(x)
函数被实现为 与 做 &
运算,具体为什么在此不多赘述,可以自行查询位运算相关知识。
基本用法
终于到了激动人心的基本用法讲解!
写在前面
首先,你要了解树状数组查询区间信息的本质——差分。
因此,普通的树状数组不能维护区间最大值等等不可差分的信息!
区间求和
注意:树状数组每次只能查询形如下标在 到 的区间前缀和,所以真正的区间和需要运用前缀和知识进行拼凑。
假设我们要查询区间 到 的前缀和(下文中设 lowbit(k)
为 ,且 等表述意为 在减去先前一个 之后的数做 lowbit
运算的值)。
首先,我们已经有了 ,那么,为了继续找到我们所求答案的下一个部分,我们需要继续查询 的值并累加到答案中,注意到这个值就是 ,那么以此类推,每次都用上述一样的思想就可以得出查询的方法是将 一直到 这些值全部相加,就拼凑了原数组中下标在 到 的和。
之后,在求出了 到 的和 与 到 的和 后,就可以根据前缀和的知识得知 到 的和为 。
代码:
int Query(int x) {
int ret=0;
for(; x; x-=lb(x)) {
ret+=c[x];
}
return ret;
}
单点修改
如果要修改 的值,那么就需要在 数组中更新所有管辖了 值的节点。
观察最初的图,可以发现 号有色节点的父节点编号是 ( 为 lowbitx(x)
),那么就可以通过不断从 往上“跳”,每次都跳到当前节点的父节点,更新跳到的每个节点即可。
代码:
void Modify(int x,int v) {
for(; x<=m; x+=lb(x)) {
c[x]+=v;
}
}
Tips
注意,一般情况下,树状数组中的初值就是在原数组对应的位置存上对应的值!
练习
现在,你学习了树状数组的基本用法,那么,你就可以完成 P3374 了!
小进阶
1. 区间修改,单点查询
结合普通的差分数组,我们就可以实现区间修改,单点查询!
实现:
- 求出原序列的查分数组 ,并将其按照下标作为键值存入树状数组。
- 利用原本树状数组“单点修改”的特性与差分性质,修改 与 即可实现“区间修改”。
- 利用原本树状数组“区间查询”的特征与差分性质——对差分数组求前缀和就可以获得原序列可得,查询的第 个数的值相当于求出 到 在树状数组上的和。
代码(存储初值):
b[i] = a[i] - a[i - 1];
Modify(i, b[i]);
代码(修改):
Modify(l, k);
Modify(r + 1, -k);
代码(查询):
printf("%d\n", Query(x));
练习 2
接下来,完成 P3368 吧!
2. 区间修改,区间查询
其实当我们掌握了基本方法,做任意理论上可以实现的查询都可以通过“推式子”得出。
由上个部分的查分数组做考虑组合出答案。
首先,,那么:
那么这个式子可以分别维护左半部分和右半部分,开两个树状数组即可,一个存储普通的数值,一个存储 。
代码(存储):
t1.add(i,b[i]);
t2.add(i,(i-1)*b[i]);
代码(修改):
t1.add(x,k);
t1.add(y+1,-k);
t2.add(x,k*(x-1));
t2.add(y+1,-k*y);
代码(查询):
ans+=y*t1.q(y);
ans-=(x-1)*t1.q(x-1);
ans-=t2.q(y);
ans+=t2.q(x-1);
练习 3
使用树状数组完成 P3372。
正经进阶
来点进阶的!
1. 权值树状数组
本质上,权值树状数组就是将原本用下标作为键值的树状数组改为了用一个数值作为下标!
他有什么用呢?
他可以相当于将树状数组变成一个“数轴”,因为使用值域作为下标,那么原本在一个位置加上一个数的操作就相当于在一条数轴上标记一个点。
值得注意的是,这种方法受空间限制(总不能开 大小的数组吧),所以通常搭配离散化来进行操作!
如果我们要统计一个数组中 的数量,我们该怎么做?
根据上文的描述,我们可以将这些值全部作为点存进“数轴中”,假设为下图。
其中,红色数字代表树状数组中的“下标”,蓝色的数字表示这个数字出现的次数,那么,如果我们想要统计比 小的元素有多少个,那么我们只需要求得“下标”在 间所有蓝色数的和即可,对应到树状数组上就是查询区间 的和,也就是 Query(5)
,如果要查询比某个数大的元素个数,也只需要求得这个数右侧的下标对应的蓝色数的和即可。
代码(加点,其中求 的部分是离散化后的结果):
int rk=lower_bound(b+1,b+m+1)-b;
Modify(rk,1);
练习 4
好了,再结合离散化,你就可以完成:
- SP32899(通常情况下,“加点”操作都要按照顺序一个一个来,不能一次性全部加进去,因为这样会导致对下标的要求混乱,比如你要求所有的 为了保证 的关系,你需要按照顺序加点)。
- P1908(本题中因为逆序对也要求了下标的顺序,注意控制“加点”的顺序与查询的细节)。
2. 全局第 大值。
再次考虑权值树状数组。
问题相当于:在权值树状数组上找到一个 ,满足 到 的前缀和 , 到 的前缀和 ,那么, 就是第 大值。
二分 结合权值树状数组查询即可,复杂度 ,慢了。
考虑更高效的“跳”来找到 。
想到倍增,从大到小枚举一个 ,记录一个变量 初始为 ,每次跳 步,尝试将 的前缀和加入一个初始为 的数 中,如果加入后 ,那么说明可以继续往后跳,将 更新为 ,依次类推,最后会找到最大的 使 ,那么 就是答案。
由于 的前缀和其实就是 ,可以每次 查询,于是这种方法的复杂度降至了 ,优秀。
其次,修改操作只要在权值树状数组对应的映射上进行加减操作即可。
3. 二维树状数组
顾名思义,二维树状数组就是对一个矩阵进行操作的数据结构。
先给个代码感受下:
void add(int x, int y, int v) {
for (int i=x; i <= n; i += lowbit(i)) {
for (int j=y; j<=n; j += lowbit(j)) {
c[i][j] += v;
}
}
}
int sum(int x,int y) {
int ret=0;
for(int i=x; i; i-=lowbit(i)) {
for(int j=y; j; j-=lowbit(j)) {
ret+=c[i][j];
}
}
return ret;
}
具体讲解可以看作者的这篇题解。
习题 5
鸽了
1. 维护不可差分信息
不可差分的信息树状数组可不可以维护呢?
行!但就是很慢,是单次 的,不如线段树。
全部评论 9
sblz,快把代骂都给出来,不然不好cv
6天前 来自 广东
0sblz,快把代骂都给出来,不然不好cv
1周前 来自 浙江
0(((
1周前 来自 浙江
0?
1周前 来自 浙江
0谁能帮我 at AC君
1周前 来自 浙江
0
%%%
1周前 来自 广东
0P3374 【模板】树状数组 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
-
将某一个数加上 ;
-
求出某区间每一个数的和。
输入格式
第一行包含两个正整数 ,分别表示该数列数字的个数和操作的总个数。
第二行包含 个用空格分隔的整数,其中第 个数字表示数列第 项的初始值。
接下来 行每行包含 个整数,表示一个操作,具体如下:
-
1 x k
含义:将第 个数加上 ; -
2 x y
含义:输出区间 内每个数的和。
输出格式
输出包含若干行整数,即为所有操作 的结果。
输入输出样例 #1
输入 #1
5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4
输出 #1
14 16
说明/提示
【数据范围】
对于 的数据,,;
对于 的数据,;
对于 的数据,。数据保证对于任意时刻, 的任意子区间(包括长度为 和 的子区间)和均在 范围内。
样例说明:
故输出结果 和 。
1周前 来自 福建
0-
@AC君
1周前 来自 浙江
0lz竟然不会树状数组上二分
1周前 来自 广东
0神人lz,全局第 大不就二分一下就行了吗
1周前 来自 广东
0会的,只是现在不想写
1周前 来自 浙江
0%%%
1周前 来自 广东
0nmnmn
1周前 来自 浙江
0
lz 依旧擅长画画(((
1周前 来自 浙江
01周前 来自 浙江
0
有帮助,赞一个