一种树状数组上二分的方法

前言

近日鄙人通过剽窃一位神的提交记录碰巧学会了树状数组的新的应用，再加上在OIwiki上的查阅后颇有理解，故写此文以记之。

原理

首先树状数组的结构是很巧妙的，下标为 $i$ 的节点统计的是下标为 $i-lowbit(i)+1$ ~ $i$ 的节点上的权值。而统计的方式就是通过把满足 $x+lowbit(x)=i$ 的所有下标 $x$ 上的值全部累加进 $i$ 中，过程大概如下图：

就拿查询第 $k$ 大来举例，其实这玩意儿完全可以像线段树二分一样。不难发现其实这玩意儿和线段树的形状很像，只不过每一层只往下一层连接了左儿子。没关系，我们可以脑补出右儿子，然后就像线段树那样一层层往下找。

实现

模拟一下线段树的查找过程，实际上是在二进制下从高位往低位一位位确定，假如现在在线段树的深度为 $dep$ 的节点上做决策，那么对答案产生的影响的步长为 $[1<<dep]$ ，是逐渐减少的，因此可以枚举目前做到第 $i$ 位，然后考虑是否拓展，如果拓展就直接在下标 $now$ 上加上 $[1<<i]$ ， 值 $ret$ 上直接加 $s[now+(1<<i)]$ （由于$i$是从高往低枚举，所以下标改变后的 $lowbit$ 就是 $[1<<i]$ 然后 $s[now+(1<<i)]$ 管的刚好就是 $now+1$ ~ $now+(1<<i)$ 范围的值，然后直接加上即可，这样加的话不用query ，时间复杂度少了一个 $log$ ），这样总的时间复杂度就是枚举 $i$ 的次数，也就是 $O(log~n)$ 。

int kth(int k){
    int p=0,val=0;
    for(int i=log(n);i>=0;--i){
        p+=1<<i;
        if(p>n||val+s[p]>k)p-=1<<i;
        else val+=s[p];
    }
    return p
}