群论

https://www.cnblogs.com/TSHugh/p/8567671.html

最小生成树

https://www.iteye.com/blog/dsqiu-1689178

AC自动机详解

https://bestsort.cn/2019/04/28/402/

线段树操作

（1）差分数组

传送门

牛客算法周周练：小阳的贝壳

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+6; 
typedef long long ll;
int sum[N<<2],ma[N<<2],gcd[N<<2],last=0;
int _gcd(int a,int b){return b?_gcd(b,a%b):a;}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1 
void push_up(int rt){
    //cout<<rt<<endl;
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
    gcd[rt]=_gcd(gcd[rt<<1],gcd[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        int now;
        scanf("%d",&now);
        sum[rt]=now-last;
        ma[rt]=abs(now-last);
        gcd[rt]=abs(now-last);
        last=now;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int a,int c,int l,int r,int rt){
    if(l==r){
        sum[rt]+=c;
        ma[rt]=abs(sum[rt]);
        gcd[rt]=abs(sum[rt]);
        return;
    }
    int mid=(l+r)>>1;
    if(a<=mid) update(a,c,lson);
    else update(a,c,rson);
    push_up(rt);
}
int query(int a,int b,int l,int r,int rt,int opt){
    if(a<=l&&b>=r){
        if(opt==2){
            return ma[rt];
        }else if(opt==3){
            return sum[rt];
        }else{
            return gcd[rt];
        }
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(opt==2){
        if(a<=mid) ans=max(ans,query(a,b,lson,opt));
        if(b>mid) ans=max(ans,query(a,b,rson,opt));
    }else if(opt==3){
        if(a<=mid) ans+=query(a,b,lson,opt);
        if(b>mid) ans+=query(a,b,rson,opt);
    }else{
        if(a<=mid) ans=_gcd(ans,query(a,b,lson,opt));
        if(b>mid) ans=_gcd(ans,query(a,b,rson,opt));
    }
    return ans;
}
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;++i){
        int tmp,tmp2,tmp3;
        scanf("%d",&tmp);
        if(tmp==1){
            scanf("%d%d%d",&tmp2,&tmp3,&tmp);
            update(tmp2,tmp,1,n,1);
            if(tmp3!=n) update(tmp3+1,-tmp,1,n,1);
        }else{
            scanf("%d%d",&tmp2,&tmp3);
            if(tmp==2) tmp2==tmp3?puts("0"):printf("%d
",query(tmp2+1,tmp3,1,n,1,tmp));
            else printf("%d
",_gcd(query(1,tmp2,1,n,1,3),query(tmp2+1,tmp3,1,n,1,4)));
        }
    }
}