数据结构学习笔记

很早就想写的东西，最近才有时间写。主要是不想改错

树状数组

支持维护前缀和或者是前缀最大值之类的东西，支持单点修改。

基本只有维护前缀才会想到这个，其余的情况用线段树替代。

Code

int c[N],n;
int ask(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))ans+=c[x];
    return ans;
}
void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x))c[x]+=y;
}

线段树

用处多的很，支持区间修改和区间查询，以及可以在线段树上二分。

扫描线可以在维护矩形的周长并或者面积并时用到。

Code

int a[N];
struct Segment_Tree
{
    struct sss
    {
        int l,r;
        long long sum,add;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define sum(x) tree[x].sum
        #define add(x) tree[x].add
    }tree[1000005];
    void build(int x,int l,int r)
    {
        l(x)=l;r(x)=r;
        if(l==r)
        {
            sum(x)=a[l];
            return;
        }
        int mid=(l(x)+r(x))>>1;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        sum(x)=sum(x*2)+sum(x*2+1);
    }
    void spread(int x)
    {
        if(add(x))
        {
            add(x*2)+=add(x);
            add(x*2+1)+=add(x);
            sum(x*2)+=add(x)*(r(x*2)-l(x*2)+1);
            sum(x*2+1)+=add(x)*(r(x*2+1)-l(x*2+1)+1);
            add(x)=0;
        }
    }
    void change(int x,int l,int r,int p)
    {
        if(l<=l(x)&&r(x)<=r)
        {
            sum(x)+=p*(r(x)-l(x)+1);
            add(x)+=p;
            return;
        }
        spread(x);
        int mid=(l(x)+r(x))>>1;
        if(l<=mid)change(x*2,l,r,p);
        if(mid<r)change(x*2+1,l,r,p);
        sum(x)=sum(x*2)+sum(x*2+1);
    }
    long long ask(int x,int l,int r)
    {
        if(l<=l(x)&&r(x)<=r)return sum(x);
        spread(x);
        int mid=(l(x)+r(x))>>1;
        long long res=0;
        if(l<=mid)res+=ask(x*2,l,r);
        if(mid<r)res+=ask(x*2+1,l,r);
        return res;
    }
}T1;

分块

将序列分成若干块，大段维护，局部朴素。块长一般取 $\sqrt{n}$。

具体来说就是对于操作 $[l,r]$，设 $l$ 在块 $bl$ ，$r$ 在 $br$ 。

• 如果 $br-bl=1$ 就直接暴力。

• 否则对于 $[bl+1,br-1]$ 的块，直接在块上查询/修改；

  然后暴力查询/修改剩下的部分。

Code P4168 [Violet]蒲公英

#include<algorithm>
#include<cmath>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
int T,L,n,a[50005],s[505][50005],f[505][505],d[50005],sum,cnt,x,g[50005];
map<int,int>mp;
int main()
{
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        d[i]=a[i];
    }
    sort(d+1,d+n+1);
    sum=unique(d+1,d+n+1)-1-d;
    for(int i=1;i<=sum;i++)mp[d[i]]=i;
    for(int i=1;i<=n;i++)a[i]=mp[a[i]];
    L=sqrt(n);
    cnt=(n-1)/L+1;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=(i-1)*L+1;j<=min(i*L,n);j++)s[i][a[j]]++;
        for(int j=1;j<=sum;j++)s[i][j]+=s[i-1][j];
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i;j<=cnt;j++)
        {
            int mx=f[i][j-1];
            for(int k=(j-1)*L;k<=min(j*L,n);k++)if((s[j][a[k]]-s[i-1][a[k]]>s[j][mx]-s[i-1][mx])||(s[j][a[k]]-s[i-1][a[k]]==s[j][mx]-s[i-1][mx]&&a[k]<mx))mx=a[k];
            f[i][j]=mx;
        }
    }
    while(T--)
    {
        memset(g,0,sizeof(g));
        int l,r;
        scanf("%d%d",&l,&r);
        l=((l+x-1)%n)+1;
        r=((r+x-1)%n)+1;
        if(l>r)swap(l,r);
        int bl=(l-1)/L+1,br=(r-1)/L+1,mx;
        if(br-bl<=1)
        {
            for(int i=l;i<=r;i++)g[a[i]]++;
            for(int i=l;i<=r;i++)if(g[a[i]]>g[mx]||(g[a[i]]==g[mx]&&a[i]<mx))mx=a[i];
        }
        else
        {
            for(int i=l;i<=L*bl;i++)g[a[i]]++;
            for(int i=L*(br-1)+1;i<=r;i++)g[a[i]]++;
            mx=f[bl+1][br-1];
            for(int i=l;i<=L*bl;i++)
            {
                int pre=g[mx]+s[br-1][mx]-s[bl][mx],now=g[a[i]]+s[br-1][a[i]]-s[bl][a[i]];
                if(now>pre||(now==pre&&mx>a[i]))mx=a[i];
            }
            for(int i=L*(br-1)+1;i<=r;i++)
            {
                int pre=g[mx]+s[br-1][mx]-s[bl][mx],now=g[a[i]]+s[br-1][a[i]]-s[bl][a[i]];
                if(now>pre||(now==pre&&mx>a[i]))mx=a[i];
            }
        }
        x=d[mx];
        printf("%d\n",x);
    }
}

