树状数组

用户头像 发布于 6 天前 31 次阅读 OI

树状数组

P3605 [USACO17JAN] Promotion Counting P

很模板的一道树上树状数组，
计算遍历子树后的变化就可以了，
代码：

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=2e5+5;
int n,m;
vector<int> g[N];
int a[N],tr[N],cnt[N],p[N];

void change(int x,int k){
	while(x<=n){
		tr[x]+=k;
		x+=lowbit(x);
	}
}

int query(int x){
	int t=0;
	while(x){
		t+=tr[x];
		x-=lowbit(x);
	}
	return t;
}

void dfs1(int x){
	cnt[x]-=(query(n)-query(a[x]));
	for(int i=0;i<g[x].size();i++) dfs1(g[x][i]);
	cnt[x]+=(query(n)-query(a[x]));
	change(a[x],1);
}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		a[i]=p[i];
	}
	sort(p+1,p+1+n);
	for(int i=1;i<=n;i++) a[i]=lower_bound(p+1,p+1+n,a[i])-p;
	for(int i=2;i<=n;i++){
		int u;
		cin>>u; 
		g[u].push_back(i);
	} 
	dfs1(1);
	for(int i=1;i<=n;i++) cout<<cnt[i]<<endl;
    return 0;
}

P1972 [SDOI2009] HH 的项链

考虑离线处理，对每次查询按右端点大小排序。
然后从左到右枚举每个贝壳，
如果之前出现了相同的贝壳种类，
由于右端点排序的性质，当前贝壳一定会查询到，
所以给当前贝壳加一，给之前的贝壳减一，来消除区间求和找到它的影响即可。
代码：

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=1e6+5;
int n,m;
int tr[N],a[N],last[N],ans[N];
struct ask{
	int l,r,id;
}q[N];

void change(int x,int k){
	while(x<=n){
		tr[x]+=k;
		x+=lowbit(x);
	}
}

int query(int x){
	int t=0;
	while(x){
		t+=tr[x];
		x-=lowbit(x);
	}
	return t;
}

bool cmp(ask x,ask y){return x.r<y.r;}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+1+m,cmp);
	int l=0;
	for(int i=1;i<=m;i++){
		while(l<q[i].r){
			l++;
			if(last[a[l]]) change(last[a[l]],-1);
			last[a[l]]=l;
			change(l,1);
		}
		ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}

P4113 [HEOI2012] 采花

思路和上一题很相似，只不过题目改成了区间内同颜色数量大于 2 的颜色个数。
一样的离线+排序，发现从左往右找找到第二个同颜色的点才会对答案有贡献，
所以对于当前点，上一个同颜色的点 +1，上上一个同颜色的点 -1 消除影响即可。
代码：

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=2e6+5;
int n,m,c;
int tr[N],a[N],last[N],last2[N],ans[N];
struct ask{
	int l,r,id;
}q[N];

void change(int x,int k){
	while(x<=n){
		tr[x]+=k;
		x+=lowbit(x);
	}
}

int query(int x){
	int t=0;
	while(x){
		t+=tr[x];
		x-=lowbit(x);
	}
	return t;
}

bool cmp(ask x,ask y){return x.r<y.r;}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	cin>>n>>c>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+1+m,cmp);
	int l=0;
	for(int i=1;i<=m;i++){
		while(l<q[i].r){
			l++;
			if(!last[a[l]]){
				last[a[l]]=l;
				continue;
			}
			change(last[a[l]],1);
			if(last2[a[l]]) change(last2[a[l]],-1);
			last2[a[l]]=last[a[l]],last[a[l]]=l; 
		}
		ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

P4054 [JSOI2009] 计数问题

二维树状数组模板题，建 c 个树状数组即可，代码：

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=105;
int n,m,q;
int tr[N][N*3][N*3],a[N*3][N*3];

void change(int c,int x,int y,int k){
	for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) tr[c][i][j]+=k;
}

int query(int c,int x,int y){
	int t=0;
	for(int i=x;i>=1;i-=lowbit(i)) for(int j=y;j>=1;j-=lowbit(j)) t+=tr[c][i][j];
	return t;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		cin>>a[i][j];
		change(a[i][j],i,j,1);
	}
	cin>>q;
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int x,y,c;
			cin>>x>>y>>c;
			change(a[x][y],x,y,-1);
			change(a[x][y]=c,x,y,1);
		}
		else{
			int x1,x2,y1,y2,c;
			cin>>x1>>x2>>y1>>y2>>c;
			cout<<query(c,x2,y2)-query(c,x1-1,y2)-query(c,x2,y1-1)+query(c,x1-1,y1-1)<<"\n";
		}
	}
    return 0;
}

P4514 上帝造题的七分钟

这题需要直接对二维差分数组进行前缀和，
设 aa 为原数组，dd 为差分数组，sumsum 为前缀和数组，有：

a[x][y]=∑i=1x∑j=1yd[i][j]sum[x][y]=∑i=1x∑j=1ya[i][j]\begin{aligned} a[x][y]=\sum^{x}_{i=1}\sum^{y}_{j=1}d[i][j] \\ sum[x][y]=\sum^{x}_{i=1}\sum^{y}_{j=1}a[i][j] \\ \end{aligned}
sum[x][y]=∑i=1x∑j=1y∑k=1i∑l=1jd[k][l]=∑i=1x∑j=1y(x−i+1)(y−j+1)d[i][j]=∑i=1x∑j=1yi⋅j⋅d[i][j]−(y+1)∑i=1x∑j=1yi⋅d[i][j]−(x+1)∑i=1x∑j=1yj⋅d[i][j]+(x+1)(y+1)∑i=1x∑j=1yd[i][j] \begin{aligned} &sum[x][y] \\ =&\sum^{x}_{i=1}\sum^{y}_{j=1}\sum^{i}_{k=1}\sum^{j}_{l=1}d[k][l] \\ =&\sum^{x}_{i=1}\sum^{y}_{j=1}(x-i+1)(y-j+1)d[i][j] \\ =&\sum^{x}_{i=1}\sum^{y}_{j=1}i\cdot j\cdot d[i][j] -(y+1)\sum^{x}_{i=1}\sum^{y}_{j=1}i\cdot d[i][j] -(x+1)\sum^{x}_{i=1}\sum^{y}_{j=1}j\cdot d[i][j] +(x+1)(y+1)\sum^{x}_{i=1}\sum^{y}_{j=1}d[i][j] \end{aligned}

然后维护四个二维树状数组即可。

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=2050;
int n,m;
char op;
int a,b,c,d,delta;
int tr1[N][N],tri[N][N],trj[N][N],trij[N][N];
void add(int x,int y,int k){
	for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) tr1[i][j]+=k,tri[i][j]+=k*x,trj[i][j]+=k*y,trij[i][j]+=k*x*y;
}
int check(int x,int y){
	int res=0;
	for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) res+=(x+1)*(y+1)*tr1[i][j]-(x+1)*trj[i][j]-(y+1)*tri[i][j]+trij[i][j];
	return res;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	while(cin>>op){
		if(op=='X') cin>>n>>m;
		else if(op=='L'){
			cin>>a>>b>>c>>d>>delta;
			add(a,b,delta),add(a,d+1,-delta),add(c+1,b,-delta),add(c+1,d+1,delta);
		}
		else if(op=='k'){
			cin>>a>>b>>c>>d;
			cout<<check(c,d)-check(a-1,d)-check(c,b-1)+check(a-1,b-1)<<"\n";
		}
		else break;
	}
	return 0;
}