$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. gcd(a[l], a[l+1], ……, a[r]) = gcd(a[l], a[l+1] - a[l], ……, a[r] - a[r-1])
2. 先建立线段树，用来维护差分数组（注意：回溯时不要忘了更新）
3. 修改操作：对于区间[l, r] + d，差分数组b[l] + d, b[r + 1] - d
4. 查询操作则有以下四种情况：
5. （1）若该树区间完全被包含在被查询的区间内，则直接返回该树区间
6. （2）若查询区间在 mid 左边，则递归左边
7. （3）若查询区间在 mid 右边，则递归右边
8. （4）若查询区间跨越 mid，则两边都递归并 pushup 一遍

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 500010;

int n,m;
LL a[N];
struct Node
{
    int l,r;
    LL sum,d;
}tr[N*4]; //开四倍空间

//求最大公约数
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

void pushup(Node &u,Node &l,Node &r)
{
    //区间和
    u.sum=l.sum+r.sum;

    //区间最大公约数
    u.d=gcd(l.d,r.d);
}

//由子节点求父节点
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[l]-a[l-1],a[l]-a[l-1]};
    else 
    {
        tr[u]={l,r};

        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);

        //回溯更新
        pushup(u);
    }
}

void modify(int u,int x,LL v)
{
    if(tr[u].l==tr[u].r&&tr[u].l==x) tr[u]={x,x,tr[u].sum+v,tr[u].sum+v};
    else 
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);

        //回溯更新
        pushup(u);
    }
}

Node query(int u,int l,int r)
{
    //该树区间被完全包含在被查询区间内
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    else 
    {
        int mid=tr[u].l+tr[u].r>>1;

        //该区间全部在 mid 左边
        if(r<=mid) return query(u<<1,l,r);

        //该区间全部在 mid 右边
        else if(l>mid) return query(u<<1|1,l,r);

        //该区间跨越 mid
        else 
        {
            auto left=query(u<<1,l,r);
            auto right=query(u<<1|1,l,r);
            Node res;
            pushup(res,left,right);
            return res;
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>a[i];

    build(1,1,n);

    char op;
    int l,r;
    LL d;
    while(m--)
    {
        cin>>op>>l>>r;

        //修改操作
        if(op=='C')
        {
            cin>>d;

            modify(1,l,d);

            //防止越界
            if(r+1<=n) modify(1,r+1,-d);
        }
        //查询操作
        else 
        {
            auto left=query(1,1,l);
            Node right={0,0,0,0};

            //防止越界
            if(l+1<=r) right=query(1,l+1,r);

            //gcd(a[l], gcd(b[l+1], b[l+2], ……, b[r]))
            cout<<abs(gcd(left.sum,right.d))<<endl;
        }
    }

    return 0;
}