01trie实现平衡树功能(32倍空间换时间)
cpp
namespace Trie{
int tr[N*33][2],cnt[N*33];
int idx;
constexpr int P=1e7;// [-1e7,1e7]
void insert(int val,int c){
val+=P;
int p=0;
for(int i=30;i>=0;i--){
int t=val>>i&1;
if(!tr[p][t])tr[p][t]=++idx;
cnt[tr[p][t]]+=c;
p=tr[p][t];
}
}
int find_rank(int val){
val+=P;
int p=0,ans=0;
for(int i=30;i>=0;i--){
int t=val>>i&1;
if(t){
if(tr[p][0])ans+=cnt[tr[p][0]];
if(!tr[p][1])break;
p=tr[p][1];
}
else{
if(tr[p][0])p=tr[p][0];
else break;
}
}
return ans+1;
}
int kth(int k){
int p=0,ans=0;
for(int i=30;i>=0;i--){
if(tr[p][0]&&cnt[tr[p][0]]>=k)p=tr[p][0];
else{
k-=cnt[tr[p][0]];
p=tr[p][1];
ans+=1<<i;
}
}
return ans-P;
}
int find_prev(int val){
return kth(find_rank(val)-1);
}
int find_next(int val){
return kth(find_rank(val+1));
}
};