python/TangDou/AcWing/权值树状数组的简单介绍.md

https://blog.csdn.net/xiji333/article/details/88538920 https://blog.csdn.net/xiji333/article/details/88537527

一、权值数组

for i =1 to n  do A[a[i]]++

权值数组的$A[i]$存储的是给定序列$a[1]-a[n]$中等于$i$的元素个数。

二、权值数组前缀和

for i = minval+1 to maxval do A[i]+=A[i-1]
minval=min{a[i]} 
maxval=max{a[i]}

此时$A[i]$的含义已经从权值数组 转化成 权值数组前缀和。注意下标从1开始。 也就是说，权值数组的前缀和$A[i]$就表示原序列$a[1]-a[n]$中小于等于$i$的元素个数。

三、权值树状数组

inline int lowbit(int x){
	return x&(-x);
}
 //小于等于v的元素的数目
int getsum(int v){
	int s=0;
	for(;v;v-=lowbit(v)) s+=cnt[v];
	return s;
}
//将值为v的元素增加num个
void update(int v,int num){
	for(;v<=maxn;v+=lowbit(v)) cnt[v]+=num;
}

根据前面的了解，我们知道$getsum(v)$得到的是原序列中小于等于$v$的元素的个数，$update(int v，int num)$是在原序列中插入$num$个值为$v$的元素。

四、有什么用呢？

权值数组前缀和是单调递增的，那么权值树状数组自然也是单调递增的，利用这一点我们可以二分查询原序列中第$k$大的值。拿$getsum(mid)$的值跟$k$值相比来缩小上下界就可以做到这一点。时间复杂度$O((logn)^2)$。

while(l<=r){
	int mid=(l+r)>>1;
	int t=getsum(mid);
	if(t<k)
		l=mid+1;
	else
		r=mid-1;
}
printf("%d\n",l);

还有一种时间复杂度为O(lgn)的方法，比较玄学，我大概解释一下吧。首先我们假设第$k$大的数为$temp$，那么$getsum(temp)=k$，那么如果我们能找到满足$getsum(i)<k$的最大的$i$，那么$i$必定为$temp-1$，即第$k$大的数等于$i+1$。这就是这个函数的核心思想。

再深入一点，$i$又可以写成二进制的形式，假设$i=2^n+2^(n-1)+……+2^t+……+2^0$，那么求$getsum(i)$的过程就是求$tree[i]+tree[i-2^0]+tree[i-2^0-……-2^t]+tree[i-2^0-……-2^t-……-2^(n-1)]$，也即求$tree[2^n]+tree[2^n+2^(n-1)]+……+tree[i]$，我们发现，只要从二进制的高位向低位扩展，求$i$的过程就可以顺便求出$getsum(i)$，从而降低时间复杂度。

int find_kth(int k){
	int ans=0,sum=0,i;
	for(int i=20;i>=0;i--){
		ans+=(1<<i);
		if(ans>=maxn||sum+cnt[ans]>=k)
			ans-=(1<<i);
		else
			sum+=cnt[ans];
	}
	return ans+1;
}