树状数组与线段树、平衡树

【树状数组】CF2129B

【题目大意】给定大小为\(n\)的排列\(P=\left \{ p_1,p_2,\cdots,p_n \right \}\)，对排列\(A=\left \{ a_1,a_2,\cdots,a_n\right \}\)，\(a_i\)可取\(p_i\)或\(2n-p_i\)，求\(A\)的一个合理构造，使\(A\)中逆序对数量最少。

【树状数组】P1774 

【题目大意】对序列$A=\left { a_1,a_2,\cdots,a_n\right } $，记交换相邻元素为一次操作，求使该序列变为不下降子序列的最小操作数。

树状数组的单点修改，单点查询，区间修改，区间查询。

树状数组对于”单点修改，区间查询“与”区间修改、单点查询“非常方便。

【单点修改，区间查询】LuoguP3374 树状数组1 参考解答

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q;
long long t[N];
void add(int x,int k)
{
    while(x<=n) t[x]+=k,x+=x&(-x);
}
long long query(int x)
{
    long long ans=0;
    while(x) ans+=t[x],x-=x&(-x);
    return ans;
}
int main()
{
    cin>>n>>q;
    int op,x,y;
    for(int i=1;i<=n;i++)
        cin>>x,add(i,x);
    for(int i=1;i<=q;i++)
    {
        cin>>op>>x>>y;
        if(op==1) add(x,y);
        else cout<<query(y)-query(x-1)<<endl;
    }
    return 0;
}

【区间修改，单点查询】LuoguP3368 树状数组2 参考解答

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,a[N],t[N],q;
void add(int x,long long k)
{
    while(x<=n) t[x]+=k,x+=x&(-x);
}
long long query(int x)
{
    long long res=0;
    while(x) res+=t[x],x-=x&(-x);
    return res;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,a[i]-a[i-1]);
    for(int i=1;i<=q;i++)
    {
        int op,l,r,x;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&l,&r,&x);
            add(l,x),add(r+1,-x);
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}

【树状数组】【排序】LuoguP10814 离线二维数点

【题目大意】给定长度为\(N\)的序列，有\(q\)个询问，每次询问给定\(L,R,x\)，求区间\([L,R]\)中小于等于\(x\)的元素个数。

实现1：

LuoguP10814 离线二维数点 参考实现1

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int ans[N],n,q,a[N],t[N];
struct node{int l,r,x,num;}b[N],c[N];
bool cmp1(node x,node y){if(x.l!=y.l) return x.l<y.l;}
bool cmp2(node x,node y){if(x.r!=y.r) return x.r<y.r;}
void add(int x,int k)
{while(x<=n) t[x]+=k,x+=x&(-x);}
int query(int x)
{
    int res=0;
    while(x) res+=t[x],x-=x&(-x);
    return res;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=q;i++) 
        scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x),b[i].num=i;
    for(int i=1;i<=q;i++) c[i]=b[i];
    sort(b+1,b+q+1,cmp1);
    sort(c+1,c+q+1,cmp2);
    int tot1=1,tot2=1;
    for(int i=1;i<=n;i++)
    {
        while(b[tot1].l==i) 
            ans[b[tot1].num]-=query(b[tot1].x),tot1++;
        add(a[i],1);
        while(c[tot2].r==i) 
            ans[c[tot2].num]+=query(c[tot2].x),tot2++;
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}

【树状数组】LuoguP6225 异或橙子 

【题目大意】给定长度为\(N\)的序列\(A\)，要求支持以下操作：（1）修改\(a_i\)为\(x\)（2）求区间\([L,R]\)的权值\(W_{[L,R]}\)，权值\(W_{[L,R]}\)定义为

\[W_{[L,R]}=\bigoplus\limits_{L\le i<j\le R}\bigoplus\limits_{i\le k\le j}a_k\]

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,x,op,y;
struct tree
{
    int t[4*N];
    void add(int x,int k)
    {while(x<=n) t[x]^=k,x+=x&(-x);}
    int query(int x)
    {
        int res=0;
        while(x) res^=t[x],x-=x&(-x);
        return res;
    }
}t1,t2;
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i%2==1) t1.add(i/2+1,x);
        else t2.add(i/2,x);
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            if(x%2==1) 
            {
                int posi=x/2+1;
                t1.add(posi,y^(t1.query(posi)^t1.query(posi-1)));
            }
            else
            {
                int posi=x/2;
                t2.add(posi,y^(t2.query(posi)^t2.query(posi-1)));
            }
        }
        else
        {
            if((y-x+1)%2==0) printf("0\n");
            else
            {
                if(x%2==1)
                {
                    int posi1=x/2+1,posi2=y/2+1;
                    printf("%d\n",t1.query(posi2)^t1.query(posi1-1));
                } 
                else
                {
                    int posi1=x/2,posi2=y/2;
                    printf("%d\n",t2.query(posi2)^t2.query(posi1-1));
                }
            }
        }
    }
    return 0;
}

【树状数组】【容斥原理】LuoguP3801 红色的幻想乡 

【题目大意】在\(n\cdot m\)的方格阵中，某方格可以填入1，0两种数，初始全为0。要求支持以下操作：（1）选定\(x,y\)，反转属于\(第x行\)与\(第y列\)的全体方格，（2）查询\(左上角为(x_1,y_1)，右下角为(x_2,y_2)\)的区域内填数为1的方格数。

关键在于维护被置为1的总行数与总列数，使用两个树状数组分别维护总行数与总列数，修改时若同一行/列被填数两次，则变为0。计数时，设\(p=query(x_2)-query(x_1-1),q=query(y_2)-query(y_1--1)\)，结果为\((y_2-y_1+1)p+(x_2-x_1+1)q-2pq\)

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int l[N],c[N],n,m,q;
struct tree
{
    int t[N],limit;
    void add(int x,int k)
    {while(x<=limit) t[x]+=k,x+=x&(-x);}
    int query(int x)
    {
        int res=0;
        while(x) res+=t[x],x-=x&(-x);
        return res;
    }
}t1,t2;
int main()
{
    cin>>n>>m>>q;
    t1.limit=n,t2.limit=m;
    for(int i=1;i<=q;i++)
    {
        int op,xs,xe,ys,ye;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&xs,&ys);
            if(l[xs]) t1.add(xs,-1),l[xs]=0;
            else t1.add(xs,1),l[xs]=1;
            if(c[ys]) t2.add(ys,-1),c[ys]=0;
            else t2.add(ys,1),c[ys]=1;
        }
        else
        {
            scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
            long long p=t1.query(xe)-t1.query(xs-1);
            long long q=t2.query(ye)-t2.query(ys-1);
            printf("%lld\n",(ye-ys+1)*p+(xe-xs+1)*q-2*p*q);
        }
    }
    return 0;
}

