如果线段树要维护区间gcd 这个很简单，但是如果有了区间加，维护gcd 就比较麻烦了。
这个首先可以证明的是 gcd(x,y,z)=gcd(x,y-x,z-y) 这个可以推到 n 个
这个就和差分扯上关系了 可以看一下差分 差分传送门
上面的这两个博客基本上告诉我们这两个题目怎么写了。
首先我们对于每一个数进行处理，把这个数变成差分的形式，
因为最后的结果我们要 gcd(x,y-x,z-y) 所以我们要求和，还有求gcd ，这个就会有两个查询，一个查询sum，一个查询gcd
你看了差分的博客后你就发现，如果我们要给一段区间整体加上一个值，这个区间更新可以转化成差分的单点更新。
然后就是区间差值最大，这个很好求，因为我们每一个数本来放进去的就是区间的差分，所以这个相当于在求最大值。只是注意边界。
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <string> #include <iostream> #include <map> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 2e5 + 10; int a[maxn]; struct node { int l, r; int max, sum, val; }tree[maxn*4]; int gcd(int a,int b) { return b == 0 ? a : gcd(b, a%b); } void push_up(int id) { tree[id].max = max(abs(tree[id << 1].max), abs(tree[id << 1 | 1].max)); tree[id].sum = tree[id << 1 | 1].sum + tree[id << 1].sum; tree[id].val = gcd(tree[id << 1].val, tree[id << 1 | 1].val); } void build(int id,int l,int r) { tree[id].l = l; tree[id].r = r; if(l==r) { tree[id].sum = tree[id].val = a[l]; tree[id].max = abs(a[l]); return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); push_up(id); } int query_sum(int id,int x,int y) { int l = tree[id].l; int r = tree[id].r; if(x<=l&&y>=r) { return tree[id].sum; } int ans = 0; int mid = (l + r) >> 1; if (x <= mid) ans += query_sum(id << 1, x, y); if (y > mid) ans += query_sum(id << 1 | 1, x, y); return ans; } int query_val(int id,int x,int y) { int l = tree[id].l; int r = tree[id].r; if(x<=l&&y>=r) { return tree[id].val; } int ans = 0; int mid = (l + r) >> 1; if (x <= mid) ans = gcd(ans, query_val(id << 1, x, y)); if (y > mid) ans = gcd(ans, query_val(id << 1 | 1, x, y)); return ans; } int query_max(int id,int x,int y) { int l = tree[id].l; int r = tree[id].r; if(x<=l&&y>=r) { return tree[id].max; } int ans = 0; int mid = (l + r) >> 1; if (x <= mid) ans = max(ans, query_max(id << 1, x, y)); if (y > mid) ans = max(ans, query_max(id << 1 | 1, x, y)); return ans; } void update(int id,int pos,int x) { int l = tree[id].l; int r = tree[id].r; if(l==r) { tree[id].sum += x; tree[id].val += x; tree[id].max = abs(tree[id].val); return; } int mid = (l + r) >> 1; if (pos <= mid) update(id << 1, pos, x); else update(id << 1 | 1, pos, x); push_up(id); } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = n; i >= 1; i--) a[i] = a[i] - a[i - 1]; build(1, 1, n); while (m--) { int opt, l, r, x; scanf("%d", &opt); if(opt==1) { scanf("%d%d%d", &l, &r, &x); if (l > r) swap(l, r); update(1, l, x); if(r+1<=n) update(1, r + 1, -x); } if(opt==2) { scanf("%d%d", &l, &r); if (l > r) swap(l, r); int ans = 0; if(l!=r) ans = query_max(1, l + 1, r); printf("%d ", ans); } if(opt==3) { scanf("%d%d", &l, &r); if (l > r) swap(l, r); int ans = 0; int ex1 = query_sum(1, 1, l); int ex2 = query_val(1, l + 1, r); if (l == r) ans = ex1; else ans = abs(gcd(ex1, ex2)); printf("%d ", ans); } // if(opt==4) // { // scanf("%d", &l); // printf("%d ", query_sum(1, 1, l)); // } } return 0; }