题意：
4302 Interval GCD 0x40「数据结构进阶」例题
描述
给定一个长度为N的数列A，以及M条指令 (N≤5*10^5, M<=10^5)，每条指令可能是以下两种之一：
“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
输入格式
第一行两个整数N,M，第二行N个整数Ai，接下来M行每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
样例输入
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4
样例输出
1
2
4
数据范围与约定
- N,M≤2*10^5，l<=r，数据保证任何时刻序列中的数都是不超过2^62-1的正整数。
差分思想 线段树。
树状数组维护原始，线段树维护A[i]-A[i-1]
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
//headconst int maxn = 2e6+11;struct node
{int l,r;ll dat;
}t[maxn];ll a[maxn],b[maxn],c[maxn];
int n,m;
ll gcd(ll a,ll b){return b? gcd(b,a%b):a;}
void pushup(int i){t[i].dat = gcd(t[i<<1].dat,t[i<<1|1].dat);}
void build(int i,int l,int r)
{t[i].l = l,t[i].r = r;if(l == r){t[i].dat= b[l];return;}int mid = (l+r)>>1;build(i<<1,l,mid);build(i<<1|1,mid+1,r);pushup(i);
}void update(int i,int x,ll v)
{if(t[i].l == t[i].r) {t[i].dat += v; return;}int mid = (t[i].l + t[i].r)>>1;if(x<=mid)update(i<<1,x,v);else update(i<<1|1,x,v);pushup(i);
}ll query(int i,int ql,int qr)
{if(ql<=t[i].l && qr >= t[i].r)return abs(t[i].dat);int mid = (t[i].l + t[i].r)>>1;ll ans = 0;if(ql <= mid)ans = gcd(ans,query(i<<1,ql,qr));if(qr > mid)ans = gcd(ans,query(i<<1|1,ql,qr));return abs(ans);
}ll sum(int x)
{ll y = 0;for(;x;x-=x&-x)y += c[x];return y;
}void add(int x,ll y)
{for(; x<=n;x+=x&-x)c[x]+=y;
}int main()
{cin>>n>>m;rep(i,1,n+1){scanf("%lld",a+i);b[i] = a[i] - a[i-1];}build(1,1,n);rep(i,1,m+1){char op[11];scanf("%s",op);int l,r;scanf("%d%d",&l,&r);if(op[0] == 'Q'){ll al = a[l] + sum(l);ll val = l<r? query(1,l+1,r):0;printf("%lld\n",gcd(al,val));}else{ll tmp;scanf("%lld",&tmp);update(1,l,tmp);if(r<n)update(1,r+1,-tmp);add(l,tmp);add(r+1,-tmp); }}return 0;
}