欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线段树专题

程序员文章站 2022-07-13 11:30:55
...

线段树(未完待续)



线段树长度,若元素个数为n,一般开4倍(maxn<<2)的空间就不会溢出,hdu1166开两倍会超时,改成四倍就ac了,线段树必须从1开始,每个节点(线段)管理的区间为【】,两边都是闭区间。
线段树专题

  • 线段树就是讲区间分解成小区间,比如求区间【1,4】的和,讲分解为【1,1】【2,2】【3,4】。

hdu 1166 敌兵布阵(线段树单点更新)

Input
第一行一个整数T,表示有T组数据。
敌人有N个工兵营地,有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令

Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=50000+5;
int sum[maxn<<2];

////i节点收集子节点的统计结果
void getsum(int i){
    sum[i]=sum[i*2]+sum[i*2+1]; 
}

void build(int i,int l,int r){
    if(l==r){  //到达叶子节点,叶子节点管理的区间仅有一个点 
        scanf("%d",&sum[i]);
        //cout<<sum[i]<<'\n';
        return ;
    }
    
    int m=(l+r)/2;
    
    build(i<<1,l,m);
    build(i<<1|1,m+1,r);//移位运算符优先级大于位运算符
    getsum(i);  //收集子节点的结果,要时刻记住维护节点统计信息的正确性!!
}

//update这个函数就有点定制的意味了
//本题是单点更新,所以实在区间[l,r]内使得第id数的值+val
//如果是区间更新,可以将函数的id参数变为ql,qr
void update(int id,int x,int i,int l,int r){
    if(l==r){
        sum[i]+=x;return ;
    }
    
    int m=(l+r)/2;
    
    if(id<=m)update(id,x,i<<1,l,m);
    else  update(id,x,i<<1|1,m+1,r);
    
    getsum(i);//要时刻记住维护节点统计信息的正确性!!
}

//在当前区间[l,r]内查询区间[ql,qr]间的目标值
//且能执行这个函数的前提是:[l,r]与[ql,qr]的交集不为空
//其实本函数返回的结果也是 它们交集的目标值

int query(int ql,int qr,int i,int l,int r){
    int m=(l+r)/2,ans=0;
    
    if(ql<=l&&qr>=r)return sum[i];
    
    if(qr<l||ql>r)return 0;//完全不在查询区间内,返回一个没有影响的输 
    
    if(ql<=m)
    	ans+=query(ql,qr,i<<1,l,m);
    if(qr>m)//特别注意此处,不是else!!!!!
    	ans+=query(ql,qr,i<<1|1,m+1,r);//按位或运算符
    
    return ans;
} 

int main()
{
    int T,n,kase=0;;
    cin>>T;
    while(T--)
    {
        cin>>n;
        build(1,1,n);
        char str[10];
        int x,y;
        printf("Case %d:\n",++kase);
        while(~scanf("%s",str))
        {
            if(str[0]=='E')
                break;
            scanf("%d%d",&x,&y);
            if(str[0]=='A')
                update(x,y,1,1,n);
            else if(str[0]=='Q')
                printf("%d\n",query(x,y,1,1,n));
            else if(str[0]=='S')
                update(x,-y,1,1,n);
        }
    }
    return 0;
}

洛谷P1047 校门外的树(线段树区间更新,区间查询)

  • 题意:[0,n]每个点有一棵树,M此操作,每次讲[a,b]区间的树砍掉,问最后剩下多少树。
输入
500 3
150 300
100 200
470 471

输出
298
  • 线段树区间更新,区间查询,维护一个sum[]数组,初始赋值为1,更新时变成0,最后query整个区间。此处的区间更新是自己想出来的,按照点更新的思想实现的。
  • 正宗区间更新,区间查询算法
//正宗区间查询,lazy标记思想,区间加法
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=100005;
ll sum[maxn<<2],addv[maxn<<2];//addv为lazy标记 
void up(int i){
	sum[i]=sum[i<<1]+sum[i<<1|1];
}

