树状数组倍增（二分）

· · 算法·理论

维护多重集合：

--- 首先显然可以权值线段树二分做。 实际上树状数组也可以做，可能有部分人不知道。 :::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(n\log{n})$。 用于： - 单点修改。 - **全局**二分。 区间修改或区间内二分请使用线段树。