以及，分块可以维护插入和删除操作，我们可以将分块存在一个链表上面，块首单独存在另一个一个链表上面，找块的时候直接在这个链表上面跳即可。

• 对于插入，我们直接插在所对应的块里面，如果该块长超过了 $2\sqrt{n}$，就把它分成两部分；
• 对于删除，直接删即可，如果该块为空，删除这个块。

莫队

对询问进行分块，将左端点排序，分成 $\sqrt{n}$ 块，每块内部再按照右端点排序。

这样就可以以上次的询问为基础，在 $\sqrt{n}$ 的时间里更新答案。

Code P1494 [国家集训队] 小 Z 的袜子

#include<algorithm>
#include<cmath>
#include<iostream>
#define int long long
using namespace std;
struct sss
{
    int l,r,id;
}a[100005];
int s[100005],n,T,ans[100005][2],an1,an2,f[1005][50005],L,cnt,sum[100005],l,r;
bool cmp(sss a,sss s)
{
    int x=(a.l-1)/L+1;
    int y=(s.l-1)/L+1;
    if(x==y)return a.r>s.r;
    return x<y;
}
void add(int x)
{
    sum[x]++;
    if(sum[x]>1)an1=an1+sum[x]*(sum[x]-1)-(sum[x]-1)*(sum[x]-2);
}
void del(int x)
{
    sum[x]--;
    if(sum[x]>0)an1=an1+sum[x]*(sum[x]-1)-(sum[x]+1)*sum[x];
}
void get(int x,int y,int i)
{
    if(x==0)
    {
        ans[i][0]=0;
        ans[i][1]=1;
        return;
    }
    int gcd=__gcd(x,y);
    ans[i][0]=x/gcd;
    ans[i][1]=y/gcd;
}
signed main()
{
    scanf("%lld%lld",&n,&T);
    L=sqrt(T);
    cnt=(T-1)/L+1;
    for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
    for(int i=1;i<=T;i++)scanf("%lld%lld",&a[i].l,&a[i].r),a[i].id=i;
    sort(a+1,a+T+1,cmp);
    for(int i=a[1].l;i<=a[1].r;i++)add(s[i]);
    an2=(a[1].r-a[1].l+1)*(a[1].r-a[1].l);
    get(an1,an2,a[1].id);
    l=a[1].l;r=a[1].r;
    for(int i=2;i<=T;i++)
    {
        while(l<a[i].l)del(s[l++]);
        while(l>a[i].l)add(s[--l]);
        while(r<a[i].r)add(s[++r]);
        while(r>a[i].r)del(s[r--]);
        an2=(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
        if(l==r)ans[a[i].id][0]=0,ans[a[i].id][1]=1;
        else get(an1,an2,a[i].id);
    }
    for(int i=1;i<=T;i++)printf("%lld/%lld\n",ans[i][0],ans[i][1]);
}

平衡树

终于到了平衡树了。

FHQ，也就是无旋 Treap ，与 Treap 相似，都是运用堆性质来维护树高。

FHQ 的核心主要是两种操作：split 和 merge。

• splitv 是将 FHQ 分裂成两颗树 $x$ 和 $y$，满足 $x$ 的所有节点权值均小于 $key$ 小于 $y$ 中节点。（$key$ 自己定，大于小于看题目情况）

  splits 是将 FHQ 分裂成两颗树 $x$ 和 $y$，满足 $x$ 的节点个数为 $s$。（$s$ 自己定）

• merge 是将 $x$ 和 $y$ 合并成一颗树，在中序遍历中，$x$ 中节点的位置将在 $y$ 的节点的右边。

这是详解。

有了这个，剩下的都可以自己推了。

Code

#include<iostream>
using namespace std;
struct FHQ
{
    int cnt,root;
    struct sss
    {
        int r,l,s,w,v;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define s(x) tree[x].s
        #define w(x) tree[x].w
        #define v(x) tree[x].v
    }tree[100005];
    void build(){cnt=0;}
    int New(int x)
    {
        w(++cnt)=rand();
        v(cnt)=x;
        s(cnt)=1;
        return cnt;
    }
    void pushup(int x){s(x)=s(l(x))+s(r(x))+1;}
    void splitv(int root,int key,int &x,int &y)
    {
        if(!root)x=y=0;
        else if(v(root)<=key)
        {
            x=root;
            splitv(r(root),key,r(x),y);
            pushup(root);
        }
        else
        {
            y=root;
            splitv(l(root),key,x,l(y));
            pushup(root);
        }
    }
    void splits(int root,int s,int &x,int &y)
    {
        if(!root)x=y=0;
        else if(s(l(root))<s)
        {
            x=root;
            splits(r(root),s-s(l(root))-1,r(x),y);
            pushup(root);
        }
        else
        {
            y=root;
            splits(l(root),s,x,l(y));
            pushup(root);
        }
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x^y;
        else if(w(x)>w(y))
        {
            r(x)=merge(r(x),y);
            pushup(x);
            return x;
        }
        else
        {
            l(y)=merge(x,l(y));
            pushup(y);
            return y;
        } 
    }
    void insert(int key)
    {
        int x,y;
        splitv(root,key-1,x,y);
        root=merge(merge(x,New(key)),y);
    }
    void remove(int key)
    {
        int x,y,z;
        splitv(root,key,x,z);
        splitv(x,key-1,x,y);
        if(y)y=merge(l(y),r(y));
        root=merge(merge(x,y),z);
    }
    int v2r(int key)
    {
        int x,y,ans;
        splitv(root,key-1,x,y);
        ans=s(x)+1;
        root=merge(x,y);
        return ans;
    }
    int r2v(int key)
    {
        int x,y,ans,now;
        splits(root,key,x,y);
        now=x;
        while(r(now))now=r(now);
        ans=v(now);
        root=merge(x,y);
        return ans;
    }
    int pre(int key)
    {
        int x,y,now,ans;
        splitv(root,key-1,x,y);
        now=x;
        while(r(now))now=r(now);
        ans=v(now);
        root=merge(x,y);
        return ans;
    }
    int nxt(int key)
    {
        int x,y,now,ans;
        splitv(root,key,x,y);
        now=y;
        while(l(now))now=l(now);
        ans=v(now);
        root=merge(x,y);
        return ans;
    }
}T1;
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)T1.insert(x);
        else if(op==2)T1.remove(x);
        else if(op==3)printf("%d\n",T1.v2r(x));
        else if(op==4)printf("%d\n",T1.r2v(x));
        else if(op==5)printf("%d\n",T1.pre(x));
        else printf("%d\n",T1.nxt(x));
    }
}

