· 主席树

1、不带修主席树

俗称静态区间第k小

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#define N 200000+100
using namespace std;

int a[N],Hash[N],T[N],tot,n,m,t[N];
int sum[50*N],L[50*N],R[50*N];
int build(int l,int r)
{
    int rt=++tot;
    sum[rt]=0;
    if(l<r)
    {
        int mid=(l+r)/2;
        L[rt]=build(l,mid);
        R[rt]=build(mid+1,r);
    }
    return rt;
}

int update(int pre,int l,int r,int x)
{
    int rt=++tot;
    L[rt]=L[pre];
    R[rt]=R[pre];
    sum[rt]=sum[pre]+1;
    if(l<r)
    {
        int m=(l+r)/2;
        if(x<=m)
            L[rt]=update(L[pre],l,m,x);
        else R[rt]=update(R[pre],m+1,r,x);
    }
    return rt;
}
int query(int u,int v,int l,int r,int k)
{
    if(l==r)return l;
    int num=sum[L[v]]-sum[L[u]];
    int m=(l+r)/2;
    if(num>=k)return query(L[u],L[v],l,m,k);
    else return query(R[u],R[v],m+1,r,k-num);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),Hash[i]=a[i];
    sort(Hash+1,Hash+1+n);
    int d=unique(Hash+1,Hash+1+n)-Hash-1;
    t[0]=build(1,d);
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(Hash+1,Hash+1+d,a[i])-Hash;
        t[i]=update(t[i-1],1,d,x);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        int x=query(t[l-1],t[r],1,d,k);
        printf("%d\n",Hash[x]);
    }

    return 0;
}

2、带修主席树

支持单点修改的区间最值

与树状数组结合使用

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#define N 200000+100
using namespace std;

int a[N],Hash[N],tot,n,m,t[N],s[N],use[N],d;
int sum[50*N],L[50*N],R[50*N];
struct node
{
    int flag,l,r,k;
}q[N];
int lowbit(int x)
{
   return x&(-x);
}
int getsum(int x)
{
    int tot=0;
    while(x>0)
    {
        tot+=sum[L[use[x]]];
        x-=lowbit(x);
    }
    return tot;
}
int build(int l,int r)
{
    int rt=++tot;
    if(l<r)
    {
        int mid=(l+r)/2;
        L[rt]=build(l,mid);
        R[rt]=build(mid+1,r);
    }
    return rt;
}

int update(int pre,int l,int r,int x,int dd)
{
    int rt=++tot;
    L[rt]=L[pre];
    R[rt]=R[pre];
    sum[rt]=sum[pre]+dd;
    if(l<r)
    {
        int m=(l+r)/2;
        if(x<=m)
            L[rt]=update(L[pre],l,m,x,dd);
        else R[rt]=update(R[pre],m+1,r,x,dd);
    }
    return rt;
}
int query(int u,int v,int ll,int rr,int l,int r,int k)
{

    if(l>=r)return l;
    int m=(l+r)/2;
    int aa=getsum(v);
    int bb=getsum(u);
    int num=aa-bb+sum[L[rr]]-sum[L[ll]];
    if(k<=num)
    {
        for(int j=u;j>0;j=j-lowbit(j))use[j]=L[use[j]];
        for(int j=v;j>0;j=j-lowbit(j))use[j]=L[use[j]];
        return query(u,v,L[ll],L[rr],l,m,k);

    }
    else
    {
        for(int j=u;j>0;j=j-lowbit(j))use[j]=R[use[j]];
        for(int j=v;j>0;j=j-lowbit(j))use[j]=R[use[j]];
        return query(u,v,R[ll],R[rr],m+1,r,k-num);
    }

}
void modify(int x,int p,int dd)
{
    while(x<=n)
    {
        s[x]=update(s[x],1,d,p,dd);
        x+=lowbit(x);
    }
}
int main()
{
    int dd=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),Hash[++dd]=a[i];
    char ss[10];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ss);
        if(ss[0]=='Q')
        {
            scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
            q[i].flag=1;
        }
        else
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            Hash[++dd]=q[i].r;
            q[i].flag=0;
        }
    }
    sort(Hash+1,Hash+1+dd);
     d=unique(Hash+1,Hash+1+dd)-Hash-1;
    t[0]=build(1,d);
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(Hash+1,Hash+1+d,a[i])-Hash;
        t[i]=update(t[i-1],1,d,x,1);
    }
    for(int i=1;i<=n;i++)s[i]=t[0];
    for(int i=1;i<=m;i++)
    {
        if(q[i].flag)
        {
            for(int j=q[i].l-1;j>0;j=j-lowbit(j))use[j]=s[j];
            for(int j=q[i].r;j>0;j=j-lowbit(j))use[j]=s[j];
            int tt=query(q[i].l-1,q[i].r,t[q[i].l-1],t[q[i].r],1,d,q[i].k);
            printf("%d\n",Hash[tt]);
        }
        else
        {
            int xx=lower_bound(Hash+1,Hash+1+d,a[q[i].l])-Hash;
            int yy=lower_bound(Hash+1,Hash+1+d,q[i].r)-Hash;
            modify(q[i].l,xx,-1);
            modify(q[i].l,yy,1);
           a[q[i].l]=q[i].r;
        }
    }

    return 0;
}

