这是一篇关于数据结构模板的文章 这些是其他模板分类的链接

并查集

• P3367 【模板】并查集

class mfs{
    int f[N];

    public:

    void init(int x){
        iota(f+1,f+x+1,1);
    }

    int find(int x){
        return f[x]==x ? x : f[x]=find(f[x]);
    }

    bool merge(int x, int y){
        x=find(x), y=find(y);
        if(x==y) return 0;
        f[y]=x;
        return 1;
    }
};

ST 表

• P3865 【模板】ST 表

int n,a[N],dp[L][N];

void init(){
    for(int i=1; i<=n; i++) dp[0][i]=a[i];

    int t=log2(n);
    for(int i=1; i<=t; i++){
        for(int j=1; j+(1<<i)-1<=n; j++) dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<i-1)]);
    }
}

int query(int l, int r){
    int t=log2(r-l+1);
    return max(dp[t][l],dp[t][r-(1<<t)+1]);
}

树状数组

单点修改，区间查询

• P3374 【模板】树状数组 1

int n;

class fen{
    int c[N];

    int sum(int x){
        int s=0;
        for(int i=x; i; i&=i-1) s+=c[i];
        return s;
    }

    public:

    void update(int p, int x){
        for(int i=p; i<=n; i+=i&-i) c[i]+=x;
    }

    int query(int l, int r){
        return sum(r)-sum(l-1);
    }
};
                          

区间修改，单点查询

• P3368 【模板】树状数组 2

int n;

class fen{
    int c[N];

    void add(int p, int x){
        for(int i=p; i<=n; i+=i&-i) c[i]+=x;
    }

    public:

    void update(int l, int r, int x){
        add(l,x), add(r+1,-x);
    }

    int query(int x){
        int s=0;
        for(int i=x; i; i&=i-1) s+=c[i];
        return s;
    }
};

线段树

单种修改，单种查询

• P3372 【模板】线段树 1

#define L x<<1
#define R x<<1|1

long long a[N];

class seg{
    long long t[N<<2];

    struct{
        int l,r;
        long long w;
    }s[N<<2];
    
    void add(int x, long long w){
        t[x]+=w, s[x].w+=w*(s[x].r-s[x].l+1);
    }

    void down(int x){
        if(t[x]) add(L,t[x]), add(R,t[x]), t[x]=0;
    }

    void up(int x){
        s[x].w=s[L].w+s[R].w;
    }

    public:

    void build(int x, int l, int r){
        s[x]={l,r}, t[x]=0;
        if(l==r){
            s[x].w=a[l];
            return;
        }

        int m=l+r>>1;
        build(L,l,m), build(R,m+1,r);
        up(x);
    }

    void update(int x, int l, int r, long long w){
        if(s[x].l>r || s[x].r<l) return;
        if(s[x].l>=l && s[x].r<=r){
            add(x,w);
            return;
        }

        down(x);
        update(L,l,r,w), update(R,l,r,w);
        up(x);
    }

    long long query(int x, int l, int r){
        if(s[x].l>r || s[x].r<l) return 0;
        if(s[x].l>=l && s[x].r<=r) return s[x].w;

        down(x);
        return query(L,l,r)+query(R,l,r);
    }
};

多种修改，单种查询

• P3373 【模板】线段树 2

#define L x<<1
#define R x<<1|1

long long a[N],MOD;

class seg{
    long long t1[N<<2],t2[N<<2];

    struct{
        int l,r;
        long long w;
    }s[N<<2];
    
    void add(int x, long long w, bool f){
        if(f) t1[x]=t1[x]*w%MOD, t2[x]=t2[x]*w%MOD, s[x].w=s[x].w*w%MOD;
        else t2[x]=(t2[x]+w)%MOD, s[x].w=(s[x].w+w*(s[x].r-s[x].l+1))%MOD;
        return;
    }

