rt，用线段树实现的维护区间 gcd，思路是用线段树维护差分

题目

代码

#include<iostream>
#define maxn 500001 
using namespace std;
int n,m;
struct Tree{ // 整个线段树维护的是差分序列 
	int l,r;
	long long sum,d; // 差分区间和、gcd 
	#define lson i<<1
	#define rson i<<1|1
}tree[maxn<<2];
long long a[maxn]; // 原序列 
inline int read();
inline long long Lread();
inline void write(long long x);
//long long gcd(long long a,long long b){ return a%b==0?b:gcd(b,a%b); } 
// ↓这种写法可以应对更大规模的数据 
long long gcd(long long a,long long b){ return b?gcd(b,a%b):a; }
void pushup(Tree &T,Tree L,Tree R){ T.sum=L.sum+R.sum,T.d=gcd(L.d,R.d); }
void build(int i,int l,int r){
	tree[i].l=l,tree[i].r=r;
	if (l==r){ tree[i]={l,r,a[r]-a[r-1],a[r]-a[r-1]}; return; }
	// sum 中存放的是差分和，当 l==r 时就是 d[r]，即 a[r]-a[r-1] 
	int mid=l+r>>1;
	build(lson,l,mid),build(rson,mid+1,r);
	pushup(tree[i],tree[lson],tree[rson]);
}
void modify(int i,int p,long long k){
	if (tree[i].l==tree[i].r && tree[i].r==p){ tree[i].sum+=k,tree[i].d+=k; return; }
	int mid=tree[i].l+tree[i].r>>1;
	if (p<=mid) modify(lson,p,k);
	if (p>mid)  modify(rson,p,k);
	pushup(tree[i],tree[lson],tree[rson]);
}
Tree query(int i,int l,int r){
	if (l<=tree[i].l && tree[i].r<=r) return tree[i];
	int mid=tree[i].l+tree[i].r>>1;
	if (r<=mid) return query(lson,l,r); // 查询区间最右边在线段树区间左边，全分布在左子树 
	else if (l>mid) return query(rson,l,r); // 反之，全在左侧。这与之前写过的线段树板子都不一样 
	Tree T; pushup(T,query(lson,l,r),query(rson,l,r));
	// 两个区间都有 
	return T;
}
void output(){ for (int i=1;i<=n*4;i++) printf("%d %d %d %d\n",tree[i].l,tree[i].r,tree[i].sum,tree[i].d); }
int main(){
	n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=Lread();
	build(1,1,n);
	while (m--){
		// output();
		char ch[2]; scanf("%s",ch); int l=read(),r=read(); 
		if (*ch=='C'){
			long long x=Lread(); modify(1,l,x);
			if (r+1<=n) modify(1,r+1,-x); // 防止越界 
			// 维护的是差分序列，对于原序列的区间修改就是对差分序列的两次单点修改 
		}
		else { // 查询，要分两步查，一部分是左侧的前缀和(构成 a[l])，一部分是右边的 gcd 
			auto left=query(1,1,l),right=query(1,l+1,r);
			write(abs(gcd(left.sum,right.d))); puts(""); 
			// 根据公式，gcd(a[l]~a[r]) = gcd(a[l],a[l+1]-a[l],a[l+2]-a[l+1],...,a[r]-a[r-1])
			//  = gcd(a[l],b[l],b[l+1],b[l+2],...,b[r]) = gcd(a[l],gcd(b[l]~b[r])) 
			// (这里 b 是差分数组 ↑)，因为线段树中维护的 sum 是差分序列，所以 
			// = gcd(a[l],query(1,l+1,r).d) = gcd(d[1]+d[2]+...+d[l],query(1,l+1,r).d) 
			// = gcd(query(1,1,l).sum,query(1,l+1).d)
		}
	}
	return 0;
}
inline int read(){
	int ans=0,f=1; char cc=getchar();
	while (cc<'0'||cc>'9'){ if (cc=='-') f=-1; cc=getchar(); }
	while ('0'<=cc && cc<='9'){ ans=(ans<<3)+(ans<<1)+(cc-'0'); cc=getchar(); }
	return f*ans;
} 
inline long long Lread(){
	long long ans=0; int f=1; char cc=getchar();
	while (cc<'0'||cc>'9'){ if (cc=='-') f=-1; cc=getchar(); }
	while ('0'<=cc && cc<='9'){ ans=(ans<<3)+(ans<<1)+(cc-'0'); cc=getchar(); }
	return f*ans;
} 
inline void write(long long x){
	if (x/10>0) write(x/10);
	putchar(x%10+'0');
}

Hack：

in:

5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 5 5
C 3 3 6
Q 2 4

1
10
4