文艺平衡树

根据 FHQ 的特性，FHQ 是可以维护区间操作的，我们只需要将通篇使用 splits 即可。

Code

#include<iostream>
using namespace std;
struct FHQ
{
    int cnt,root;
    struct sss
    {
        int r,l,s,w,v,tag;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define s(x) tree[x].s
        #define w(x) tree[x].w
        #define v(x) tree[x].v
        #define tag(x) tree[x].tag
    }tree[100005];
    void build(){cnt=0;}
    int New(int x)
    {
        w(++cnt)=rand();
        v(cnt)=x;
        s(cnt)=1;
        return cnt;
    }
    void pushup(int x){s(x)=s(l(x))+s(r(x))+1;}
    void pushdown(int x)
    {
        if(tag(x))
        {
            swap(l(x),r(x));
            tag(l(x))^=1;
            tag(r(x))^=1;
            tag(x)=0;
        }
    }
    void splits(int root,int s,int &x,int &y)
    {
        pushdown(root);
        if(!root)x=y=0;
        else if(s(l(root))<s)
        {
            x=root;
            splits(r(root),s-s(l(root))-1,r(x),y);
            pushup(root);
        }
        else
        {
            y=root;
            splits(l(root),s,x,l(y));
            pushup(root);
        }
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x^y;
        else if(w(x)>w(y))
        {
            pushdown(x);
            r(x)=merge(r(x),y);
            pushup(x);
            return x;
        }
        else
        {
            pushdown(y);
            l(y)=merge(x,l(y));
            pushup(y);
            return y;
        } 
    }
    void insert(int key)
    {
        int x,y;
        splits(root,key-1,x,y);
        root=merge(merge(x,New(key)),y);
    }
    void remove(int key)
    {
        int x,y,z;
        splits(root,key,x,z);
        splits(x,key-1,x,y);
        if(y)y=merge(l(y),r(y));
        root=merge(merge(x,y),z);
    }
    void reverse(int l,int r)
    {
        int x,y,p;
        splits(root,r,x,y);
        splits(x,l-1,x,p);
        tag(p)^=1;
        root=merge(merge(x,p),y);
    }
    void print(int x)
    {
        pushdown(x);
        if(l(x))print(l(x));
        printf("%d ",v(x));
        if(r(x))print(r(x));
    }
}T1;
int T,n;
int main()
{
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)T1.root=T1.merge(T1.root,T1.New(i));
    while(T--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        T1.reverse(l,r);
    }
    T1.print(T1.root);
}