【树状数组】【二维偏序】LuoguP2717 寒假作业 

【题目大意】给定长度为\(N\)的序列，对区间\([L,R]\)，若区间内的数的平均值\(\overline{X}\ge k\)，则此区间被视为合法区间，求合法区间总数。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long ans,t[N*4];
int n,k,a[N],h[N];
void add(int x,long long k)
{while(x<=n) t[x]+=k,x+=x&(-x);}
long long query(int x)
{
    long long res=0;
    while(x) res+=t[x],x-=x&(-x);
    return res;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]),a[i]-=k;
    for(int i=1;i<=n;i++) a[i]+=a[i-1],h[i]=a[i];
    sort(h+1,h+n+2);
    int m=unique(h+1,h+n+2)-h-1;
    for(int i=1;i<=n+1;i++)
        a[i]=lower_bound(h+1,h+m+1,a[i])-h;
    add(a[n+1],1);
    for(int i=1;i<=n;i++)
        ans+=query(a[i]),add(a[i],1);
    cout<<ans;
    return 0;
}

【二维树状数组】LuoguP4054 计数问题 

【题目大意】对\(n*m\)的方格阵，初始数据\(a_{i,j}\)表示\((i,j)\)内填\(a_{i,j}颜色，共\)\(Q\)个操作：（1）将\((i,j)\)颜色变为\(x\)；（2）询问\(左上角为(x_1,y_1),右下角为(x_2,y_2)\)的区域内颜色为\(x\)的方格数。\(1\le n,m\le 300,NUM_{color}\le 100\)

类比一维树状数组，二维树状数组\(query(i,j)\)表示\(左上角为(1,1),右下角为(i,j)\)内全体\(t_{i,j}\)的和。

参考实现

#include<bits/stdc++.h>
using namespace std;
int n,m,q,p[305][305];
struct tree
{
    int t[305][305];
    void add(int x,int y,int k)
    {
        int temp=y;
        while(x<=n)
        {
            y=temp;
            while(y<=m) t[x][y]+=k,y+=y&(-y);
            x+=x&(-x);
        }
    }
    int query(int x,int y)
    {
        int temp=y,res=0;
        while(x)
        {
            y=temp;
            while(y) res+=t[x][y],y-=y&(-y);
            x-=x&(-x);
        }
        return res;
    }
}a[105];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&p[i][j]);
            a[p[i][j]].add(i,j,1);
        }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int xs,ys,xe,ye,x,op;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&xs,&ys,&x);
            a[p[xs][ys]].add(xs,ys,-1);
            p[xs][ys]=x;
            a[p[xs][ys]].add(xs,ys,1); 
        }
        else
        {
            scanf("%d%d%d%d%d",&xs,&xe,&ys,&ye,&x);
            printf("%d\n",a[x].query(xe,ye)-a[x].query(xe,ys-1)
            -a[x].query(xs-1,ye)+a[x].query(xs-1,ys-1));
        }
    }
    return 0;
}

LuoguP3372 线段树1 【题目大意】实现区间加修改与区间和查询。

线段树的数据管理类似于二叉树。其维护的值为它的两棵子树内的所有元素做所选算子的值。

在进行修改、查询时采用了分治的思想，以区间修改、区间查询，算子为加号作为例子：在修改\([L,R]\)（给区间\([L,R]\)中的每个元素加\(k\)）时，设当前结点\(node\)管辖的左右区间为\(L_0,R_0\)，若\(L\le L_0,R\ge R_0\)，则对\(T_{node.sum}\)累加\((R_0-L_0+1)k\)，并对懒标记\(T_{node.lazy}累加k\)

为什么需要懒标记？

每次更新如果将和区间所有有交集的子树根节点全部更新的话，时间开销是巨大的:\(O(n)\)，懒标记是将更新值堆积的一种操作，在需要向儿子结点遍历时在一次性全部将之前为向下释放的更新信息合并释放，减小时间开销。举个例子，如果无懒标记，某次修改的区间包括了某子树\(T\)，更新的时间复杂度是\(O(|T|)\),而添加懒标记会使得时间复杂度降为\(O(1)\)并且保留了子树的更新信息。

LuoguP3372 线段树1 线段树做法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct tree{int l,r;long long sum,add;}t[N*4];
long long a[N];
int n,q;
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].sum=a[l];return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
void spread(int p)
{
    if(t[p].add)
    {
        t[2*p].add+=t[p].add;t[2*p+1].add+=t[p].add;
        t[2*p].sum+=(t[2*p].r-t[2*p].l+1)*t[p].add;
        t[2*p+1].sum+=(t[2*p+1].r-t[2*p+1].l+1)*t[p].add;
        t[p].add=0;
    }
}
void change(int p,int l,int r,long long k)
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].sum+=(t[p].r-t[p].l+1)*k;
        t[p].add+=k;return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(2*p,l,r,k);
    if(r>mid) change(2*p+1,l,r,k);
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
long long query(int p,int l,int r)
{
    long long res=0;
    if(t[p].l>=l&&t[p].r<=r) return t[p].sum;
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) res+=query(2*p,l,r);
    if(r>mid) res+=query(2*p+1,l,r);
    return res;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    int op,l,r;long long k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&l,&r,&k);
            change(1,l,r,k);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
}

LuoguP3372 线段树1 树状数组做法

LuoguP3373 线段树2 【题目大意】实现区间加修改、区间乘修改与区间和查询。

