之前是不是从来没发过数据结构的笔记之类的?那是因为我数据结构太菜了,这几天狂刷数据结构题!
模板 – 树状数组1
支持单点修改,并查询区间和的问题。
最经典的树状数组模板题,这里讲解一下如何操作。
树状数组其实维护的是前缀和,而两个前缀和相减就是区间和。
lowbit
求出该数最后一个1的位置。式子是 x \And -x。
线段树有一个底层,这层的数据是原始的,那么我们要按照二进制统计维护这个前缀和,将 x | 1 = 1 的和 x | 1 = 0 合并到树的第二层,大小为 sum ,那么以此类推,不断维护二进制个数的和,最后就可以以 \mathcal{O}(log_n)的复杂度求出单点的前缀和值。
有了lowbit之后,就可以逐次加上lowbit,优化空间,具体如何使用,体会一下下面的数据。
>>> 4 & -4
>>> 4
>>> 5 & -5
>>> 1
>>> 6 & -6
>>> 2
>>> 8 & -8
>>> 8
发现了没有,不管是从小往大,还是从大往小,通过lowbit处理的数据始终都是将数据靠近\texttt 2的幂次。
模板代码
#include<bits/stdc++.h>
//树状数组 模板1
using namespace std;
typedef long long ll;
const int N = 5e5+10;
int tree[N];
int lowbit(int x){return (x & -x);}
void update(int x, int d) {while(x < N) {tree[x] += d; x += lowbit(x);}}
int sum(int x) {int ans = 0; while(x > 0) {ans += tree[x];x -= lowbit(x);}return ans;}
int n, m;
ll a[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {scanf("%lld", &a[i]); update(i, a[i]);}
int q, x, y;
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &q, &x, &y);
if(q == 1) update(x, y);
else printf("%d\n", sum(y) - sum(x - 1));
}
return 0;
}
模板 – 树状数组2
同模板1,求区间的话,其实将单个的值改成差分,这样只要修改区间的左右端点,就可以区间修改。最后要求某一个数的值,由于前缀和是差分的逆运算,所以值在这里就是前缀和,直接询问即可。
Partial Code
for(int i = 1; i <= n; i++) {
update(i, a[i] - a[i - 1]);
}
int q, x, y;
ll k;
while(m--){
scanf("%d", &q);
if(q == 1) {
scanf("%d%d%lld", &x, &y, &k);
update(x, k);
update(y + 1, -k);
}
else {
scanf("%d", &x);
printf("%lld\n", query(x));
}
}
例题 – 逆序对
树状数组求逆序对,个人认为会有更多的应用,但是我没遇到过。
首先要离散化,因为树状数组开不下。树状数组维护的是前缀和,那么我们可以求出当前这个数的前面有多少个数,当权值都为\texttt 1的时候。此时,如果我已经将 i 个数放进了树状数组,而 b_i 查询出来小于 i ,那就说明在 i 前面有数被放到 i 后面了,每次加上这些数的个数。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
ll n, b[N], ans, tree[N];
inline int lowbit(int x) { return x & -x; }
inline void update(int x, int d){while (x < N){tree[x] += d;x += lowbit(x);}}
inline int query(int x){int ans = 0;while (x > 0){ans += tree[x];x -= lowbit(x);}return ans;}
struct num{int pos, val;num() {} num(int x, int y) : pos(x), val(y) {}} a[N];
inline bool cmp(num x, num y) {if (x.val == y.val){return x.pos < y.pos;}return x.val < y.val;}
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++){scanf("%lld", &a[i].val);a[i].pos = 1LL * i;}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++){b[a[i].pos] = i;}
for (int i = 1; i <= n; i++){update(b[i], 1); ans += i - query(b[i]);}
printf("%lld\n", ans);
return 0;
}
区间修改 + 区间查询
$\mathcal{O}(N)$ 建树
有时候树状数组时间被卡了,那么可以考虑线性建树。观察到在建树的时候都是加上自己的lowbit值,而每次都用单点修改会产生很多无用的相加,所以存在线性建树的方法,即递推。
每次只要把自己的lowbit值加上自己即可。
Code
int tr[N]; // 树状数组数据
int a[N]; // 原数组数据
int n; // 数列长度
int lowbit(int x) { return x & -x; }
// 建树
void build(){
for (int i = 1; i <= n; i++){
tr[i] += a[i];
int fa = i + lowbit(i); // 获得父节点下标
if (fa <= n) // 判断父节点是否超出数列范围
tr[fa] += tr[i];
}
}
进阶
准备过渡到二维树状数组