时间戳

首页 > 技术文章 > 普通平衡树的几种代替写法

普通平衡树的几种代替写法

lxh-acmer 2021-05-19 21:28 原文

前言

由于平衡树肥肠难写，没有经常写平衡树的话，我们几乎很难调好平衡树。我们不得不想出能够代替二叉树的一些操作并且时间复杂度并不太高。

题目背景：普通平衡树

01 Tire(在线做法)

做法其实是trie的模板做法啦！

sum[p]从代码中可以直接看出来，就是表示插入数的时候经过这个结点的次数，其实我们稍微转换一下，也就是结点p的子结点的个数。
getrank(x)表示的是小于x的数的个数，getkey(x)表示第x个数于是我们可以知道对于每条询问的表达方式了。

  1. insert(x,1) 显然加入就+1。
  2. insert(x,-1) 删除就-1。
  3. getrank(x)+1 因为getrank(x)表示小于x的数的个数，加一就是x的位置。
  4. getkey(x) 获取排名为x的值。
  5. key(rank(x))翻译过来就是：名次i为小于x的数的个数，即i = rank(x)，然后key(i)就是小于x的最大值了。
  6. 类似5，我们做一个简单的推理，首先最后的表达式应该式类似于key(rank(x))这样的形式的，然后需要查找的是大于x的最小值，也就是等价于先求小于等于x的数的个数，设为i然后求key(i + 1)即可，也就是key(rank(x + 1) + 1)

输入有可能为负数，所以我们需要将所有数加上一个BASE

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+100,M=32*N;
const int BASE=1e7;

int trie[M][2],tot=1;
int sum[M];

void insert(int x,int t){
    int p=1;
    x+=BASE;
    for(int i=30;i>=0;i--){
        int c=x>>i&1;
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
        sum[p]+=t;
    }
}

int getrank(int x){
    x+=BASE;
    int p=1;
    int res=0;
    for(int i=30;i>=0;i--){
        int c=x>>i&1;
	//当该位为1时，找其他的该位为0的数的个数，就是严格小于这个数的个数了
        if(c) res+=sum[trie[p][0]]; 
        p=trie[p][c];
    }
    return res;
}

int getkey(int x){
    int p=1;
    int res=0;
    for(int i=30;i>=0;i--){
        if(x>sum[trie[p][0]]){
		//比当前位为0的所有值都大。
            res+=1<<i;
            x-=sum[trie[p][0]];
            p=trie[p][1];
        }
        else p=trie[p][0];
    }
    return res-BASE;// 因为有偏移量所以需要减去一个偏移量
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    while(n--){
        int op,x;
        cin>>op>>x;
        if(op==1) insert(x,1);
        else if(op==2) insert(x,-1);
        else if(op==3) cout<<getrank(x)+1<<endl;
        else if(op==4) cout<<getkey(x)<<endl;
        else if(op==5) cout<<getkey(getrank(x))<<endl;
        else cout<<getkey(getrank(x+1)+1)<<endl;
    }
    return 0;
}

树状数组+离散化（离线做法）

值域范围不大时，所以可以之间在线做，但一般开到\(10^9\),这时候就需要离散化三连sort,unique,lower_bound，在离散化之后树状数组用来维护值域。
Hash(x) 离散后x所在的位置

  1. add(Hash(x),1) 在x的位置 +1 表示添加。
  2. add(Hash(x),-1) 在x的位置-1 表示删除。
  3. sum(Hash(x)-1)+1 表示查询x-1的前缀和就是比x的小的所有数的个数，+1后就是排名。
  4. query(x) 就是找到前缀和中第一个大于等于x的对应的数，因为前缀和其实就是排名。
  5. query(sum(Hash(x)-1)) 比如比x小的有k个数，我只要正好找到前缀和中第一个大于等于k对应的数就好了
  6. quert(sum(Hash(x))+1) 为什么查询前驱从sum(x-1)里找而后继要从sum(x)+1而不是sum(i+1)里找呢，这是因为我们为了离散化方便把查询排名的x也插了进去，这个地方可能是没有数的，sum(i+1)就和sum(x) 一样了

如何查询前缀和？

  1. 二分
  2. 树状数组的性质（代码采用了这条性质）
    image

我们发现二的幂次方维护的值从开头开始的，假设我们现在在8这个点，维护的是8的前缀和，但这个值已经比k大了，不满足最小，所以我们跳到4，其实就相当于往左儿子走，假如5是符合要求的，那我们从4跳6(+\(2^1\))到发现不可以,然后跳到5可以，之后返回，所以时间复杂度是和logn有关的，总之可以通过。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+100;

#define pii pair<int,int>
pii p[N];
int a[N],tot=0;
int Hash(int x){ return lower_bound(a+1,a+1+tot,x)-a;}

int c[N];
int lowbit(int x){ return x&-x;}
void add(int x,int t){
    for(;x<=tot;x+=lowbit(x)) c[x]+=t;
}

int sum(int x){
    int res=0;
    for(;x;x-=lowbit(x)) res+=c[x];
    return res;
}

int query(int x){
    int t=0;
    for(int i=19;i>=0;i--){
        t+=1<<i;
        if(t>tot||c[t]>=x) t-=1<<i;
        else x-=c[t];
    }
    return a[t+1];
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int op,x;
        cin>>op>>x;
        p[i]={op,x};
        if(op!=4) a[++tot]=x;
    }
    sort(a+1,a+1+tot);
    tot=unique(a+1,a+1+tot)-(a+1);//离散化
    
    for(int i=1;i<=n;i++){
        int op=p[i].first,x=p[i].second;
        if(op==1) add(Hash(x),1);
        else if(op==2) add(Hash(x),-1);
        else if(op==3) cout<<sum(Hash(x)-1)+1<<endl;
        else if(op==4) cout<<query(x)<<endl;
        else if(op==5)cout<<query(sum(Hash(x)-1))<<endl;
        else cout<<query(sum(Hash(x))+1)<<endl;
    }
    
    return 0;
}

推荐阅读