本题需要两个懒标记\(T_{node.add},T_{node.mul}\)，做加法时，只需\(T_{node.add}\)累加\(k\)，但在做乘法时，需要考虑更新三个变量的值\(T_{node.mul}*=k,T_{node.add}*=k\)，在\(spread\)处，\(T_{2*node/2*node+1.add}=T_{2*node/2*node+1.add}*T_{node.mul}+T_{node.add}\)

因乘法同时作用于\(p\)处的\(add\)值，\(2p/2p+1\)的尚未下放的\(add\)值

LuoguP3373 线段树2 参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct tree{int l,r;long long sum,add,mul;}t[N*4];
long long a[N],mod;
int n,q;
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,t[p].mul=1;
    if(l==r){t[p].sum=a[l]%mod;return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void spread(int p)
{
    if(t[p].add||t[p].mul!=1)
    {
        t[2*p].add=t[2*p].add*t[p].mul%mod;
        t[2*p+1].add=t[2*p+1].add*t[p].mul%mod;
        t[2*p].add=(t[2*p].add+t[p].add)%mod;
        t[2*p+1].add=(t[2*p+1].add+t[p].add)%mod;
        t[2*p].mul=t[2*p].mul*t[p].mul%mod;
        t[2*p+1].mul=t[2*p+1].mul*t[p].mul%mod;
        t[2*p].sum=(t[2*p].sum*t[p].mul%mod+(t[2*p].r-t[2*p].l+1)*t[p].add)%mod;
        t[2*p+1].sum=(t[2*p+1].sum*t[p].mul%mod+(t[2*p+1].r-t[2*p+1].l+1)*t[p].add)%mod;
        t[p].add=0,t[p].mul=1;
    }
}
void mul(int p,int l,int r,long long k)
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].sum=t[p].sum*k%mod;
        t[p].mul=t[p].mul*k%mod;
        t[p].add=t[p].add*k%mod;return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) mul(2*p,l,r,k);
    if(r>mid) mul(2*p+1,l,r,k);
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void add(int p,int l,int r,long long k)
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*k)%mod;
        t[p].add=(t[p].add+k)%mod;return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) add(2*p,l,r,k);
    if(r>mid) add(2*p+1,l,r,k);
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
long long query(int p,int l,int r)
{
    long long res=0;
    if(t[p].l>=l&&t[p].r<=r) 
        return t[p].sum%mod;
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) res=(res+query(2*p,l,r))%mod;
    if(r>mid) res=(res+query(2*p+1,l,r))%mod;
    return res;
}
int main()
{
    cin>>n>>q>>mod;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    int op,l,r;long long k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&l,&r,&k);
            mul(1,l,r,k);
        }
        else if(op==2)
        {
            scanf("%d%d%lld",&l,&r,&k);
            add(1,l,r,k);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
}

LuoguP1253 区间完全修改嵌套 【题目大意】实现区间完全修改、区间加与区间和查询。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const long long INF=2e16;
int n,q;long long a[N];
struct node{int l,r;long long change,v,add;}t[4*N];
void pushup(int p)
{
    t[p].v=max(t[2*p].v,t[2*p+1].v);
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,t[p].change=INF;
    if(l==r){t[p].v=a[l];return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    pushup(p);
}
void spread(int p)
{
    if(t[p].add||t[p].change!=INF)
    {
        if(t[p].change!=INF) 
        {
            t[2*p].add=t[2*p+1].add=0;
            t[2*p].v=t[2*p+1].v=t[p].change;
            t[2*p].change=t[2*p+1].change=t[p].change;
            t[p].change=INF;
        }
        else if(t[p].add)
        {
            if(t[2*p].change!=INF) t[2*p].change+=t[p].add;
            else t[2*p].add+=t[p].add;
            if(t[2*p+1].change!=INF) t[2*p+1].change+=t[p].add;
            else t[2*p+1].add+=t[p].add;
            t[2*p].v+=t[p].add;t[2*p+1].v+=t[p].add;
            t[p].add=0;
        }
    }
}
void add(int p,int l,int r,long long k)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].v+=k;
        if(t[p].change!=INF) t[p].change+=k;
        else t[p].add+=k;return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) add(2*p,l,r,k);
    if(r>mid) add(2*p+1,l,r,k);
    pushup(p);
}
void change(int p,int l,int r,long long k)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].v=k;t[p].add=0,t[p].change=k;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(2*p,l,r,k);
    if(r>mid) change(2*p+1,l,r,k);
    pushup(p);
}
long long query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].v;
    spread(p);
    int mid=t[p].l+t[p].r>>1;long long res=-2e16;
    if(l<=mid) res=max(res,query(2*p,l,r));
    if(r>mid) res=max(res,query(2*p+1,l,r));
    return res;
}
int main()
{
    cin>>n>>q;
    int op,l,r;long long x;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&l,&r,&x);
            change(1,l,r,x);
        }
        else if(op==2)
        {
            scanf("%d%d%lld",&l,&r,&x);
            add(1,l,r,x);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
}

【差分】【线段树】LuoguP1438 无聊的数列 

【题目大意】要求支持以下操作：（1）区间\([L,R]\)依次加上首项为\(K\)，公差为\(D\)的等差数列（2）单点查询

构造差分序列即可，区间加采用\(add(L,L,K)\)，\(add(L+1,R,D)\)，\(add(R+1,R+1,-K-D(R-L))\)。但应注意判断\(L+1,R+1\)是否越界。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{int l,r;long long sum,add;}t[8*N];
long long a[N],b[N];
int n,q,op;
void spread(int p)
{
    if(t[p].add)
    {
        t[2*p].add+=t[p].add;
        t[2*p+1].add+=t[p].add;
        t[2*p].sum+=(t[2*p].r-t[2*p].l+1)*t[p].add;
        t[2*p+1].sum+=(t[2*p+1].r-t[2*p+1].l+1)*t[p].add;
        t[p].add=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].sum=b[l];return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    t[p].sum=t[2*p].sum+t[2*p+1].sum; 
}
void add(int p,int l,int r,long long k)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].add+=k;
        t[p].sum+=(t[p].r-t[p].l+1)*k;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) add(2*p,l,r,k);
    if(r>mid) add(2*p+1,l,r,k);
    t[p].sum=t[2*p].sum+t[2*p+1].sum; 
}
long long query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    long long res=0;
    if(l<=mid) res+=query(2*p,l,r);
    if(r>mid) res+=query(2*p+1,l,r);
    return res;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        int l,r,x;long long k,d;
        if(op==1)
        {
            scanf("%d%d%lld%lld",&l,&r,&k,&d);
            add(1,l,l,k);
            if(l+1<=n) add(1,l+1,r,d);
            if(r+1<=n) add(1,r+1,r+1,-k-(r-l)*d);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",query(1,1,x));
        }
    }
    return 0;
}