二逼平衡树

用于在带修情况下在区间中查询第 $k$ 大等信息。

考虑线段树套平衡树，外层为值域，内层为下标。

删除和插入直接在线段树跑，在线段树中的平衡树中插入/删除下标即可。

前缀和后继可以通过查询第 $k$ 大和查询排名实现。

排名直接在线段树上面跑有多少在 $[l,r]$ 的树小于 $key$。

第 $k$ 大在线段树上二分即可。

Code

#include<iostream>
using namespace std;
int cnt;
struct sss
{
    int r,l,s,w,v;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define s(x) tree[x].s
    #define w(x) tree[x].w
    #define v(x) tree[x].v
}tree[6000005];
struct FHQ
{
    int root;
    int New(int x)
    {
        w(++cnt)=rand();
        v(cnt)=x;
        s(cnt)=1;
        return cnt;
    }
    void pushup(int x){s(x)=s(l(x))+s(r(x))+1;}
    void splitv(int root,int key,int &x,int &y)
    {
        if(!root)x=y=0;
        else if(v(root)<=key)
        {
            x=root;
            splitv(r(root),key,r(x),y);
            pushup(root);
        }
        else
        {
            y=root;
            splitv(l(root),key,x,l(y));
            pushup(root);
        }
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x^y;
        else if(w(x)>w(y))
        {
            r(x)=merge(r(x),y);
            pushup(x);
            return x;
        }
        else
        {
            l(y)=merge(x,l(y));
            pushup(y);
            return y;
        } 
    }
    void insert(int key)
    {
        int x,y;
        splitv(root,key-1,x,y);
        root=merge(merge(x,New(key)),y);
    }
    void remove(int key)
    {
        int x,y,z;
        splitv(root,key,x,z);
        splitv(x,key-1,x,y);
        if(y)y=merge(l(y),r(y));
        root=merge(merge(x,y),z);
    }
    int v2r(int key)
    {
        int x,y,ans;
        splitv(root,key-1,x,y);
        ans=s(x)+1;
        root=merge(x,y);
        return ans;
    }
    int nxt(int key)
    {
        int x,y,now,ans;
        splitv(root,key,x,y);
        now=y;
        while(l(now))now=l(now);
        ans=v(now);
        root=merge(x,y);
        return ans;
    }
}T[6000005];
struct Segment_Tree
{
    struct sss
    {
        int l,r,sum;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define sum(x) tree[x].sum
    }tree[5000005];
    int root,cnt,N=1e9,a[5000005];
    int build()
    {
        cnt++;
        return cnt;
    }
    void change(int x,int l,int r,int p,int o)
    {
        if(l==r)
        {
            if(!T[x].root)
            {
                T[x].insert(-2147483647);
                T[x].insert(2147483647);
            }
            if(o<0)T[x].remove(-o),sum(x)--;
            else T[x].insert(o),sum(x)++;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid)
        {
            if(!l(x))l(x)=build();
            change(l(x),l,mid,p,o);
        }
        else 
        {
            if(!r(x))r(x)=build();
            change(r(x),mid+1,r,p,o);
        }
        if(!T[x].root)
        {
            T[x].insert(-2147483647);
            T[x].insert(2147483647);
        }
        if(o<0)T[x].remove(-o);
        else T[x].insert(o);
        sum(x)=sum(l(x))+sum(r(x));
    }
    int ask_sum(int x,int l,int r,int l1,int r1,int l2,int r2)
    {
        if(l2<=l&&r<=r2)
        {
            int sum=0;
            sum-=T[x].v2r(l1);
            sum+=T[x].v2r(T[x].nxt(r1));
            return sum;
        }
        int mid=(l+r)>>1,sum=0;
        if(l2<=mid)
        {
            if(!l(x))l(x)=build();
            sum+=ask_sum(l(x),l,mid,l1,r1,l2,r2);
        }
        if(mid<r2)
        {
            if(!r(x))r(x)=build();
            sum+=ask_sum(r(x),mid+1,r,l1,r1,l2,r2);
        }
        return sum;
    }
    int ask_rank(int l1,int r1,int p)
    {
        return ask_sum(root,1,N,l1,r1,1,p-1)+1;
    }
    int ask_val(int x,int l,int r,int l1,int r1,int p)
    {
        if(l==r)return sum(x)?l:-1;
        int sum=0;
        sum-=T[l(x)].v2r(l1);
        sum+=T[l(x)].v2r(T[l(x)].nxt(r1));
        int mid=(l+r)>>1;
        if(p<=sum)
        {
            if(!l(x))l(x)=build();
            return ask_val(l(x),l,mid,l1,r1,p);
        }
        else
        {
            if(!r(x))r(x)=build();
            return ask_val(r(x),mid+1,r,l1,r1,p-sum);
        }
    }
    void update(int pos,int v)
    {
        change(root,1,N,a[pos],-pos);
        a[pos]=v;
        change(root,1,N,a[pos],pos);
    }
    int pre(int l,int r,int p)
    {
        if(p==1)return -2147483646;
        int rnk=ask_rank(l,r,p)-1;
        if(!rnk)return -2147483646;
        int ans=ask_val(root,1,N,l,r,rnk);
        return ans==-1?-2147483646:ans;
    }
    int nxt(int l,int r,int p)
    {
        int rnk=ask_rank(l,r,p+1);
        int ans=ask_val(root,1,N,l,r,rnk);
        return ans==-1?2147483648:ans;
    }
}T1;
int Q,n;
int main()
{
    scanf("%d%d",&n,&Q);
    T1.root=T1.build();
    for(int i=1;i<=n;i++)
    {
        int q;
        scanf("%d",&q);
        q++;
        T1.change(T1.root,1,T1.N,q,i);
        T1.a[i]=q;
    }
    while(Q--)
    {
        int op,l,r,x,pos;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",T1.ask_rank(l,r,x+1));
        }
        else if(op==2)
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",T1.ask_val(T1.root,1,T1.N,l,r,x)-1);
        }
        else if(op==3)
        {
            scanf("%d%d",&pos,&x);
            T1.update(pos,x+1);
        }
        else if(op==4)
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",T1.pre(l,r,x+1)-1);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",T1.nxt(l,r,x+1)-1);
        }
    }
}

