前置芝士
二进制，tire

平衡树

一种数据结构，来维护一些数，需要支持以下操作：
1.插入 xx 数
2.删除 xx 数(若有多个相同的数，因只删除一个)
3.查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
4.查询排名为 xx 的数
5.求 xx 的前驱(前驱定义为小于 xx，且最大的数)
6.求 xx 的后继(后继定义为大于 xx，且最小的数)

01tire

  • 功能

    一种数据结构，来维护一些数，可以支持以下操作：
    1.插入 xx 数
    2.删除 xx 数(若有多个相同的数，因只删除一个)
    3.查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
    4.查询排名为 xx 的数
    5.求 xx 的前驱(前驱定义为小于 xx，且最大的数)
    6.求 xx 的后继(后继定义为大于 xx，且最小的数)

  • 基本原理

    将每个数换算成同样长度的二进制01串（高位用零补全），再当成字符串存入字典树。

  1. 插入/删除
void ins(int val,int c)//c与操作有关，插入时为1，删除时为-1
{
    val+=(int)1e7;
    for(int i=31,rt=root,t;i;i--)
    {
        if(!ch[rt][t=(val>>i&1)])ch[rt][t]=++tot;
        num[rt=ch[rt][t]]+=c;
    }
}
  1. 查询排名
int rak(int val,int ret=0,int t=0)
{
    val+=(int)1e7;
    for(int i=31,rt=root,t;i;i--)
    {
        if((t=val>>i&1))ret+=num[ch[rt][0]];
        rt=ch[rt][t];
    }
    return ret;
}
  1. 查询第k位
int kth(int k,int ret=0)
{
    for(int i=31,rt=root,t;i;i--)
        if(k>num[ch[rt][0]])ret|=1<<i,k-=num[ch[rt][0]],rt=ch[rt][1];
        else rt=ch[rt][0];
    return ret-(int)1e7;
}

其余操作可如下处理

cond(5,printf("%d\n",kth(rak(y))+1));
cond(6,printf("%d\n",kth(rak(y+1)+1)+1));

  • 注意

  1. 空间要开32倍；

  2. 复杂度均为严格logn；

    完

版权声明：本文为2574580837wzc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/2574580837wzc/p/12110924.html