【线段树】LuoguP3870 开关

【题目大意】\(N\)个灯排成一排，初始均为灭状态，要求支持以下操作：（1）将区间\([L,R]\)的灯状态全部反转，（2）查询区间\([L,R]\)内亮灯个数。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q;
struct node{int l,r,sum,change;}t[4*N];
void pushup(int p)
{
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
}
void spread(int p)
{
    if(t[p].change)
    {
        if(t[p].change&1)
        {
            t[2*p].sum=(t[2*p].r-t[2*p].l+1)-t[2*p].sum;
            t[2*p+1].sum=(t[2*p+1].r-t[2*p+1].l+1)-t[2*p+1].sum;
        }
        t[2*p].change+=t[p].change;
        t[2*p+1].change+=t[p].change;
        t[p].change=0;
    }
}
void change(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].sum=(t[p].r-t[p].l+1)-t[p].sum;
        t[p].change++;return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(2*p,l,r);
    if(r>mid) change(2*p+1,l,r);
    pushup(p);
}
int query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    spread(p);
    int mid=t[p].l+t[p].r>>1,res=0;
    if(l<=mid) res+=query(2*p,l,r);
    if(r>mid) res+=query(2*p+1,l,r);
    return res;
}
int main()
{
    cin>>n>>q;
    int op,l,r;
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==0) change(1,l,r);
        else printf("%d\n",query(1,l,r));
    }
    return 0;
}

【状态压缩】【线段树】LuoguP1558 色板游戏

【题目大意】对于长度为\(N\)的色板，初始全涂满1号颜色，要求支持以下操作，对区间\([L,R]\)涂上颜色\(k(1\le k\le 30)\)（将覆盖掉之前的颜色），查询区间\([L,R]\)的颜色种数。

注意到颜色种数不超过30，可以使用状态压缩，用\(2^{k-1}\)表示第\(k\)种颜色，即对于二进制数\(A_{31}A_{30}\cdots A_2A_1A_0\)，仅\(A_{k-1}\)为为1，修改直接替换，合并做或运算即可，最后统计1的个数。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,color;
struct node{int l,r,change,sum;}t[N*4];
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].sum=1;return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    t[p].sum=t[2*p].sum|t[2*p+1].sum;
}
void spread(int p)
{
    if(t[p].change)
    {
        t[2*p].change=t[2*p].sum=t[p].change;
        t[2*p+1].change=t[2*p+1].sum=t[p].change;
        t[p].change=0;
    }
}
void change(int p,int l,int r,int k)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].sum=k,t[p].change=k;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(2*p,l,r,k);
    if(r>mid) change(2*p+1,l,r,k);
    t[p].sum=t[2*p].sum|t[2*p+1].sum;
}
int query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    spread(p);
    int mid=t[p].l+t[p].r>>1,res=0;
    if(l<=mid) res|=query(2*p,l,r);
    if(r>mid) res|=query(2*p+1,l,r);
    return res;
}
int main()
{
    cin>>n>>color>>q;
    build(1,1,n);
    char op;int l,r,x;
    for(int i=1;i<=q;i++)
    {
        cin>>op;
        if(op=='C')
        {
            scanf("%d%d%d",&l,&r,&x);
            if(l>r) swap(l,r); 
            change(1,l,r,1<<(x-1));
        }
        else 
        {
            scanf("%d%d",&l,&r);
            if(l>r) swap(l,r);
            int x=query(1,l,r),ans=0;
            while(x)
            {
                if(x&1) ans++;
                x>>=1;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

【动态规划】【树状数组】【线段树】LuoguP1637 三元上升子序列 

【题目大意】对序列\(A=\left \{ a_1,a_2,\cdots,a_n\right \}\)，求数对\((i,j,k),i<j<k,a_i<a_j<a_k\)的个数。

树状数组做法1：将数据离散化。考虑每个数中间数\(a_j\)的贡献，即求\(L=\left \{ a_i|a_i<a_j,i\in[1,j-1]\right \}\)，\(R=\left \{ a_k|a_k>a_j,k\in[j+1,n]\right \}\)，贡献为\(|L||R|\)，时间复杂度为\(O(n\log n)\)

动态规划、树状数组优化做法（可拓展至\(M\)元上升子序列计数）记\(dp_{i,j}\)为以\(a_j\)结尾，长度为\(i\)的上升子序列个数。有转移方程：

\[\displaystyle dp_{i,j}=\sum_{k<j,a_k<a_j}dp_{i-1,k}\]

暴力枚举的时间复杂度是\(O(n^2M)\)，可以考虑树状数组优化。将数据离散化后，每次\(i\)循环清空树状数组，\(dp_{i,j}=query(a_j-1)\)，再\(add(a_j,dp_{i-1,j})\)，这样就实现了快速转移，算法时间复杂度为\(O(nM\log n)\)，\(dp\)数组可滚动覆盖，故空间复杂度可降至\(O(n)\)。

树状数组做法2：使用两个树状数组处理：第一个的\(query(i)\)表示\(j<i,a_j<a_i\)的个数，而以\(a_k\)结尾的三元上升子序列个数为\(\displaystyle \sum_{1\le i<k,a_i<a_k}query(i)\)。可考虑在计算完\(query(i)\)后对第二个树状数组执行\(add(a_i,query(i))\)。算法时间复杂度为\(O(n\log n)\)，此方法或许也可扩展至\(M\)元上升子序列，树状数组置为\(tr_{i,j}\)或滚动覆盖。

LuoguP1637 三元上升子序列 树状数组做法1参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5; 
int a[N],h[N],t[N],l[N],r[N],n;
long long ans;
void add(int x,int k)
{while(x<=n) t[x]+=k,x+=x&(-x);}
int query(int x)
{
    int res=0;
    while(x) res+=t[x],x-=x&(-x);
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],h[i]=a[i];
    sort(h+1,h+n+1);
    int m=unique(h+1,h+n+1)-h;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(h+1,h+m+1,a[i])-h;
    for(int i=1;i<=n;i++)
    {
        l[i]=query(a[i]-1);
        add(a[i],1);
    }
    memset(t,0,sizeof(t));
    for(int i=n;i>=1;i--)
    {
        r[i]=n-i-query(a[i]);
        add(a[i],1);
    }
    for(int i=1;i<=n;i++) ans+=l[i]*r[i];
    cout<<ans;
    return 0;
}

LuoguP1637 三元上升子序列 动态规划参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long dp[4][N],t[4*N],ans;
int a[N],h[N],n;
void add(int x,long long k)
{while(x<=n) t[x]+=k,x+=x&(-x);}
long long query(int x)
{
    long long res=0;
    while(x) res+=t[x],x-=x&(-x);
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]),h[i]=a[i];
    sort(h+1,h+n+1);
    int m=unique(h+1,h+n+1)-h;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(h+1,h+m+1,a[i])-h;
    for(int i=1;i<=n;i++) dp[1][i]=1;
    for(int i=2;i<=3;i++)
    {
        memset(t,0,sizeof(t));
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=query(a[j]-1);
            add(a[j],dp[i-1][j]);
        }
    }
    for(int i=1;i<=n;i++) ans+=dp[3][i];
    cout<<ans;
    return 0;
}

