数据结构模板

dream_qwq · 2022-11-21 13:04:06 · 算法·理论

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

并查集

• 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 表](https://www.luogu.com.cn/problem/P3865)
```cpp
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](https://www.luogu.com.cn/problem/P3368)
```cpp
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](https://www.luogu.com.cn/problem/P3373)
```cpp
#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);
}

};