01trie

GeorgeJia · 2018-09-02 20:25:55 · 题解

01trie

已知最好写的平衡树，至少目前常数最小（测了大部分平衡树实现）

跑的比动态开点线段树什么的快多了

比Splay快1.5-2倍

唯一缺点是不能像Splay一样区间操作（不过能做这个的好像不多...）

还有内存占用较大，不过正常使用1e5-3e5几乎都是最大30M左右

主要是基于二进制分解的 Trie

同时满足二叉查找树，线段树和平衡树性质，具有高可扩展性

#include <cstdio>
#include <algorithm>
const int maxlog = 25;
const int MAXN = 100010;
using namespace std;

namespace trie{
    int id = 2;//此时id = 2 
    int ch[MAXN * maxlog][2];
    int sz[MAXN * maxlog];
    //int nval[MAXN * maxlog];
    int newnode(){
        ch[id][0] = ch[id][1] = sz[id] = 0;
        return id++;
    }               
    void ins(int x,int d){          
        int u = 1;          
        for(int i = maxlog - 1;i >= 0;i--){         
            int v = (x >> i) & 1;//必须是左移x           
            if(!ch[u][v]) ch[u][v] = newnode();         
            u = ch[u][v];       
            sz[u] += d;//sz[1] = 0;     
        }               
        //nval[u] += d;             
    }                                       
    int kth(int k){
        int u = 1;
        int x = 0;
        for(int i = maxlog - 1;i >= 0;i--){
            if(sz[ch[u][0]] >= k){  ///////////////////////////> >=                     
                u = ch[u][0]; 
            }
            else{
                x |= (1 << i);
                k -= sz[ch[u][0]];
                u = ch[u][1];
            }
        }
        return x;
    }
    int nlt(int x){
        int ans = 0;
        int u = 1;
        for(int i = maxlog - 1;i >= 0;i--){
            if((x >> i) & 1){
                ans += sz[ch[u][0]];
                u = ch[u][1];
            }
            else{
                u = ch[u][0];
            }
            if(!u) break;//不必有的 
        }             
        return ans;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
    }   
    void clear(){
        ch[1][0] = ch[1][1] = 0;
        id = 2;
    } 
    int pre(int x){
        int ans;
        //ins(x,1);
        ans = kth(nlt(x));
        //ins(x,-1);
        return ans;
    }
    int next(int x){
        int ans;
        //ins(x,1);
        ans = kth(nlt(x+1)+1);
        //ins(x,-1);
        return ans;
    }
} 

const int num = 10000000; 
int main(){
     int n;
     scanf("%d",&n);
     for(int i = 0;i < n;i++){
        int ord,t;
        scanf("%d%d",&ord,&t);
        switch(ord){
            case 1:trie::ins(t + num,1);break;
            case 2:trie::ins(t + num,-1);break;
            case 3:printf("%d\n",trie::nlt(t + num) + 1);break;
            case 4:printf("%d\n",trie::kth(t) - num);break;
            case 5:printf("%d\n",trie::pre(t + num) - num);break;
            case 6:printf("%d\n",trie::next(t + num) - num);break;
        }
    }
    return 0;
} 

好写好调，常数比splay小1.5-2倍，比动态开点线段树小得多，并且几乎不需要调试

浮点数直接指针强制转long long，按位比较double/single内存是可以的