LuoguP1637 三元上升子序列 树状数组做法2参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long dp[4][N],ans;
int a[N],h[N],n;
struct tree
{
    int t[4*N];
    void add(int x,long long k)
    {while(x<=n) t[x]+=k,x+=x&(-x);}
    long long query(int x)
    {
        long long res=0;
        while(x) res+=t[x],x-=x&(-x);
        return res;
    }
}t1,t2;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]),h[i]=a[i];
    sort(h+1,h+n+1);
    int m=unique(h+1,h+n+1)-h;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(h+1,h+m+1,a[i])-h;
    for(int i=1;i<=n;i++)
    {
        ans+=t2.query(a[i]-1);
        long long temp=t1.query(a[i]-1);
        t1.add(a[i],1),t2.add(a[i],temp);
    }
    cout<<ans;
    return 0;
}

【线段树】LuoguP4145 根号修改

【题目大意】实现以下操作：（1）对区间\([L,R]\)内每个数开根号并向下取整（2）区间求和，注意：初始数\(a_i\in\mathbb{N_+},a_i\le 10^{12}\)

需要注意到\(\sqrt{1}=1,10^{12}连续做6次开根号操作将得到1\),理论上需要做的开根号次数为\(O(n)\)。此时需要维护区间最大值\(maxn\)，若\(T_{p.maxn}=1\)，则跳过此区间的开根号。此算法时间复杂度为\(O(n\log n)\)

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q;
long long a[N];
struct node{int l,r;long long sum,maxn;}t[4*N];
void pushup(int p)
{
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
    t[p].maxn=max(t[2*p].maxn,t[2*p+1].maxn);
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].sum=t[p].maxn=a[l];return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    pushup(p); 
}
void change(int p,int l,int r)
{
    if(t[p].maxn==1) return;
    else if(t[p].l==t[p].r)
    {t[p].sum=sqrt(t[p].sum),t[p].maxn=sqrt(t[p].maxn);return;}
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(2*p,l,r);
    if(r>mid) change(2*p+1,l,r);
    pushup(p);
}
long long query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    int mid=t[p].l+t[p].r>>1;long long res=0;
    if(l<=mid) res+=query(2*p,l,r);
    if(r>mid) res+=query(2*p+1,l,r);
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    cin>>q;
    int op,l,r;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(l>r) swap(l,r);
        if(op==0) change(1,l,r);
        else printf("%lld\n",query(1,l,r));
    }
    return 0;
}

【线段树】LuoguP1471 方差

【题目大意】实现以下操作：（1）区间加（2）区间查询平均值（3）区间查询方差，方差定义为\(\displaystyle S^2=\frac{1}{n}\sum_{i=1}^{n}(X_i-\overline{X})^2\)

只需实现区间和与区间平方和的维护即可。在做区间加\(k\)操作时，有\(T_{p.square}=T_{p,square}+2kT_{p.sum}+(T_{p.r}-T_{p.l}+1)*k^2\)

修改\(lazy\)标记时同理。应当注意：区间平方和的修改依赖区间和，应当先更新区间平方和再更新区间和。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q;double a[N];
struct node{int l,r;double sum,square,add;}t[4*N];
void pushup(int p)
{
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
    t[p].square=t[2*p].square+t[2*p+1].square;
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].sum=a[l],t[p].square=a[l]*a[l];return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    pushup(p);
}
void spread(int p)
{
    if(t[p].add!=0)
    {
        int len1=t[2*p].r-t[2*p].l+1;
        int len2=t[2*p+1].r-t[2*p+1].l+1;
        t[2*p].add+=t[p].add;
        t[2*p+1].add+=t[p].add;
        t[2*p].square+=2*t[p].add*t[2*p].sum+len1*t[p].add*t[p].add;
        t[2*p+1].square+=2*t[p].add*t[2*p+1].sum+len2*t[p].add*t[p].add;
        t[2*p].sum+=len1*t[p].add;
        t[2*p+1].sum+=len2*t[p].add;
        t[p].add=0;
    }
}
void add(int p,int l,int r,double k)
{
    if(l<=t[p].l&&r>=t[p].r)
    {
        t[p].square+=2*k*t[p].sum+(t[p].r-t[p].l+1)*k*k;
        t[p].sum+=(t[p].r-t[p].l+1)*k;
        t[p].add+=k;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) add(2*p,l,r,k);
    if(r>mid) add(2*p+1,l,r,k);
    pushup(p);
}
double querysum(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
    spread(p);
    int mid=t[p].l+t[p].r>>1;double res=0;
    if(l<=mid) res+=querysum(2*p,l,r);
    if(r>mid) res+=querysum(2*p+1,l,r);
    return res;
}
double querysquare(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].square;
    spread(p);
    int mid=t[p].l+t[p].r>>1;double res=0;
    if(l<=mid) res+=querysquare(2*p,l,r);
    if(r>mid) res+=querysquare(2*p+1,l,r);
    return res;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    build(1,1,n);
    int l,r,op;double k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1) 
        {
            scanf("%d%d%lf",&l,&r,&k);
            add(1,l,r,k);
        }
        else if(op==2)
        {
            scanf("%d%d",&l,&r);
            printf("%.4lf\n",querysum(1,l,r)/(r-l+1));
        }
        else
        {
            scanf("%d%d",&l,&r);
            double p=querysquare(1,l,r);
            double q=querysum(1,l,r);
            q=q*q/(r-l+1);
            printf("%.4lf\n",(p-q)/(r-l+1));
        }
    }
    return 0;
}

