线段树详解
https://blog.csdn.net/sjystone/article/details/115398593

https://www.acwing.com/problem/content/247/

区间最大公约数

1.区间[l,r]增加一个数
-> 差分思想,将区间加减变成单点加减，可以不用lazy标记，用线段树或树状数组维护差分
2.求区间内最大公约数

储存信息
1.最大公约数
-> 若只有查询，可以由左子区间最大公约数和右子区间最大公约数，取他们的最大公约数得到
2.sum

维护差分序列 bi = ai - ai-1
gcd(a1, a2, a3…an) = gcd(a1, a2-a1, a3-a2 … an - an-1) = gcd(a1, gcd(b2, b3 … bn)) 代码中用w代替a
-> 线段树储存差分数组b，对于差分数组b，只需要修改两个点就可等同于对数组a进行区间修改
-> 变成单点修改，区间查询

对于每个询问，求出gcd(a[l]) 和 gcd(b[l+1] ~ b[r])，输出他们的最大公约数
-> gcd(a[l]) = gcd(b1 + b2 +…+ bl)

注意：
对于区间[l,r]内的最大公约数
query(1,l+1,r)求的是gcd(al+1 - al , al+2 - al+1… ar - ar-1)
而我们需要的是gcd(a1, a2-a1, a3-a2 … an - an-1)
故要在query(1,l+1,r)的基础上再与query(1,1,l)即gcd(a[l])，取最大公约数

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 500010;
int n, m;           //n个数，m个询问
LL w[N];
struct Node{
    int l, r;
    LL sum, d;
}tr[4 * N];

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)         //建树
{
    tr[u].l = l, tr[u].r = r;
    if ( l == r ) 
        tr[u].d = w[l] - w[l - 1], tr[u].sum = w[l] - w[l - 1];
    else
    {
        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]. r == x && tr[u].l == x ) 
        tr[u].d = tr[u].sum + v, tr[u].sum += v;    
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if ( mid >= x ) 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;
        if ( mid >= r ) return query(u << 1, l, r);
        else if ( mid < l ) return query(u << 1 | 1, l, r);
        else
        {
            Node left = query(u << 1, l, r);        //如果当前访问区间的子区间横跨询问区间
            Node right = query(u << 1 | 1, l, r);   //则递归两个子区间
            Node res;                               //res相当于left和right的父区间
            pushup(res, left, right);               //相当于求right和left区间合并后的结果
            return res;
        }
    }
}

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
    build(1, 1, n);
    int l, r;
    LL d;
    char op[2];
    while ( m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if ( * op == 'C' ) 
        {
            scanf("%lld", &d);
            modify(1, l, d);                            //差分操作l处加d，r+1处减d
            if ( r + 1 <= n ) modify(1, r + 1, -d);     //注意判断r+1与n的关系
        }
        else
        {
            Node left = query(1, 1, l);                 //gcd(a[l])
            Node right = {0, 0, 0, 0};                  //若l+1>r
            if ( l + 1 <= r ) right = query(1, l + 1, r);   //gcd(b[l+1]~b[r])
            printf("%lld\n", abs(gcd(left.sum, right.d)));  //输出正数
        }
    }
    return 0;
}