半前缀计数

题解

维护一个序列$a$，支持修改某个元素的值和寻找最小的满足$\sum_{i=1}^t a_i >= k$的$t$。（如果把该序列下标看成值域，值看作出现的次数，则第二种操作表示找第$k$大元素）

显然线段树上二分可以做到$O(logn)$的查询修改复杂度。

但是树状数组同样存在一种类似数位$DP$的方式，将修改操作做到一个$log$的复杂度。（时间空间上更优秀）

考虑树状数组的定义方式，第$i$位$Bit[i] = a[i-2^k+1] + a[i-2^k+2] + … + a[i]$（$k$表示$i$的二进制最低非零位，$2^k$即$lowbit(i)$）（求前缀和时一直减$lowbit$类似于数位$DP$中枚举最低紧贴上限的二进制位来遍历所有数）

利用数位$DP$的思想，从高位到低位逐位确定所求值。（具体看代码实现）

代码

struct BIT{
	int a[N];
	
	void add(int x,int d){
		for(;x<=n;x+=x&-x)a[x]+=d;
	}
	
	int sum(int x){
		int ret=0;
		for(;x;x-=x&-x)ret+=a[x];
		return ret;
	}

	int get(int k){
	    int x=0;
	    for(int i=MAXLOGN;~i;--i){
	    	int x1=x+(1<<i);
	        if(x1<=n&&k>a[x1]){
	            k-=a[x1];
	            x=x1;
	            //类似于数位DP，此处所有下标<=x的原序列的值都已从k中减去
	        }
	    }
	    return x+1;//此处x在满足前x个位置的和小于k的条件下尽可能地大，所以第k大在第x+1个位置上
	}
}T;