【线段树】LuoguP4513 小白逛公园

【题目大意】

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,q,a[N];
struct tree{int l,r,maxn,lmax,rmax,sum;}t[4*N];
void pushup(int p)
{
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
    t[p].lmax=max(t[2*p].lmax,t[2*p].sum+t[2*p+1].lmax);
    t[p].rmax=max(t[2*p+1].rmax,t[2*p+1].sum+t[2*p].rmax);
    t[p].maxn=max(max(t[2*p].maxn,t[2*p+1].maxn),t[2*p].rmax+t[2*p+1].lmax);
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].maxn=t[p].lmax=t[p].rmax=t[p].sum=a[l];return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
    pushup(p);
}
void change(int p,int x,int k)
{
    if(t[p].l==t[p].r)
    {t[p].sum=t[p].lmax=t[p].rmax=t[p].maxn=k;return;}
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(2*p,x,k);
    else change(2*p+1,x,k);
    pushup(p);
}
tree query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p];
    int mid=t[p].l+t[p].r>>1;
    if(r<=mid) return query(2*p,l,r);
    else if(l>mid) return query(2*p+1,l,r);
    else
    {
        tree x=query(2*p,l,r),y=query(2*p+1,l,r);
        tree temp;
        temp.lmax=max(x.lmax,x.sum+y.lmax);
        temp.rmax=max(y.rmax,y.sum+x.rmax);
        temp.maxn=max(max(x.maxn,y.maxn),x.rmax+y.lmax);
        return temp;
    }
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    int op,x,y;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            if(x>y) swap(x,y);
            printf("%d\n",query(1,x,y).maxn);
        }
        else change(1,x,y);
    }
    return 0;
}

【线段树】【Set/平衡树】【剪枝】CF19D Points

【题目大意】对于坐标系\(xOy\)，要求支持以下操作：（1）添加一个点\((x,y)\)，保证添加前未出现此点；（2）删除一个点\((x,y)\)，保证删除前存在此点；（3）查询所有横坐标大于\(x\)，纵坐标大于\(y\)的点，找出其中横坐标最小的点，若满足条件的点有多个，取纵坐标最小的点，否则报错。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct tree{int l,r,maxn;}t[4*N];
set<int> s[N];
int opt[N],x[N],y[N],h[N],n;
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r){return;}
    int mid=l+r>>1;
    build(2*p,l,mid),build(2*p+1,mid+1,r);
}
void change(int p,int x,int k)
{
    if(t[p].l==t[p].r){t[p].maxn=k;return;}
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(2*p,x,k);
    else change(2*p+1,x,k);
    t[p].maxn=max(t[2*p].maxn,t[2*p+1].maxn); 
}
int query(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) return t[p].maxn;
    int res=0,mid=t[p].l+t[p].r>>1;
    if(l<=mid) res=max(res,query(2*p,l,r));
    if(r>mid) res=max(res,query(2*p+1,l,r));
    return res;
}
int find(int p,int limit,int x)
{
    if(t[p].r<limit||t[p].maxn<=x) return -1;
    if(t[p].l==t[p].r) return t[p].l;
    int res=find(2*p,limit,x);
    if(res!=-1) return res;
    else return find(2*p+1,limit,x);
} 
int main()
{
    cin>>n;
    string op;int p,q;
    for(int i=1;i<=n;i++)
    {
        cin>>op>>p>>q;
        if(op=="add") opt[i]=1;
        else if(op=="remove") opt[i]=2;
        else opt[i]=3;
        x[i]=p,y[i]=q,h[i]=x[i];
    }
    sort(h+1,h+n+1);
    int m=unique(h+1,h+n+1)-h-1;
    build(1,1,m);
    for(int i=1;i<=n;i++)
        x[i]=lower_bound(h+1,h+m+1,x[i])-h;
    for(int i=1;i<=n;i++)
    {
        if(opt[i]==1)
        {
            s[x[i]].insert(y[i]);
            if(query(1,x[i],x[i])<y[i])
                change(1,x[i],y[i]);
        }
        else if(opt[i]==2)
        {
            int temp=y[i];
            s[x[i]].erase(s[x[i]].find(y[i]));
            if(query(1,x[i],x[i])==temp)
            {
                if(s[x[i]].empty()) change(1,x[i],0);
                else
                {
                    auto it=s[x[i]].end();it--;
                    change(1,x[i],*it);
                }
            }   
        }
        else
        {
            int L=x[i],R=m;
            if(query(1,x[i]+1,m)<=y[i])
            {printf("-1\n");continue;}
            int temp=find(1,x[i]+1,y[i]);
            auto ans=s[temp].upper_bound(y[i]);
            printf("%d %d\n",h[temp],*ans);
        }
    }
    return 0;
}

【平衡树】LuoguP6136 普通平衡树（数据加强版）

【题目大意】实现一种数据结构来维护可重集合\(M\)，需要提供以下操作：

（1）向\(M\)中插入数\(x\)

（2）从\(M\)中删除一个数\(x\)（若有多个相同的数，应只删除一个）

（3）查询M中有多少个数比\(x\)小，并将得到的答案加1（\(x\)可能不存在于\(M\)中）

（4）查询如果将\(M\)从小到大排列后，排名位于第\(x\)位的数

