GCD线段树+差分+树状数组模板

https://ac.nowcoder.com/acm/contest/1033/B

线段树维护原数组的差分数组，因为题目直接区间修改，用线段树维护原数组的gcd效率很低，区间gcd的值会发生改变

根据更相减损术的原理，可将，推广得首位不变

树状数组维护原数组，因为推广得到的式子需要用到原数组，需要区间修改 单点查询

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define ll long long
#define inf 0x3f3f3f
int n,m; 
ll num[MAXN];
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

//树状数组模板 
ll BIT[MAXN],BITN[MAXN];
ll lowbit(ll x){return x&(-x);}
//单点修改 区间查询 可使用n初始化
void change(int x,ll val){//单点修改 
	for(int i=x;i<=n;){
		BIT[i]+=val;
		
		//区间修改语句 使用原数组的差分 
		BITN[i]+=val*(x-1);//维护c[i]*(n-1) 
		  
		i+=lowbit(i);
	}
}
ll getSum(int x){//1-x的和 
	ll res=0;
	for(int i=x;i;){
		//res+=BIT[i];
		
		//区间修改语句 使用原数组的差分 
		res+=x*BIT[i]-BITN[i];
		
		i-=lowbit(i);
	}
	return res;
}
//区间修改 区间查询 只能使用nlogn初始化 使用原数组的差分 
void range_change(int l,int r,ll val){
	change(l,val);
	change(r+1,-val);//差分思想 
}
ll getrange_Sum(int l,int r){
	return getSum(r)-getSum(l-1);
}
//用于单点修改 因为区间修改的BITN无法线性初始化 
ll pre[MAXN];//前缀和 
void initBIT(){//线性初始化BIT 
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+num[i];//构造关于num的BIT 
		BIT[i]=pre[i]-pre[i-lowbit(i)];
	}
}

//线段树模板 
struct node{
	ll val;
}segtree[MAXN<<2];

void pushdown(int root){
	segtree[root].val=gcd(segtree[root<<1].val,segtree[root<<1|1].val);
}

void build(int root,int nl,int nr){
	if(nl==nr){
		segtree[root].val=num[nl]-num[nl-1];
		return ;
	}
	
	int mid=nl+nr>>1;
	build(root<<1,nl,mid);
	build(root<<1|1,mid+1,nr);
	
	pushdown(root);//与update同操作
}
 
ll query(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return 0;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].val;
	}
	
	int mid=nl+nr>>1;
	return gcd(query(root<<1,nl,mid,ql,qr),query(root<<1|1,mid+1,nr,ql,qr));
}
 
void update(int root,int nl,int nr,int ql,int qr,ll add){
	if(nl>qr||nr<ql){
		return ;
	}
	
	if(nl>=ql&&nr<=qr){
		segtree[root].val+=add;
		return ;
	}
	
	if(nl==nr){
		segtree[root].val+=add;
		return ;
	}
	
	int mid=nl+nr>>1;
	update(root<<1,nl,mid,ql,qr,add);
	update(root<<1|1,mid+1,nr,ql,qr,add);
	
	pushdown(root);//与build同操作
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&num[i]);
	}
	
	for(int i=1;i<=n;i++){
		change(i,num[i]-num[i-1]);//树状数组维护num  因为需要区间修改 使用差分 
	}
	
	build(1,1,n);//线段树维护差分数组 
	
	for(int i=1;i<=m;i++){
		getchar();
		char c;
		scanf("%c",&c);
		if(c=='Q'){
			ll a,b;
			scanf("%lld%lld",&a,&b);
			printf("%lldn",abs(gcd(getrange_Sum(a,a),query(1,1,n,a+1,b))));
		}
		else if(c=='C'){
			ll a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c);
			
			range_change(a,b,c);
			
			update(1,1,n,a,a,c);
			update(1,1,n,b+1,b+1,-c);
		}
	}
	return 0;
}

树状数组：

单点修改 区间查询：直接存储原数组,使用最基础的树状数组.初始化

区间修改 单点查询：清空数组,用树状数组 差分维护 修改操作的变化量,通过BIT前缀和+原数值可得变化后的数值.初始化

区间修改 区间查询：存储原数组的差分数组,使用进阶树状数组.初始化

线段树的数据范围大概在5e5左右

因为线段是维护的是差分数组，直接求query(1,1,n,1,r)的值就是修改后的单点值，但是牛客这题卡内存，线段树节点中多加一个变量需要增加四个数组的内存，会MLE几个点，求单点值部分使用BIT只需要增加1或2个数组的内存

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define ll long long
#define inf 0x3f3f3f
int n,m; 
ll num[MAXN];
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

//线段树模板 
struct node{
	ll val;
	ll sum;
}segtree[MAXN<<2];

void pushdown(int root){
	segtree[root].sum=segtree[root<<1].sum+segtree[root<<1|1].sum;
	segtree[root].val=gcd(segtree[root<<1].val,segtree[root<<1|1].val);
}

