这个题目是一个线段树+差分+GCD
推荐一个差分的博客：https://www.cnblogs.com/cjoierljl/p/8728110.html
学会了这个简单差分之后，就可以把这个题目的区间更新转化成单点更新了，emmm...可能还是不太理解，那就说下具体思路吧。
这个题目一看感觉很难，然后就取看题解，这个看了题解之后发现裴蜀定理+线段树。
讲一下为什么是裴蜀定理+线段树，线段树应该没有什么异议，因为这个有区间更新区间查询，而且n，m的数值很大，不用线段树很容易T。
因为你要进行很多次操作，就可以列一个式子：ax1+bx2+cx3....=ans
这个式子，如果你的数论学的很好的话，就可以知道应该用裴蜀定理，这个裴蜀定理可以自己简单学习一下。
根据裴蜀定理这个最小值应该是gcd(a,b,c,d....)，所以我们就应该用线段树来求一个区间的gcd。
为什么又要用到差分呢？
因为如果你每次进行区间更新都是每一个点进行更新(只能这样，不然就无法求gcd），这样子的话，你就会发现T了。
所以我们不这么写，从刚刚的那个博客可以看出，这个可以把区间更新转化成单点更新了，就只需要更新区间左端点和区间右端点+1。
所以总结一下，这个题解法就是：
先对序列进行差分，然后用差分数列进行建树，这个要记录一个和sum和gcd val
然后就是查询，这个查询就是先查左端点的sum，然后再查左端点到右端点之间的差分的val（这个是根据裴蜀定理得出的）
然后就是更新，这个更新是只要对左端点和右端点+1进行更新就可以了。
之前是写之前的思路，接下来说说写的过程种碰到的bug，写在代码里了。
其实和普通线段树是差不多的，但是就是会有很多小bug没注意到。
线段树的bug还是很难找的。
写一下我对于差分的理解：
如果你碰到你要更新一个区间，给这个区间上的每一个数都加上一个x，让你求n次操作之后求一个区间总和。
又有时间限制，不可以一个一个的去加，这个时候就可以用上差分了。
就是先将这个数列进行差分得到一个差分数列，然后就是对于这个区间的第一位+x，
最后一位的后面一位-x。
这样子操作n次之后再用前缀和求出原来的数列，最后原来的数列再运算即可。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 10;
struct node
{
int l, r;
int sum, val;
}tree[maxn*4];
int a[maxn];
int gcd(int a,int b)
{
return b == 0 ? a : gcd(b, a%b);
}
void push_up(int id)
{
tree[id].sum = tree[id << 1].sum + tree[id << 1 | 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(tree[id].l==tree[id].r)
{
tree[id].sum = tree[id].val = 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 l,int r)//求到第区间第一个的真实值
{
if(l<=tree[id].l&&r>=tree[id].r)
{
return tree[id].sum;
}
int mid = (tree[id].l + tree[id].r)>>1, ans = 0;
if (l <= mid) ans += query_sum(id << 1, l, r);
if(r>mid) ans += query_sum(id << 1 | 1, l, r);
return ans;
}
int query_val(int id,int l,int r)//求区间除开第一个的差分gcd
{
if(l<=tree[id].l&&r>=tree[id].r)
{
return tree[id].val;
}
int mid = (tree[id].l + tree[id].r) >> 1, ans = 0;
if (l <= mid) ans = gcd(ans, query_val(id << 1, l, r));
if (r > mid) ans = gcd(ans, query_val(id << 1 | 1, l, r));
return ans;
}
void update(int id,int p,int x)
{
if (p > tree[id].r) return;
if(tree[id].l==tree[id].r)
{
tree[id].sum += x;
tree[id].val += x;
return;
}
int mid = (tree[id].l + tree[id].r) >> 1;
if (p <= mid) update(id << 1, p, x);
else update(id << 1 | 1, p, 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);
for (int i = 1; i <= m; i++)
{
int p, l, r;
scanf("%d%d%d", &p, &l, &r);
if (l > r) swap(l, r);//这个其实交换不交换都差不多
if (p == 1)
{
int exa1 = query_sum(1, 1, l);//去查找第i个数的真实值
int exa2 = query_val(1, l + 1, r);//i到r之间的gcd
int ans = abs(gcd(exa1,exa2));//因为是进行差分了，所以gcd之后也有可能有负值
printf("%d
", ans);
}
else
{
int x;
scanf("%d", &x);
update(1, l, x);//差分的更新
update(1, r + 1, -x);
}
}
return 0;
}