（5）求\(M\)中\(x\)的前驱（\(x\)可能不存在于\(M\)中）

（6）求\(M\)中\(x\)的后继（\(x\)可能不存在于\(M\)中）

Splay树写法

Splay（伸展树）是一种平衡二叉树，通过不断将某个结点旋转到根节点，使整棵树仍然满足BST的性质且保持平衡，由Daniel Sleator和Robert Tarjan发明。

Splay使得每次操作的均摊复杂度为\(O(\log n)\)

均摊时间复杂度\(O(\log n)\)的证明

每个节点\(node\)的信息包括：\(s_0,s_1\)分别指示左右儿子，\(p\)指示祖先。\(cnt\)指示当前结点权值出现次数。

左旋，右旋的统一写法和pushup

void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[y].s[k]=tr[x].s[k^1];
    tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y;
    tr[y].p=x;
    tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    pushup(y),pushup(x);
}

设链\(z\to y\to x\)要进行左旋或右旋，则\(x\)为\(y\)的左儿子还是右儿子决定了左旋还是右旋。

pushup用于更新子树总结点个数。

void pushup(int x)
{
     tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}

Splay实现

伸展（Splay）：访问一个结点\(x\)，并把\(x\)旋转到根节点。

将\(x\)转到\(k\)的下方，若\(k=0\)，则将\(x\)转到\(root\)

void splay(int x,int k)
{
    while(tr[x].p!=k)
    {
        int y=tr[x].p,z=tr[y].p;
        if(z!=k)
            (tr[y].s[0]==x)^(tr[z].s[0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(k==0) root=x;
}

find查找的实现

找到\(v\)所在结点，并把该节点转到根。

void find(int v)
{
    int x=root;
    while(tr[x].s[v>tr[x].v]&&v!=tr[x].v)
        x=tr[x].s[v>tr[x].v];
    splay(x,0);
}

getpre查找前驱、getsuc查找后继的实现

int get_pre(int v)
{
    find(v);
    int x=root;//此时权值为v/接近v的结点已经被转到根节点
    if(tr[x].v<v) return x;
    x=tr[x].s[0];
    while(tr[x].s[1]) x=tr[x].s[1];
    splay(x,0);return x;
}
int get_suc(int v)
{   
    find(v);
    int x=root;
    if(tr[x].v>v) return x;
    x=tr[x].s[1];
    while(tr[x].s[0]) x=tr[x].s[0];
    splay(x,0);return x;
}

del删除结点，insert插入节点

void del(int v)
{
    int pre=get_pre(v),suc=get_suc(v);
    splay(pre,0);splay(suc,pre);
    int del=tr[suc].s[0];
    if(tr[del].cnt>1) tr[del].cnt--,splay(del,0);
    else tr[suc].s[0]=0,splay(suc,0);
}
void insert(int v)
{
    int x=root,p=0;
    while(x&&tr[x].v!=v)
        p=x,x=tr[x].s[v>tr[x].v];
    if(x) tr[x].cnt++;
    else
    {
        x=++idx;
        tr[p].s[v>tr[p].v]=x;
        tr[x].init(p,v);
    }
    splay(x,0);
}

getrank查询排名，getval根据排名查询数值

int get_rank(int v)
{
    insert(v);
    int res=tr[tr[root].s[0]].size;
    del(v);return res;
}
int get_val(int p)
{
    int x=root;
    while(1)
    {
        int y=tr[x].s[0];
        if(tr[y].size+tr[x].cnt<p)
        {
            p-=tr[y].size+tr[x].cnt;
            x=tr[x].s[1];
        }
        else
        {
            if(tr[y].size>=p) x=tr[x].s[0];
            else break;
        }
    }
    splay(x,0);
    return tr[x].v;
}

Splay参考代码，以LuoguP6136 普通平衡树（数据加强版）为例

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,INF=2147483647;
int q,root,idx,n;
struct node
{int s[2],p,v,cnt,size;
void init(int p1,int v1)
{p=p1,v=v1,cnt=size=1;}}tr[N*4];
void pushup(int x)
{
    tr[x].size=tr[tr[x].s[0]].size+
    tr[tr[x].s[1]].size+tr[x].cnt;
}
void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[y].s[k]=tr[x].s[k^1];
    tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y;
    tr[y].p=x;
    tr[x].p=z;
    tr[z].s[tr[z].s[1]==y]=x;
    pushup(y),pushup(x);
}
void splay(int x,int k)
{
    while(tr[x].p!=k)
    {
        int y=tr[x].p,z=tr[y].p;
        if(z!=k)
            (tr[z].s[0]==y)^(tr[y].s[0]==x)?
            rotate(x):rotate(y);
        rotate(x);
    }
    if(k==0) root=x;
}
void find(int v)
{
    int x=root;
    while(tr[x].s[v>tr[x].v]&&tr[x].v!=v)
        x=tr[x].s[v>tr[x].v];
    splay(x,0);
}
int get_pre(int v)
{
    find(v);int x=root;
    if(tr[x].v<v) return x;
    x=tr[x].s[0];
    while(tr[x].s[1]) x=tr[x].s[1];
    splay(x,0);return x;
}
int get_suc(int v)
{
    find(v);int x=root;
    if(tr[x].v>v) return x;
    x=tr[x].s[1];
    while(tr[x].s[0]) x=tr[x].s[0];
    splay(x,0);return x;
}
void insert(int v)
{
    int x=root,p=0;
    while(x&&tr[x].v!=v)
        p=x,x=tr[x].s[v>tr[x].v];
    if(x) tr[x].cnt++;
    else
    {
        x=++idx;
        tr[p].s[v>tr[p].v]=x;
        tr[x].init(p,v);
    }
    splay(x,0);
}
void del(int v)
{
    int pre=get_pre(v),suc=get_suc(v);
    splay(pre,0);splay(suc,pre);
    int del=tr[suc].s[0];
    if(tr[del].cnt>1) tr[del].cnt--,splay(del,0);
    else tr[suc].s[0]=0,splay(suc,0);
}
int get_rank(int v)
{
    insert(v);
    int res=tr[tr[root].s[0]].size;
    del(v);return res;
}
int get_val(int p)
{
    int x=root;
    while(1)
    {
        int y=tr[x].s[0];
        if(tr[y].size+tr[x].cnt<p)
        {
            p-=tr[y].size+tr[x].cnt;
            x=tr[x].s[1];
        }
        else
        {
            if(tr[y].size>=p) x=tr[x].s[0];
            else break;
        }
    }
    splay(x,0);
    return tr[x].v;
}
int main()
{
    insert(-INF),insert(INF);
    cin>>n>>q;int op,x,last=0,ans=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&x),insert(x);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==1) insert(x^last);
        else if(op==2) del(x^last);
        else
        {
            if(op==3) last=get_rank(x^last);
            else if(op==4) last=get_val((x^last)+1);
            else if(op==5) last=tr[get_pre(x^last)].v;
            else last=tr[get_suc(x^last)].v;
            ans^=last; 
        }
    }
    cout<<ans;
}

