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

92 阅读 0 评论 61 点赞

我是靠谱客的博主秀丽飞鸟，这篇文章主要介绍GCD线段树+差分+树状数组模板，现在分享给大家，希望可以做个参考。

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

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

根据更相减损术的原理，可将 $gcd(x,y)rightleftharpoons gcd(x,y-x)$ ，推广得 $gcd(a,b,ccdot cdotcdot cdot )rightleftharpoons gcd(a,b-a,c-bcdot cdotcdot cdot )$ 首位不变

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

复制代码

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#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;
}

树状数组：

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

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

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

线段树的数据范围大概在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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#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 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#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);
}

//线段树模板 
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同操作
}

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#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;
}