算法1

树状数组 + 线段树

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;

ll trr[N]; // 树状数组 维护a数组的差分数组
ll a[N]; // 原数组
struct Node 
{
    int l, r;
    ll d; // 序列差分的最大公约数
} tr[N << 2];
int n, m;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, ll v)
{
    for(int i = x; i <= n; i += lowbit(i))
        trr[i] += v;
}

ll sum(int x)
{
    ll res = 0;
    for(int i = x; i; i -= lowbit(i))
        res += trr[i];
    return res;
}

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

void pushup(Node &fa, Node &l, Node &r)
{
    fa.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[r] - a[r - 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 == x && tr[u].r == x)
    {
        tr[u].d += 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(l <= tr[u].l && r >= tr[u].r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        else
        {
            Node res;
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld", &a[i]);
        add(i, a[i]), add(i + 1, -a[i]);
    }
    build(1, 1, n);

    while(m --)
    {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'Q')
        {
            // gcd(a[l] ~ a[r]) = gcd(sum(a[l]), gcd(b[l + 1] ~ b[r]))
            ll res = 0;
            if(l == r)
                res = abs(sum(l));
            else
                res = abs(gcd(sum(l), query(1, l + 1, r).d));
            printf("%lld\n", res);
        }
        else
        {
            ll x;
            scanf("%lld", &x);
            modify(1, l, x);
            if(r < n)
                modify(1, r + 1, -x);
            add(l, x);
            add(r + 1, -x);
        }
    }
    return 0;
}

算法2

线段树 （同时维护 差分序列的区间和 + 差分序列的最大公约数）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;

struct Node
{
    int l, r;
    ll sum; // 区间[l, r]的和(原序列的差分序列的区间和)
    ll d; // 区间[l, r]差分序列的最大公倍数
} tr[N << 2];
ll a[N];
int n, m;

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

void pushup(Node &fa, Node &l, Node &r)
{
    fa.d = gcd(l.d, r.d);
    fa.sum = l.sum + r.sum;
}

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)
    {
        ll b = a[r] - a[r - 1];
        tr[u] = {l, r, b, b};
    }
    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 == x && tr[u].r == x)
    {
        tr[u].d += 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(l <= tr[u].l && r >= tr[u].r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        else
        {
            Node res;
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);

    build(1, 1, n);

    while(m --)
    {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'Q')
        {
            // gcd(a[l ~ r]) = gcd(a[l], gcd(b[l + 1 ~ r]));
            // a[l] = query(1, 1, l).sum;
            // gcd(b[l + 1 ~ r]) = query(1, l + 1, r).d;
            ll res = 0;
            if(l == r)
                res = query(1, 1, l).sum;
            else 
                res = abs(gcd(query(1, 1, l).sum, query(1, l + 1, r).d));
            printf("%lld\n", res);
        }
        else
        {
            ll x;
            scanf("%lld", &x);
            modify(1, l, x);
            if(r < n)
                modify(1, r + 1, -x);
        }
    }
    return 0;
}