Treap写法

单次操作的期望时间复杂度优化为\(O(\log n)\)

随机优先级使得Treap的形状等价于“随机二叉搜索树”，后者的期望高度为\(O(\log n)\)

同时满足BST和heap性质的树是唯一的，heap确定了BST的插入顺序。

相关证明

按键值大小排序为\(1,2,\cdots,n\)，第\(i\)个键的深度为\(depth_i\)，对每个\(j\neq i\)定义指示变量\(A_j=1\)当且仅当\(j\)是\(i\)的祖先。则\(\displaystyle D_i=\sum_\limits{j\neq i}A_j\)，故\(\displaystyle ED_i=\sum_\limits{j\neq i}A_j\)

对任意区间\([a,b],i\in [a,b]\)，区间内优先级最高的结点会成为这个区间对应子树的根，对于\(j<i\)，结点\(j\)成为\(i\)的祖先当且仅当区间\([j,i]\)中\(j\)的键值最大，概率为\(\displaystyle \frac{1}{j-i+1}\)

故\(\displaystyle ED_i=\sum_\limits{j\neq i}A_j=\sum_{k=1}^{i-1}\frac{1}{k-i+1}+\sum_{k=i+1}^{n}\frac{1}{k-i+1}=H_{i}+H_{n-i+1}-2\)，其中\(H_m\)是第\(m\)个调和数，\(\displaystyle H_m=\sum_{t=1}^{m}\frac{1}{t}=\ln m+\gamma\)

故\(ED_i=O(\log n)\)对任意\(i\)成立，树高度的期望为\(O(\log n)\)

Treap参考代码，以LuoguP6136 普通平衡树（数据加强版）为例

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,INF=2147483647;
int q,idx,root=0,n;
struct node
{
    int s[2],size,cnt,rd,v;
    void init(int v1)
    {v=v1,cnt=size=1,rd=rand();}
}tr[N*4];
void pushup(int p)
{
    tr[p].size=tr[tr[p].s[0]].size+tr[tr[p].s[1]].size+tr[p].cnt;
}
void rotate(int &p,int d)
{
    int k=tr[p].s[d^1];
    tr[p].s[d^1]=tr[k].s[d];
    tr[k].s[d]=p;
    pushup(p),pushup(k);p=k;
}
void insert(int &p,int x)
{
    if(!p)
    {
        p=++idx,tr[p].init(x);return;
    } 
    if(tr[p].v==x)
    {
        tr[p].cnt++,tr[p].size++;
        return;
    }
    int d=x>tr[p].v;
    insert(tr[p].s[d],x);
    if(tr[p].rd<tr[tr[p].s[d]].rd) rotate(p,d^1);
    pushup(p);
}
void del(int &p,int x)
{
    if(!p) return;
    if(x<tr[p].v) del(tr[p].s[0],x);
    else if(x>tr[p].v) del(tr[p].s[1],x);
    else
    {
        if(!tr[p].s[0]&&!tr[p].s[1])
        {
            tr[p].cnt--,tr[p].size--;
            if(tr[p].cnt==0) p=0;
        }
        else if(tr[p].s[0]&&!tr[p].s[1])
        {
            rotate(p,1);
            del(tr[p].s[1],x);
        }
        else if(!tr[p].s[0]&&tr[p].s[1])
        {
            rotate(p,0);
            del(tr[p].s[0],x);
        }
        else
        {
            int d=tr[tr[p].s[0]].rd>tr[tr[p].s[1]].rd;
            rotate(p,d);
            del(tr[p].s[d],x);
        }
    }
    pushup(p);
}
int getrank(int p,int x)
{
    if(!p) return 1;
    if(tr[p].v==x) return tr[tr[p].s[0]].size+1;
    if(tr[p].v<x) return tr[tr[p].s[0]].size+
    tr[p].cnt+getrank(tr[p].s[1],x);
    if(tr[p].v>x) return getrank(tr[p].s[0],x);
}
int getval(int p,int x)
{
    if(!p) return 0;
    if(tr[tr[p].s[0]].size>=x) return getval(tr[p].s[0],x);
    else if(tr[tr[p].s[0]].size+tr[p].cnt<x) 
        return getval(tr[p].s[1],x-tr[tr[p].s[0]].size-tr[p].cnt);
    else return tr[p].v; 
}
int get_pre(int p,int x)
{
    if(!p) return -INF;
    if(tr[p].v>=x) return get_pre(tr[p].s[0],x);
    else return max(tr[p].v,get_pre(tr[p].s[1],x));
}
int get_suc(int p,int x)
{
    if(!p) return INF;
    if(tr[p].v<=x) return get_suc(tr[p].s[1],x);
    else return min(tr[p].v,get_suc(tr[p].s[0],x));
}
int main()
{
    int op,x,last=0,ans=0;
    cin>>n>>q;
    for(int i=1;i<=n;i++) 
        scanf("%d",&x),insert(root,x);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&op,&x);
        x=x^last;
        if(op==1) insert(root,x);
        if(op==2) del(root,x);
        if(op==3) last=getrank(root,x),ans^=last;
        if(op==4) last=getval(root,x),ans^=last;
        if(op==5) last=get_pre(root,x),ans^=last;
        if(op==6) last=get_suc(root,x),ans^=last;
    }
    cout<<ans;
    return 0;
}