void build(int root,int nl,int nr){
	if(nl==nr){
		segtree[root].val=num[nl]-num[nl-1];
		segtree[root].sum=segtree[root].val;
		return ;
	}
	
	int mid=nl+nr>>1;
	build(root<<1,nl,mid);
	build(root<<1|1,mid+1,nr);
	
	pushdown(root);//与update同操作
}

void update(int root,int nl,int nr,int ql,int qr,ll add){
	if(nl>qr||nr<ql){
		return ;
	}
	
	if(nl==nr){
		segtree[root].sum+=add;
		segtree[root].val+=add;
		return ;
	}
	
	int mid=nl+nr>>1;
	update(root<<1,nl,mid,ql,qr,add);
	update(root<<1|1,mid+1,nr,ql,qr,add);
	
	pushdown(root);//与build同操作
}

ll querySum(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return 0;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].sum;
	}
	
	int mid=nl+nr>>1;
	return querySum(root<<1,nl,mid,ql,qr)+querySum(root<<1|1,mid+1,nr,ql,qr);
}

ll queryGcd(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return 0;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].val;
	}
	
	int mid=nl+nr>>1;
	return gcd(queryGcd(root<<1,nl,mid,ql,qr),queryGcd(root<<1|1,mid+1,nr,ql,qr));
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&num[i]);
	}

	build(1,1,n);//线段树维护差分数组 
	
	for(int i=1;i<=m;i++){
		getchar();
		char c;
		scanf("%c",&c);
		if(c=='Q'){
			ll a,b;
			scanf("%lld%lld",&a,&b);
			printf("%lldn",abs(gcd(querySum(1,1,n,1,a),queryGcd(1,1,n,a+1,b))));
		}
		else if(c=='C'){
			ll a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c);

			update(1,1,n,a,a,c);
			update(1,1,n,b+1,b+1,-c);
		}
	}
	return 0;
}

https://ac.nowcoder.com/acm/contest/949/H

线段树维护差分数组的和，gcd，最值

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
#define inf 0x3f3f3f
int n,m,num[MAXN];

ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

//线段树模板 
struct node{
	ll val;
	ll mx,mn;
	ll sum; 
}segtree[MAXN<<2];
 
void pushdown(int root){
	segtree[root].sum=segtree[root<<1].sum+segtree[root<<1|1].sum;
	segtree[root].val=gcd(segtree[root<<1].val,segtree[root<<1|1].val);
	segtree[root].mx=max(segtree[root<<1].mx,segtree[root<<1|1].mx);
	segtree[root].mn=min(segtree[root<<1].mn,segtree[root<<1|1].mn);
}
 
void build(int root,int nl,int nr){
	if(nl==nr){
		segtree[root].val=num[nl]-num[nl-1];
		segtree[root].sum=segtree[root].mx=segtree[root].mn=segtree[root].val;
		return ;
	}
	
	int mid=nl+nr>>1;
	build(root<<1,nl,mid);
	build(root<<1|1,mid+1,nr);
	
	pushdown(root);//与update同操作
}
 
void update(int root,int nl,int nr,int ql,int qr,ll add){
	if(nl>qr||nr<ql){
		return ;
	}
	
	if(nl==nr){//由于只涉及单点更新 
		segtree[root].sum+=add;
		segtree[root].val+=add;
		segtree[root].mx+=add;
		segtree[root].mn+=add;
		return ;
	}
	
	int mid=nl+nr>>1;
	update(root<<1,nl,mid,ql,qr,add);
	update(root<<1|1,mid+1,nr,ql,qr,add);
	
	pushdown(root);//与build同操作
}

ll querySum(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return 0;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].sum;
	}
	
	int mid=nl+nr>>1;
	return querySum(root<<1,nl,mid,ql,qr)+querySum(root<<1|1,mid+1,nr,ql,qr);
}

ll queryGcd(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return 0;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].val;
	}
	
	int mid=nl+nr>>1;
	return gcd(queryGcd(root<<1,nl,mid,ql,qr),queryGcd(root<<1|1,mid+1,nr,ql,qr));
}

ll queryMax(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return -inf;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].mx;
	}
	
	int mid=nl+nr>>1;
	return max(queryMax(root<<1,nl,mid,ql,qr),queryMax(root<<1|1,mid+1,nr,ql,qr));
}

ll queryMin(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return inf;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].mn;
	}
	
	int mid=nl+nr>>1;
	return min(queryMin(root<<1,nl,mid,ql,qr),queryMin(root<<1|1,mid+1,nr,ql,qr));
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
	}

	build(1,1,n);//线段树维护差分数组 
	
	for(int i=1;i<=m;i++){
		int t,a,b;
		scanf("%d",&t);
		scanf("%d%d",&a,&b);
		if(t==1){
			int val;
			scanf("%d",&val);

			update(1,1,n,a,a,val);
			update(1,1,n,b+1,b+1,-val);
		}
		else if(t==2){
			if(a==b){
				putchar('0');puts("");
				continue;
			}
			printf("%dn",max(queryMax(1,1,n,a+1,b),-queryMin(1,1,n,a+1,b)));//一定要注意边界 
		}
		else {
			if(a==b){
				printf("%dn",abs(querySum(1,1,n,1,a)));
				continue;
			}
			printf("%dn",abs(gcd(querySum(1,1,n,1,a),queryGcd(1,1,n,a+1,b))));
		}
	}

	return 0;
} 

