BIT with BS

#define mx 2097152
#define mx2 1429500
#define inf 1000000000000000000
#define int long long

int tree[mx+5];
int ara[mx];

int read(int idx){
    int sum = 0;
    while(idx>0){
        sum += tree[idx];
        idx -= (idx&-idx);
    }
    return sum;
}

void update(int idx, int val){
    while(idx<=mx){
        tree[idx] += val;
        idx += (idx&-idx);
    }
}

int bsonbit(int val){
    int idx = 0, d = mx, tidx;
    val--;
    while(d>0 && idx<=mx){
        tidx = idx + d;
        if(tidx<=mx&&tree[tidx]<=val){
            idx = tidx;
            val -= tree[tidx];
        }
        d >>= 1;
    }
    return idx + 1;
}