树状数组倍增¶

对应线段树二分，树状数组也有自己对应的树上对数级查找算法。这种算法利用了树状数组独特的性质，被称作树状数组倍增。

如何倍增？¶

我们都知道，树状数组下标为 $i$ 的位置存储着 $(i-\operatorname{lowbit}(i),i]$ 的信息。

int query(int x){
    int res(0);
    for(; x; x -= x & -x)
        res += tr[x];
    return res;
}

考虑以上过程。以 $100101001010$ 为例，它的贡献是这样计算的：

$T(1001010010\textbf10)+T(10010100\textbf{1}000)+T(10010\textbf1000000)+T(100\textbf100000000)+T(100000000000)$

换句话讲，就是逐次去除最低位。

考虑反向计算贡献，即逐次添加最高位。这样的过程实际上就是倍增。