【一本通题解】树状数组

前言

刚开始刷树状数组的时候只会模板，后面的题压根不会，于是就用别的算法水了几道。

后来板刷一本通的时候，感觉要不整个活就太亏了，于是有了这篇文章

「一本通 4.1 例 1」数列操作

原题

算法：分块

树状数组板子题，用分块过了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],pos[N],L[N],R[N],add[N],sum[N];
int n,t,m;
inline void init(){
	t=sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
	for(int i=1;i<=t;i++){
		sum[i]=0,add[i]=0;
		for(int j=L[i];j<=R[i];j++) pos[j]=i,sum[i]+=a[j];
	}
}
inline void change(int x,int k){
	a[x]+=k,sum[pos[x]]+=k;
}
inline int query(int l,int r){
	int p=pos[l],q=pos[r],ans=0;
	if(p==q){
		for(int i=l;i<=r;i++) ans+=a[i]+add[p];
	}
	else{
		for(int i=p+1;i<=q-1;i++) ans+=sum[i];
		for(int i=l;i<=R[p];i++) ans+=a[i]+add[pos[i]];
		for(int i=L[q];i<=r;i++) ans+=a[i]+add[pos[i]];
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) cin>>a[i];
	init();
	while(m--){
		int k,a,b;
		scanf("%d%d%d",&k,&a,&b);
		if(!k) printf("%d\n",query(a,b));
		else change(a,b);
	}
}

「一本通 4.1 例 2」数星星 Stars

原题

算法：动态开点权值线段树

正解应该是权值树状数组，但我用了权值线段树，但空间不够，于是动态开点。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=6e4+10;
struct node{
	long long num;
	int ls,rs;
}tr[90005];
int tot=0;
inline void pushup(int x){
	tr[x].num=tr[tr[x].ls].num+tr[tr[x].rs].num;
}
void insert(int &x,int l,int r,int k){
	if(!x) x=++tot;
	if(l==r){
		tr[x].num++;
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid) insert(tr[x].ls,l,mid,k);
	else insert(tr[x].rs,mid+1,r,k);
	pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
	if(!x) return 0;
	if(l>=ql&&r<=qr) return tr[x].num;
	int mid=(l+r)/2,sum=0;
	if(ql<=mid) sum+=query(tr[x].ls,l,mid,ql,qr);
	if(qr>mid) sum+=query(tr[x].rs,mid+1,r,ql,qr);
	return sum;
}
int n,root;
int main(){
	scanf("%d",&n);
	while(n--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",query(root,0,N,0,x));
		insert(root,0,N,x);
	}
}

「一本通 4.1 练习 1」清点人数

原题

算法：线段树

可以说是线段树板子题吧，自然是要用线段树的捏

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int tr[N*4];
inline void pushup(int x){
	tr[x]=tr[x*2]+tr[x*2+1];
}
void insert(int x,int l,int r,int k,int p){
	if(l==r){
		tr[x]+=p;
		return;
	}
	int mid=(l+r)/2;
	if(k<=mid) insert(x*2,l,mid,k,p);
	else insert(x*2+1,mid+1,r,k,p);
	pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return tr[x];
	int mid=(l+r)/2,sum=0;
	if(ql<=mid) sum=query(x*2,l,mid,ql,qr);
	if(qr>mid) sum+=query(x*2+1,mid+1,r,ql,qr);
	return sum;
}
int n,k;
int main(){
	scanf("%d%d",&n,&k);
	while(k--){
		char opt[2];
		int m,p;
		scanf("%s",opt);
		if(opt[0]=='A'){
			scanf("%d",&m);
			printf("%d\n",query(1,1,n,1,m));
		}
		else if(opt[0]=='B'){
			scanf("%d%d",&m,&p);
			insert(1,1,n,m,p);
		}
		else{
			scanf("%d%d",&m,&p);
			insert(1,1,n,m,-p);
		}
	}
}

「一本通 4.1 练习 2」简单题

原题

算法：线段树

区间取反，自然是要用可爱的线段树啦，维护个懒标记即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,tr[N*4],add[N*4];
inline void pushdown(int x){
	if(add[x]){
		add[x]=0;
		add[x*2]^=1,add[x*2+1]^=1;
	}
}
void update(int x,int l,int r,int ql,int qr){
	
	if(l>=ql&&r<=qr){
		add[x]^=1;
		return;
	}
	pushdown(x);
	int mid=(l+r)/2;
	if(ql<=mid) update(x*2,l,mid,ql,qr);
	if(qr>mid) update(x*2+1,mid+1,r,ql,qr);
}
int query(int x,int l,int r,int k){
	if(l==r) return add[x];
	pushdown(x);
	int mid=(l+r)/2;
	if(k<=mid) return query(x*2,l,mid,k);
	return query(x*2+1,mid+1,r,k);
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int opt,l,r;
		scanf("%d%d",&opt,&l);
		if(opt==1){
			scanf("%d",&r);
			update(1,1,n,l,r);
		}
		else printf("%d\n",query(1,1,n,l));
	}
}

「一本通 4.1 练习 3」打鼹鼠

原题

算法：线段树+暴力+剪枝

本来想写二逼线段树的，但是xyz太懒了，不想写那么高难度的算法，于是她想暴力。

她写了个一维暴力，二维线段树的$O(n^2\log n)$暴力算法，果然挂了（73）

然后聪明的xyz就加了个剪枝（若一行里个数为0直接返回），就过了！！！

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2100;
int tot=0,root[N],ls[N*N],rs[N*N],tr[N*N];
inline void pushup(int x){
	tr[x]=tr[ls[x]]+tr[rs[x]];
}
void build(int &x,int l,int r){
	x=++tot;
	if(l==r) return;
	int mid=(l+r)/2;
	build(ls[x],l,mid),build(rs[x],mid+1,r);
	pushup(x);
}
void add(int x,int l,int r,int k,int p){
	tr[x]+=p;
	if(l==r) return;
	int mid=(l+r)/2;
	if(k<=mid) add(ls[x],l,mid,k,p);
	else add(rs[x],mid+1,r,k,p);
}
int query(int x,int l,int r,int ql,int qr){
	if(!tr[x]) return 0;
	if(ql<=l&&r<=qr) return tr[x];
	int mid=(l+r)/2,sum=0;
	if(ql<=mid) sum=query(ls[x],l,mid,ql,qr);
	if(qr>mid) sum+=query(rs[x],mid+1,r,ql,qr);
	return sum;
}
int n,m;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) build(root[i],0,n-1);
	while(cin>>m&&m!=3){
		if(m==1){
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			add(root[x],0,n-1,y,k);
		}
		else{
			int x,y,x2,y2,sum=0;
			scanf("%d%d%d%d",&x,&y,&x2,&y2);
			for(int i=x;i<=x2;i++) sum+=query(root[i],0,n-1,y,y2);
			printf("%d\n",sum);
		}
	}
}

后记

本文是xyz的整活，如果你真的想学树状数组，千万不要像她这么干

（xyz可爱捏）