    void down(int x){
        if(t1[x]!=1) add(L,t1[x],1), add(R,t1[x],1), t1[x]=1;
        if(t2[x]) add(L,t2[x],0), add(R,t2[x],0), t2[x]=0;
    }

    void up(int x){
        s[x].w=(s[L].w+s[R].w)%MOD;
    }

    public:

    void build(int x, int l, int r){
        s[x]={l,r}, t1[x]=1, t2[x]=0;
        if(l==r){
            s[x].w=a[l]%MOD;
            return;
        }

        int m=l+r>>1;
        build(L,l,m), build(R,m+1,r);
        up(x);
    }

    void update(int x, int l, int r, long long w, bool f){
        if(s[x].l>r || s[x].r<l) return;
        if(s[x].l>=l && s[x].r<=r){
            add(x,w,f);
            return;
        }

        down(x);
        update(L,l,r,w,f), update(R,l,r,w,f);
        up(x);
    }

    long long query(int x, int l, int r){
        if(s[x].l>r || s[x].r<l) return 0;
        if(s[x].l>=l && s[x].r<=r) return s[x].w;

        down(x);
        return (query(L,l,r)+query(R,l,r))%MOD;
    }
};

多种修改，多种查询

• P2572 [SCOI2010] 序列操作

#define L x<<1
#define R x<<1|1

int a[N];

struct node{
    int l,r,c,s0,s1,sl,sr;
    bool fl,fr;
    
    node operator +(node x){
        node t={l,x.r,c+x.c,max(s0,x.s0),max(s1,x.s1),sl,x.sr,fl,x.fr};
        
        if(fr && x.fl){
            t.s1=max(t.s1,sr+x.sl);
            if(sl==r-l+1) t.sl+=x.sl;
            if(x.sr==x.r-x.l+1) t.sr+=sr;
        }
        else if(!fr && !x.fl){
            t.s0=max(t.s0,sr+x.sl);
            if(sl==r-l+1) t.sl+=x.sl;
            if(x.sr==x.r-x.l+1) t.sr+=sr;
        }
        
        return t;
    }
};

class seg{
    int t[N<<2];
    node s[N<<2];
    
    void add(int x, int w){
        if(w==2){
            t[x]= t[x]==2 ? -1 : ~t[x] ? !t[x] : 2;
            s[x].fl=!s[x].fl, s[x].fr=!s[x].fr, s[x].c=s[x].r-s[x].l-s[x].c+1, swap(s[x].s0,s[x].s1);
        }
        else if(~w){
            t[x]=s[x].fl=s[x].fr=w, s[x].sl=s[x].sr=s[x].r-s[x].l+1;
            if(w) s[x].c=s[x].s1=s[x].r-s[x].l+1, s[x].s0=0;
            else s[x].s0=s[x].r-s[x].l+1, s[x].c=s[x].s1=0;
        }
    }

    void down(int x){
        if(~t[x]) add(L,t[x]), add(R,t[x]), t[x]=-1;
    }

    void up(int x){
        s[x]=s[L]+s[R];
    }

    public:

    void build(int x, int l, int r){
        s[x]={l,r}, t[x]=-1;
        if(l==r){
            s[x].fl=s[x].fr=s[x].c=s[x].s1=a[l], s[x].s0=!a[l], s[x].sl=s[x].sr=1;
            return;
        }

        int m=l+r>>1;
        build(L,l,m), build(R,m+1,r);
        up(x);
    }

    void update(int x, int l, int r, int w){
        if(s[x].l>r || s[x].r<l) return;
        if(s[x].l>=l && s[x].r<=r){
            add(x,w);
            return;
        }

        down(x);
        update(L,l,r,w), update(R,l,r,w);
        up(x);
    }

    node query(int x, int l, int r){
        if(s[x].l>r || s[x].r<l) return {s[x].l,s[x].r};
        if(s[x].l>=l && s[x].r<=r) return s[x];
        
        down(x);
        return query(L,l,r)+query(R,l,r);
    }
};