树状数组倍增（二分）：可以过平衡树板子！
Unaccepted_Zhou
·
·
算法·理论
维护多重集合：
---
首先显然可以权值线段树二分做。
实际上树状数组也可以做，可能有部分人不知道。
:::info[思考过程]
类似于线段树，考虑从最大的块 $2^w$ 开始。
如果这一块 $<k$ 找右子树，否则找左子树。
找右子树相当于将当前位置增大 $2^w$，向左不变。
然后以此类推。
:::
其实就是从 $0$ 开始的倍增。
:::info[正确性]
考虑当前位置 $p$，倍增 $2^w$，需要判断 $(p,p+2^w]$。
显然 $2^{w+1}\mid p$。
则有 $2^{w+1}\nmid p+2^w$，$2^w\mid p+2^w$。
则有 $p+2^w$ 的 lowbit 为 $2^w$。
则有树状数组上 $c_{p+2^w}=(p,p+2^w]$。
:::
:::success[code]
```cpp
ll p=0,k=/*输入*/;
for(ll w=1<<21;w;w>>=1)
if(p+w<=n&&c[p+w]<k) p+=w,k-=c[p];
printf("%lld\n",p+1);
//注意：一定加 <=n，否则溢出部分的 c 全是 0
```
:::
时间复杂度：显然小常数 $O(\log{n})$。
用于：
- 单点修改的数据结构问题。
---
更多应用：
- 区间二分。以值域区间第 $k$ 小为例，先查询 $[1,l)$ 的元素数，然后全局二分。
- 前驱后继。后继为例，查找 $[1,x]$ 的元素数 $k$，然后找第 $k+1$ 小元素。
:::success[657B 树状树组倍增实现普通平衡树]
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll k=1e7+5,N=k<<1;
ll a[N],n,o,x;
ll ct(ll x){
ll s=0;
for(ll i=x+k;i;i-=i&-i)
s+=a[i]; return s;
}
ll nm(ll x){
ll s=0;
for(ll i=24;i>=0;i--)
if(s+(1<<i)<N&&a[s+(1<<i)]<x)
s+=1<<i,x-=a[s]; return s+1-k;
}
int main(){
scanf("%lld",&n);
while(n--){
scanf("%lld%lld",&o,&x);
if(o<3)
for(ll i=x+k;i<N;i+=i&-i)
o==2?a[i]--:a[i]++;
else if(o==3) x=ct(x-1)+1;
else if(o==4) x=nm(x);
else if(o==5) x=nm(ct(x-1));
else x=nm(ct(x)+1);
if(o>2) printf("%lld\n",x);
}
return 0;
}
```
:::
:::success[1020B 线段树二分实现普通平衡树加强版]
要不是 `unordered_map` 常数过大我也用不着线段树。
```cpp
#include<bits/stdc++.h>
#define k (l+r>>1)
using namespace std;
typedef int ll;
const ll N=3e7+10,V=(1<<30)-1;
ll p[N],L[N],R[N];
ll n,m,o,x,y,K=1,z,c=1,F;
ll b(ll &x){return x?x:x=++c;}
void d(ll u,ll l,ll r){
if(r==1) F++;
if(l==r){p[u]+=K; return;}
if(x<=k) d(b(L[u]),l,k);
else d(b(R[u]),k+1,r);
p[u]=p[L[u]]+p[R[u]];
}
ll q(ll u,ll l,ll r){
if(!u) return 0; ll s=0;
if(r<=x) return p[u];
if(k<x) s=q(R[u],k+1,r);
return s+q(L[u],l,k);
}
ll f(ll u,ll l,ll r){
if(l==r) return l;
if(x<=p[L[u]])
return f(L[u],l,k);
x-=p[L[u]];
return f(R[u],k+1,r);
}
ll ct(ll t)
{x=t; return q(1,0,V);}
ll nm(ll t)
{x=t; return f(1,0,V);}
int main(){
scanf("%d%d",&n,&m);
while(n--)
scanf("%d",&x),d(1,0,V);
while(m--){
scanf("%d%d",&o,&x),x^=y;
if(o<3) K=o==2?-1:1,d(1,0,V);
else if(o==3) y=ct(x-1)+1;
else if(o==4) y=nm(x);
else if(o==5) y=nm(ct(x-1));
else y=nm(ct(x)+1);
if(o>2) z^=y;
}
printf("%d",z);
return 0;
}
```
:::
没有区间移动或翻转的似乎很多都能树状树组或线段树搞掉（？）
---
补充：ST 表倍增（二分）
这个更显然，不细讲了，直接倍增即可。虽然时间复杂度不变，但可以省去一堆代码。
应用：查找位置 $i$ 右面第一个 $\le k$ 的元素。