模板

struct BIT{

    //宣告
    vector<ll> tree; 
    int _n; //初始化用
    int bit_num; // 初始化用

    int lowbit(int x){
        return x&(-x);
    }

    BIT(int n) {
        bit_num = __lg(n) + 1;
        _n = (1 << bit_num) - 1;
        tree.assign(_n + 1, 0); 
    }

    void update(int i,ll data){ 
        while(i<=_n){
            tree[i]+=data;
            i+=lowbit(i);
        }
    }

    int query(int i){ 
        int re=0;
        while(i){
            re+=tree[i];
            i-=lowbit(i);
        }
        return re;
    }

    int k_th(int k){  // 找第k大
        int now=0; 
        for(int i=bit_num-1;i>=0;i--) {
            if(tree[now+(1 << i)]<k) {
                k-=tree[now+(1 << i)];
                now+= (1 << i);
            }
        }
        return now+1;
    }

};