CDQ

处理三维偏序的时候用，可以类比一下归并排序求逆序对，就是多了一个树状数组处理多出来的一维偏序。

记得树状数组清零的时候用撤销操作，否则时间复杂度直接跑到 $n^2\log^2{n}$。

Code P3810 【模板】三维偏序（陌上花开）

#include<algorithm>
#include<iostream>
#define lowbit(x) (x&-x)
using namespace std;
struct sss
{
    int a,s,d,cnt,ans;
}a[1000005],s[1000005];
int n,k,d[1000005],c[1000005],m;
inline int ask(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))ans+=c[x];
    return ans;
}
inline void add(int x,int y)
{
    for(;x<=k;x+=lowbit(x))c[x]+=y;
}
bool cmp1(sss a,sss s){return a.a!=s.a?a.a<s.a:a.s!=s.s?a.s<s.s:a.d<s.d;}
bool cmp2(sss a,sss s){return a.s!=s.s?a.s<s.s:a.d<s.d;}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(s+l,s+mid+1,cmp2);
    sort(s+mid+1,s+r+1,cmp2);
    int j=l;
    for(int i=mid+1;i<=r;i++)
    {
        while(s[j].s<=s[i].s&&j<=mid)
        {
            add(s[j].d,s[j].cnt);
            j++;
        }
        s[i].ans+=ask(s[i].d);
    }
    for(int i=l;i<j;i++)add(s[i].d,-s[i].cnt);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].a,&a[i].s,&a[i].d);
    sort(a+1,a+n+1,cmp1);
    int num=0;
    for(int i=1;i<=n;i++)
    {
        num++;
        if(a[i].a!=a[i+1].a||a[i].s!=a[i+1].s||a[i].d!=a[i+1].d)
        {
            s[++m].a=a[i].a;
            s[m].s=a[i].s;
            s[m].d=a[i].d;
            s[m].cnt=num;
            num=0;
        }
    }
    cdq(1,m);
    for(int i=1;i<=m;i++)d[s[i].ans+s[i].cnt-1]+=s[i].cnt;
    for(int i=0;i<n;i++)printf("%d\n",d[i]);
}

后记

写的有点潦草，有空再补。