void down(int ln,int rn,int i){
	if(addv[i]){
		sum[i<<1]+=(ll)ln*addv[i];
		sum[i<<1|1]+=(ll)rn*addv[i];
		addv[i<<1]+=addv[i];
		addv[i<<1|1]+=addv[i];
		addv[i]=0;
	}	
}
void build(int i,int l,int r){
	if(l==r){
		scanf("%lld",&sum[i]);
		return ;
	}
	int m=l+(r-l)/2;
	build(i<<1,l,m);
	build(i<<1|1,m+1,r);
	up(i); 
}
void update(int i,int l,int r,int v,int L,int R){
	if(L<=l&&R>=r){
		sum[i]+=(r-l+1)*v;
		addv[i]+=v;
		return;
	}
	if(l>R||r<L)return;
	int m=l+(r-l)/2;
	down(m-l+1,r-m,i);
	if(L<=m)update(i<<1,l,m,v,L,R);
	if(R>m)update(i<<1|1,m+1,r,v,L,R);
	up(i);
}

ll query(int i,int l,int r,int L,int R){
	if(l>=L&&r<=R)return sum[i];
	if(l>R||r<L)return 0; 
	int m=l+(r-l)/2;
	down(m-l+1,r-m,i);
	ll ans=0;
	if(L<=m)ans+=query(i<<1,l,m,L,R);
	if(R>m)ans+=query(i<<1|1,m+1,r,L,R);
	return ans;
}
int main(){
	//freopen("C:\\Users\\22765\\Desktop\\in.txt","r",stdin);
	int n,q;
	scanf("%d%d",&n,&q); 
	build(1,1,n);
	char op;int x,y,v;
	while(q--){
		getchar();
		op=getchar();
		if(op=='Q'){
			scanf("%d %d",&x,&y);
			printf("%lld\n",query(1,1,n,x,y));
		}
		else {
			scanf("%d %d %d",&x,&y,&v);
			update(1,1,n,v,x,y);
		}
	}
	return 0;
}
#include <iostream>
using namespace std;
const int N=1e4+3;

int n,M;
int sum[N<<2];//开四倍空间 
void build(int i,int l,int r){
	if(l==r){
		sum[i]=1;
		return ;
	}
	
	int m=(l+r)/2;
	build(i*2,l,m);
	build(i*2+1,m+1,r);
	
	sum[i]=sum[i*2]+sum[i*2+1];
	
}

void update(int i,int ql,int qr,int l,int r){

	if(l==r){//直接更新到某个点,有点像暴力打法,一个一个点更新 
		sum[i]=0; 
		return ;
	}
	if(ql>r||qr<l)return ;
	
	int m=(l+r)/2;
	
	if(ql<=m)update(i*2,ql,qr,l,m);
	if(qr>m)update(i*2+1,ql,qr,m+1,r);
	
	sum[i]=sum[i*2]+sum[i*2+1];
	 
} 
int query(int ql,int qr,int i,int l,int r){
	int ans=0;
	if(ql<=l&&qr>=r)return ans+=sum[i];
	
	int m=(ql+qr)/2;
	
	if(ql<=m)ans+=query(ql,qr,i*2,l,m);
	if(qr>m)ans+=query(ql,qr,i*2+1,m+1,r);
	
	return ans;
}
int main(){
	cin>>n>>M;
	build(1,1,n+1);
	int a,b;
	while(M--){
		cin>>a>>b;
		update(1,a+1,b+1,1,n+1);
	}
	cout<<query(1,n+1,1,1,n+1);
	return 0;
}
/*
500 3
150 300
100 200
470 471

1000 5
0 100
101 200
900 1000
207 400
401 899

7 2 
1 3
2 4

*/

线段树区间设置值,区间查询

//区间设置值,setv,区间求和
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll sum[maxn<<2],setv[maxn<<2]; 

void up(int i){
	sum[i]=sum[i<<1]+sum[i<<1|1];
	//cout<<"up "<<i<<" "<<sum[i]<<endl; 
}

void down(int ln,int rn,int i){
	if(setv[i]){
		setv[i<<1]=setv[i<<1|1]=setv[i];//注意这里不是+= 
		sum[i<<1]=(ll)ln*setv[i];//注意这里不是+= 
		sum[i<<1|1]=(ll)rn*setv[i]; //注意这里不是+= 
		setv[i]=0;	
		//cout<<"down "<<i<<" "<<ln<<" "<<rn<<" "<<sum[i<<1]<<" "<<sum[i<<1|1]<<" "<<setv[i<<1]<<endl;
	}
}
 
