树状数组 BIT

lowbit(x)=x&(-x)就是 取x的二进制最右边的1和它所有的0。也可以理解为能整除x的最大2的幂次。
除此之外，如果设C[i]为树状数组,C[i]的覆盖长度使lowbit(i)(也可以理解为管辖范围。
对于树状数组需要解决的两个问题：
1.求出前n个数的和, getSum( )。
2.给第x个数加上v的功能,A[x]+=v。

//getSum函数返回前x个整数之和
int getSum(int x) {
	int sum=0;  //记录和
	for(int i=x;i>0;i-=lowbit(i) {  //注意i>0不是i>=0
		sum+=c[i];   //累计c[i]，然年后把问题缩小为sum(1,i-lowbit(i))
	}
	return sum;  //返回和

//update函数将第x个整数加上v
voif update(int x,int v) {
	for(int i=x;i<=N;i+=lowbit(i)) {  //注意i必须能取到N
		c[i]+=v;  //让c[i]加上v，然后让c[i+lowbit(i)]加上v
	}
}

例问：给定一个有N个正整数序列A(N<=10^5, A[i]<=10^5), 对序列中的每个数，求出序列中它左边比它小的数的个数。

#include<cstdio>
#include<cstring>
const int maxn=100010;
#define lowbit(i) ((o)&)(-i)) //lowbit写成宏定义的形式，注意括号
int c[maxn]; //树状数组
//update函数将第x个整数加上v
void update(int x,int v) {
	for(int i=x;i<maxn;i+=lowbit(i)) { //i<maxn或者i<=n都可以
	c[i]+=v; //累计c[i],然后把问题缩小为SUM(1,i-lowbit(i))
	}
	return sum; //返回和
}
int main( ) {
	int n,x;
	scanf("%d",&n);
	memset(c,0,sizeof(c)); //树状数组初值为0
	for(int i=0;i<n;i++) {
		scanf("%d",&x); //输入序列元素
		update(x,1); //x的出现次数加1
		printf("%d\n",getSum(x-1));
	}
	return 0;
}

寻找第k大的数

int findKthElement (int K) {
	int l=1,r=MAXN,mid; //初始区间为[1,MAXN]
	while(l<r) { //循环，知道[l,r]能锁定单一元素
		mid=(l+r)/2;
		if(getSUM(mid)>=K) r=mid; //所求位置不超过mid
		else l=mid+1; //所求位置大于mid
	}
	return 1;  //返回二分夹出的元素
}

二维树状数组

int c[maxn][maxn];  //二维树状数组
//二维update函数位置为(x,y)的整数加上v
void update(int x,int y,int v) {
	for(int i=x;i<maxn;i+=lowbit(i)) {
		for(int j=y;j<maxn;j+=lowbit(j)) {
			c[i][j] += v;
		}
	}
}
//二维getSum函数返回(1,1)到(x,y)的子矩阵中元素之和
int getSum(int x,int y) {
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i)) {
		for(int j=y;j>0;j-=lowbit(j)) {
		sum+=c[i][j];
		}
	}
	return sum;
}

以上的算法都保证了树状数组能再单点更新、区间查询，一下算法可以进行区间更新、单点查询。
c[i]仍保持和之前一样的长度，即lowbit(i)，值不过C[i]不再表示这段区间的元素值和，而是表示这段区间每个数当前被加了多少。
A[x]的值实际就是覆盖它的若干个“矩形“C[i]的值之和。

//getSum函数返回第x个整数的值
int getSum(int x) {
	int sum=0;  //记录和
	for(int i=x;i<maxn;i+=lowbit(i) { //沿着i增大的路径
		sum+=c[i]; //累计c[i]
	}
	return sum;
}
//update函数将前x个整数都加上v
void update(int x,int v) {
	for( int i=x;i>0;i-=lowbit(i)) { //沿着i减小的路径
		c[i]+=v;  //让c[i]加上v
	}
}