线段树+树状数组

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
#define inf 0x3f3f3f
int n,m,num[MAXN];
int d[MAXN];

ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

//树状数组模板 
ll BIT[MAXN],BITN[MAXN];
ll lowbit(ll x){return x&(-x);}
//单点修改 区间查询 可使用n初始化
void change(int x,ll val){//单点修改 
	for(int i=x;i<=n;){
		BIT[i]+=val;
		
		//区间修改语句 使用原数组的差分 
		BITN[i]+=val*(x-1);//维护c[i]*(n-1) 
		  
		i+=lowbit(i);
	}
}
ll getSum(int x){//1-x的和 
	ll res=0;
	for(int i=x;i;){
		//res+=BIT[i];
		
		//区间修改语句 使用原数组的差分 
		res+=x*BIT[i]-BITN[i];
		
		i-=lowbit(i);
	}
	return res;
}
//区间修改 区间查询 只能使用nlogn初始化 使用原数组的差分 
void range_change(int l,int r,ll val){
	change(l,val);
	change(r+1,-val);//差分思想 
}
ll getrange_Sum(int l,int r){
	return getSum(r)-getSum(l-1);
}
//用于单点修改 因为区间修改的BITN无法线性初始化 
ll pre[MAXN];//前缀和 
void initBIT(){//线性初始化BIT 
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+num[i];//构造关于num的BIT 
		BIT[i]=pre[i]-pre[i-lowbit(i)];
	}
}

//线段树模板 
struct node{
	ll val;
	ll mx,mn;
}segtree[MAXN<<2];
 
void pushdown(int root){
	segtree[root].val=gcd(segtree[root<<1].val,segtree[root<<1|1].val);
	segtree[root].mx=max(segtree[root<<1].mx,segtree[root<<1|1].mx);
	segtree[root].mn=min(segtree[root<<1].mn,segtree[root<<1|1].mn);
}
 
void build(int root,int nl,int nr){
	if(nl==nr){
		segtree[root].val=num[nl]-num[nl-1];
		segtree[root].mx=segtree[root].mn=segtree[root].val;
		return ;
	}
	
	int mid=nl+nr>>1;
	build(root<<1,nl,mid);
	build(root<<1|1,mid+1,nr);
	
	pushdown(root);//与update同操作
}
 
void update(int root,int nl,int nr,int ql,int qr,ll add){
	if(nl>qr||nr<ql){
		return ;
	}
	
	if(nl==nr){
		segtree[root].val+=add;
		segtree[root].mx+=add;
		segtree[root].mn+=add;
		return ;
	}
	
	int mid=nl+nr>>1;
	update(root<<1,nl,mid,ql,qr,add);
	update(root<<1|1,mid+1,nr,ql,qr,add);
	
	pushdown(root);//与build同操作
}

ll queryGcd(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return 0;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].val;
	}
	
	int mid=nl+nr>>1;
	return gcd(queryGcd(root<<1,nl,mid,ql,qr),queryGcd(root<<1|1,mid+1,nr,ql,qr));
}

ll queryMax(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return -inf;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].mx;
	}
	
	int mid=nl+nr>>1;
	return max(queryMax(root<<1,nl,mid,ql,qr),queryMax(root<<1|1,mid+1,nr,ql,qr));
}

ll queryMin(int root,int nl,int nr,int ql,int qr){
	if(nl>qr||nr<ql){
		return inf;
	}
	
	if(nl>=ql&&nr<=qr){
		return segtree[root].mn;
	}
	
	int mid=nl+nr>>1;
	return min(queryMin(root<<1,nl,mid,ql,qr),queryMin(root<<1|1,mid+1,nr,ql,qr));
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
		d[i]=num[i]-num[i-1];//d为差分数组 
	}
	
	for(int i=1;i<=n;i++){
		change(i,num[i]-num[i-1]);//??????num  ???????? ???? 
	}

	build(1,1,n);//线段树维护差分数组 
	
	for(int i=1;i<=m;i++){
		int t,a,b;
		scanf("%d",&t);
		scanf("%d%d",&a,&b);
		if(t==1){
			int val;
			scanf("%d",&val);
			
			range_change(a,b,val);
			
			update(1,1,n,a,a,val);
			update(1,1,n,b+1,b+1,-val);
		}
		else if(t==2){
			if(a==b){
				putchar('0');puts("");
				continue;
			}
			printf("%dn",max(queryMax(1,1,n,a+1,b),-queryMin(1,1,n,a+1,b)));//一定要注意边界 
		}
		else {
			if(a==b){
				printf("%dn",abs(getrange_Sum(a,a)));
				continue;
			}
			printf("%dn",abs(gcd(getrange_Sum(a,a),queryGcd(1,1,n,a+1,b))));
		}
	}

	return 0;
} 

最后

以上就是秀丽飞鸟为你收集整理的GCD线段树+差分+树状数组模板的全部内容，希望文章能够帮你解决GCD线段树+差分+树状数组模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。