树状数组的应用_树状数组求左侧小于该元素的元素个数

1 统计序列中在元素左边比该元素小的元素个数

#include<stdio.h>
#include<string.h>
#define lowbit(i) ((i)&(-i))
const int maxn=100010;
int c[maxn];	//树状数组 
 
//getSum函数返回前x个整数之和 
int getSum(int x){
	int sum=0;	//记录和 
	for(int i=x;i>0;i-=lowbit(i)){ 
		sum+=c[i];	//累计c[i]，然后把问题缩小为sum(1,i-lowbit[i]) 
	}
	return sum;	//返回和 
}
 
//update函数将第x个整数加上v
void update(int x,int v){
	for(int i=x;i<maxn;i+=lowbit(i)){
		c[i]+=v;
	}
}
 
int main(){
	int n,x;
	scanf("%d",&n);
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		update(x,1);
		printf("%d\n",getSum(x-1)); 
	}
	return 0;
}

2 求序列中第k大的元素

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
#define lowbit(i) ((i)&(-i))
 
struct Node{
	int val;	//序列元素的值 
	int pos;	//原始序号 
}temp[maxn];
 
//a是离散化后的原始数组，c是树状数组 
int a[maxn],c[maxn]; 
 
//update函数将第x个整数加上v
void update(int x,int v){
	for(int i=x;i<maxn;i+=lowbit(i)){
		c[i]+=v;
	}
} 
 
//getSum函数返回前x个整数之和
int getSum(int x){
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i)){
		sum+=c[i];
	}
	return sum;	//返回和 
} 
 
//按val从小到大排序
bool cmp(Node a,Node b){
	return a.val<b.val;
} 
 
//求序列元素第k大 
int findKthElement(int k){
	int l=1,r=maxn,mid;
	while(l<r){
		mid=(l+r)/2;
		if(getSum(mid)>=k) r=mid;
		else l=mid+1;
	}
	return l;
}
 
int main(){
	int n;
	scanf("%d",&n);
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++){
		scanf("%d",&temp[i].val);
		temp[i].pos=i;
	}
	//离散化
	sort(temp,temp+n,cmp);
	for(int i=0;i<n;i++){
		//与上一个元素值不同时，赋值为元素个数
		if(i==0||temp[i].val!=temp[i-1].val){
			a[temp[i].pos]=i+1;	//这里必须从1开始 
		}else{	//与上一个元素值相同时，直接继承 
			a[temp[i].pos]=a[temp[i-1].pos]; 
		}
	} 
	//正式进入更新和求和操作
	for(int i=0;i<n;i++){
		update(a[i],1);	//a[i]的出现次数加1
		printf("%d\n",getSum(a[i]-1));	//查询当前小于A[i]的数的个数 
	} 
	return 0;
}