void build(int i,int l,int r){
	if(l==r){
		sum[i]=1;
		return ;
	}
	
	int m=l+(r-l)/2;
	build(i<<1,l,m);
	build(i<<1|1,m+1,r);
	up(i);
}

void update(int i,int v,int l,int r,int L,int R){
	if(l>R||r<L)return;
	if(L<=l&&R>=r){
		sum[i]=(r-l+1)*v;//注意这里不是+=  
		setv[i]=v;//注意这里不是+= 
		//cout<<i<<" update "<<sum[i]<<" "<<setv[i]<<endl;
		//cout<<setv[i]<<endl;
		return;
	}
	
	int m=l+(r-l)/2;
	down(m-l+1,r-m,i);//注意这里是   m-l+1!!!调试了一上午没发现 
	if(L<=m)update(i<<1,v,l,m,L,R);
	if(R>m)update(i<<1|1,v,m+1,r,L,R);
	up(i);
}
ll query(int i,int l,int r,int L,int R){
	if(l>=L&&r<=R)return sum[i];
	if(l>R||r<L)return 0;
	
	int m=l+(r-l)/2;
	down(m-l+1,r-m,i);
	ll ans=0;
	if(L<=m)ans+=query(i<<1,l,m,L,R);
	if(R>m)ans+=query(i<<1|1,m+1,r,L,R);
	return ans;
}
int main(){
	int t,n;scanf("%d",&t);
	int x,y,v,q;
	for(int i=1;i<=t;i++){
		memset(sum,0,sizeof(sum));
		memset(setv,0,sizeof(setv));
		scanf("%d",&n);
		build(1,1,n);
		scanf("%d",&q);
		while(q--){
			scanf("%d%d%d",&x,&y,&v);
		//	cout<<x<<y<<v<<endl;
			update(1,v,1,n,x,y);
		}
	//	cout<<sum[1]<<endl;
		printf("Case %d: The total value of the hook is %lld.\n",i,query(1,1,n,1,n));
	}
	return 0;
}

ZOJ - 1610 Count the Colors(区间染色)

  • 题意:在一条长度为8000的线段上染色,每次把区间[a,b]染成c颜色。显然,后面染上去的颜色会覆盖掉之前的颜色。求染完之后,每个颜色在线段上有多少个间断的区间。

  • 这题比较坑的是千万不能拿n建树,不然就会segmentation fault,必须拿8000建树,也就是树是固定的。


#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=8004;
int col[maxn<<2];
int num[maxn];
void down(int i){
	if(col[i]!=-1){
		col[i<<1]=col[i<<1|1]=col[i];
		col[i]=-1;
	}
}
void update(int i,int c,int l,int r,int L,int R){
	if(l>R||r<L)return;
	if(L<=l&&r<=R){
		col[i]=c;
		return ;
	}
	down(i);
	int m=l+(r-l)/2;
	if(L<=m)update(i<<1,c,l,m,L,R);
	if(R>m)update(i<<1|1,c,m+1,r,L,R);
}
int pre=-2;
void query(int i,int l,int r,int L,int R){
	if(l==r){
		if(col[i]!=-1&&col[i]!=pre){
			num[col[i]]++;
		}
		pre=col[i];
		return;
	}
	
	int m=l+(r-l)/2;
	down(i);
	if(L<=m)query(i<<1,l,m,L,R);
	if(R>m)query(i<<1|1,m+1,r,L,R);
}
int main(){
	int n,x,y,c;
	while(~scanf("%d",&n)){
		memset(col,-1,sizeof(col));
		memset(num,0,sizeof(num));
		while(n--){
			scanf("%d %d %d",&x,&y,&c);
			update(1,c,1,8000,x+1,y);
		}
		query(1,1,8000,1,8000);
		for(int i=0;i<=8000;i++){
			if(num[i])
				printf("%d %d\n",i,num[i]);
		}
		printf("\n");
	}
	return 0;
}