· 线段树

这个东西很傻逼，早年码风懒得改了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define N 200000+100
using namespace std;
struct node
{
    int lt;
    int rt;
    long long val;
    long long sum;
}a[4*N];
int n,m,data[N];
void pushup(int p)
{
   a[p].sum=a[2*p].sum+a[2*p+1].sum;
}
void build(int p,int l,int r)
{
    a[p].lt=l;
    a[p].rt=r;
    if(l==r){a[p].sum=data[l];return;}
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
   pushup(p);
}
void pushdown(int p)
{
     if(a[p].val!=0)
    {
        a[2*p].val+=a[p].val;
        a[2*p].sum+=(a[2*p].rt-a[2*p].lt+1)*a[p].val;
        a[2*p+1].val+=a[p].val;
        a[2*p+1].sum+=(a[2*p+1].rt-a[2*p+1].lt+1)*a[p].val;
        a[p].val=0;
    }

}
void update(int p,int l,int r,long long d)
{
    if(a[p].lt==l&&a[p].rt==r){a[p].val+=d;a[p].sum+=(r-l+1)*d;return;}
    pushdown(p);
    int mid=(a[p].lt+a[p].rt)/2;
    if(r<=mid)update(2*p,l,r,d);
    else if(l>mid)update(2*p+1,l,r,d);
         else {update(2*p,l,mid,d);update(2*p+1,mid+1,r,d);}
   pushup(p);
}
long long query(int p,int l,int r)
{
    if(a[p].lt==l&&a[p].rt==r)return a[p].sum;
    pushdown(p);
    int mid=(a[p].lt+a[p].rt)/2;
    if(r<=mid)return query(2*p,l,r);
    else if(l>mid)return query(2*p+1,l,r);
         else return query(2*p,l,mid)+query(2*p+1,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&data[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        long long dd;
        cin>>z;
        if(z==1){scanf("%d%d%lld",&x,&y,&dd);update(1,x,y,dd);}
        else {scanf("%d%d",&x,&y);printf("%d\n",query(1,x,y));}
    }
    return 0;
}

· 树状数组

１、单点修改＋区间求和

早年代码*2

#include <bits/stdc++.h>
#define N 500000+100
using namespace std;
int tree[N*4],n,m;
void add(int x,int k)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=x&(-x);
    }
}
int getsum(int x)
{
    int sum=0;
    while(x!=0)
    {
        sum+=tree[x];
        x-=x&(-x);

    }
    return sum;
}
int main()
{
     cin>>n>>m;
     for(int i=1;i<=n;i++)
     {
         int a;
         cin>>a;
         add(i,a);
     }
     for(int i=1;i<=m;i++)
     {
         int x,y,z;
         cin>>x>>y>>z;
         if(x==1)add(y,z);
         else cout<<getsum(z)-getsum(y-1)<<endl;
     }
    return 0;
}

2、单点修改+单点查询

早年代码*3

#include <bits/stdc++.h>
#define N 500000+100
using namespace std;
int tree[N*4],n,m,data[N*4];
void add(int x,int k)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=x&(-x);
    }
}
int getsum(int x)
{
    int sum=0;
    while(x!=0)
    {
        sum+=tree[x];
        x-=x&(-x);

    }
    return sum;
}
int main()
{
     cin>>n>>m;
     for(int i=1;i<=n;i++)cin>>data[i];
     for(int i=1;i<=m;i++)
     {
         int x,y,z,d;
         cin>>d;
         if(d==1)
         {
             cin>>x>>y>>z;
             add(x,z);
             add(y+1,-z);
         }
         else

         {
             cin>>x;
             cout<<data[x]+getsum(x)<<endl;
         }
     }
    return 0;
}

· 莫队

1、普通莫队

例题
[国家集训队]小Z的袜子

#include <bits/stdc++.h>
#define N 100000+110
#define ll long long
using namespace std;
int n,m,blo,cnt,col;
ll ans,fenzi[N],fenmu[N];
int a[N],bel[N];
ll num[N];
struct node
{
    ll l,r,id,len;
}ask[N];

inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(f=='-')
            f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline bool cmp(node x,node y)
{
    if(bel[x.l]==bel[y.l])
    {
        return bel[x.r]<bel[y.r];
    }
    return bel[x.l]<bel[y.l];
}
inline void add(int x)
{
    num[x]++;
   if(num[x]>1)ans=ans+num[x]*(num[x]-1)-(num[x]-1)*(num[x]-2);

}
inline void Minus(int x)
{
    num[x]--;
    if(num[x]>0)ans=ans+num[x]*(num[x]-1)-num[x]*(num[x]+1);

}
ll gcd(ll a,ll b)
{
    return !b?a:gcd(b,a%b);

}
int main()
{

    n=read();
    m=read();
    blo=sqrt(n);
    for(register int i=1;i<=n;i++)
    {
        a[i]=read();
        bel[i]=(i-1)/blo+1;
    }
    for(register int i=1;i<=m;i++)
    {
        ask[i].l=read();
        ask[i].r=read();
        ask[i].len=ask[i].r-ask[i].l;
        ask[i].id=i;

    }
    sort(ask+1,ask+1+m,cmp);
    ll L=1;
    ll R=0;
    for(register int i=1;i<=m;i++)
    {
       if(ask[i].l==ask[i].r)
       {
           fenzi[ask[i].id]=0;fenmu[ask[i].id]=1;continue;
       }
        while(L>ask[i].l)
        {
            L--;
            add(a[L]);
        }
        while(R<ask[i].r)
        {
            R++;
            add(a[R]);
        }
        while(L<ask[i].l)
        {
            Minus(a[L]);
            L++;
        }
        while(R>ask[i].r)
        {
            Minus(a[R]);
            R--;
        }
        if(ans==0)
        {
           fenzi[ask[i].id]=0;fenmu[ask[i].id]=1;continue;
        }
       ll sum=ask[i].len*(ask[i].len+1);
       ll GCD=gcd(sum,ans);
       fenzi[ask[i].id]=ans/GCD;fenmu[ask[i].id]=sum/GCD;


    }
    for(register int i=1;i<=m;i++)
        printf("%lld/%lld\n",fenzi[i],fenmu[i]);
    return 0;
}

2、 带改莫队

例题

P1903 [国家集训队]数颜色 / 维护队列

luogu 卡常注意

#include <bits/stdc++.h>
#define N 50000+110
#define M 1000000+110
using namespace std;
int bl[N],n,m,p,now[N],a[N],out[N],maxx,b[M],last[M];
int tag[N],pre[M],cnum,qnum,col[M],ans;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct node
{
    int pre,l,r,id;
}q[N];

inline bool mmp(node x,node y)
{
    if(bl[x.l]==bl[y.l])
    {
        if(bl[x.r]==bl[y.r])
            return x.pre<y.pre;
        return bl[x.r]<bl[y.r];
    }
    return bl[x.l]<bl[y.l];
}
struct change
{
    int pos,v,old;
}c[N];
inline void del(int val)
{
    if(--col[val]==0)ans--;
}
inline void add(int val)
{
    if(++col[val]==1)ans++;
}
inline void work(int l,int r,int x,int d)
{
    if(l<=x&&x<=r)
    {
        add(d);
        del(a[x]);
    }
    a[x]=d;
}

inline void modui()
{
    int L=1,R=0,Now=0;
    for(int i=1;i<=qnum;i++)
    {
        while(Now<q[i].pre)Now++,work(L,R,c[Now].pos,c[Now].v);//小于当前操作，换成新的
        while(Now>q[i].pre)work(L,R,c[Now].pos,c[Now].old),Now--;//大于当前操作，换成 旧的
        while(L<q[i].l)del(a[L]),L++;
        while(L>q[i].l)L--,add(a[L]);
        while(R<q[i].r)R++,add(a[R]);
        while(R>q[i].r)del(a[R]),R--;

        out[q[i].id]=ans;

    }
    for(int i=1;i<=qnum;i++)
        printf("%d\n",out[i]);

}
int main()
{

   n=read();m=read();
    p=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        now[i]=a[i];
        bl[i]=(i-1)/p+1;
    }
    for(int i=1;i<=m;i++)
    {
        char op[3];
        scanf("%s",op);
        if(op[0]=='Q')
        {
            q[++qnum].l=read();
            q[qnum].r=read();
            q[qnum].pre=cnum;
            q[qnum].id=qnum;
        }
        else
        {
            c[++cnum].pos=read();
            c[cnum].v=read();
            c[cnum].old=now[c[cnum].pos];
            now[c[cnum].pos]=c[cnum].v;
        }
    }
    sort(q+1,q+1+qnum,mmp);
    modui();

    return 0;
}

3、二维莫队

详见二维莫队

板子合集水水水水~ ~ ~ 主要是自己复习用的啦