树状数组
用处
区间加,单点查询
单点加,区间查询
区间加,区间查询
求逆序对
……
思想
树状数组的思想对于线段树等结构来说比较抽象,所以我也懒得讲……
在这我只讲一下我对于树组的理解,对于实战来说完全够用。
先讲一个叫 \(lowbit\) 的东西,求一个数二进制下最后一个 \(1\) 的位置,比如 \((1010110)_2\) 的 \(lowbit\) 为 \((10)_2\) 。
然后在树状数组里我们定义一个 \(c\) 数组,里面存区间 \([i-lowbit(i)+1,i]\) 的所有数之和。
然后你可以这样理解: 对于二进制 \(i\) 位上的为 \(1\) ,查询的时候累计所有第 \(i\) 位置上为 \(1\) 的 \(c_i\) 之和,修改的时候把每一个二进制上的为 \(1\) 的位置来修改。
有些抽象,还是看代码吧……
树状数组支持的操作有两种
\(1.\) 查询前缀和
int ask(int x){
int ans=0;
while(x<=n){
ans+=c[x];
x+=lowbit(x);
}
return ans;
}
$ 2. $ 单点修改
int add(x,k){
while(x){
c[x]+=k;
x-=lowbit(x);
}
}
求逆序对
用 \(t[val]\) 来记录每个数在数组 \(a\) 出现的次数,我们再用树状数组来维护这个前缀和。
逆序对条件 $i<j $ 并且 \(a[i] > a[j]\)
So 从右往左遍历数组 \(a\)
步骤:
\(1.\) 查询当前 t[a[i]-1] 的前缀和,累加到答案上,因为是从右往左扫的,所以比当前位置的数小的就是逆序对的个数,自己好好想一想是不是这样。
$ 2. $ 单点增加,把 \(a[i]\) 的出现次数+1,即 \(t[a[i]]\)++ ,同时维护其前缀和。
代码
for(int i=n;i;i--){
ans+=ask(a[i]-1);
add(a[i],1);
}
复杂度为 \(O( (N+M) log M )\),$ M $为数据范围大小
当然了,当数据范围较大时,要先离散化,本生就要排序,所以在数据范围较大时不如直接用归并排序。
例题:
https://www.acwing.com/problem/content/description/243/
区间修改,单点查询
用差分思想,树状数组维护一个差分数组数组 \(b\)
操作时
add(l,d);
add(r+1,-d);
就行了。
例题:
https://www.luogu.com.cn/problem/P3368
区间修改,区间查询
修改操作思路不变,用差分数组 \(b\) 来实现。
emm……下面太难写了,拉一段李煜东大哥的书吧
在本题中,我们增加一个树状数组,用于维护 \(i*b[i]\) 的前缀和,然后可以直接进行查询、计算。
具体来说,我们建立两个树状数组 \(c0\) 和 \(c1\) ,起初全部赋值为零。对于每条指令 \(“C l r d”\),执行4个操作:
然后……
步骤:
1.在树状数组 \(c0\) 中,把位置 \(l\) 上的数加 \(d\)。
2.在树状数组 \(c0\) 中,把位置 \(r+1\) 上的数减 \(d\)。
3.在树状数组 \(c1\) 中,把位置 \(l\) 上的数加\(l* d\)。
4.在树状数组 \(c1\) 中,把位置 \(r+1\) 上的数减 \((r+1)*d\) 。
另外,我们建立数组 \(sum\) 存储序列 \(a\) 的原始前缀和。对于每条指令 \(“Qlr”\) 当然还是拆成 \(1~r\) 和 \(1~l-1\) 两个部分,二者相减。写成式子就是
sum[r]+(r+1)*ask(0,r)-ask(1,r) -
sum[l-1]+l*ask(0,l-1)-ask(1,l-1);
例题:
https://www.acwing.com/problem/content/description/244/
大家应该不会偷懒去写线段树吧……
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N=1e5+5;
int a[N],sum[N],c[2][N];//c[0]->b[i]c[1]->i*b[i]
#define FOR(i,_l,_r) for(int i=_l;i<=_r;i++)
int lowbit(int x){
return x&-x;
}
void add(int x,int id,int k){
while(x<=n){
c[id][x]+=k;
x+=lowbit(x);
}
}
int ask(int id,int x){
int ans=0;
while(x){
ans+=c[id][x];
x-=lowbit(x);
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>m;
FOR(i,1,n){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
while(m--){
char opt;
int l,r,d;
cin>>opt>>l>>r;
if(opt=='C'){
cin>>d;
add(l,0,d);
add(r+1,0,-d);
add(l,1,l*d);
add(r+1,1,-(r+1)*d);
}
else{
int ans=sum[r]+(r+1)*ask(0,r)-ask(1,r);
ans-=sum[l-1]+l*ask(0,l-1)-ask(1,l-1);
cout<<ans<<endl;
}
}
return 0;
}
作业:
https://www.acwing.com/problem/content/description/245/
作业提示:二分答案……
完结撒花
喜欢的点个赞,感激不尽
标签:树状,int,sum,刍议,add,数组,ask From: https://www.cnblogs.com/yingxilin/p/18347365