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;
}