权值树状数组求第k大/小数

_Mount_ · 2025-04-17 21:29:58 · 算法·理论

rt，代码如下：

int kth(int k){
    int sum = 0,x = 0;
    for(int i = lg[n];i >= 0;-- i){
        int y = x + (1<<i);
        if(y < m && sum + tr[y] < k){
            x = y;
            sum += tr[y];
        }
    }
    return x+1;
}