树状数组

Question 01 [P3374 树状数组一]
模板题

Code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;
class Tree{
	public:
		inline void scan(long long *_data,int _size){ 
			size=_size;
			for(int i=1;i<=size;i++)_data[i]+=_data[i-1];
			for(int i=1;i<=size;i++)data[i]=_data[i]-_data[i-lowbit(i)];
		}
		inline void modify(int pos,long long key){
			while(pos<=size)data[pos]+=key,pos+=lowbit(pos);
		}
		inline long long query(int pos){
			long long ans=0;
			while(pos>0)ans+=data[pos],pos-=lowbit(pos);
			return ans;
		}
	private:
		int size;
		long long data[N];
		inline int lowbit(int x){
			return x&-x;
		}
}; 
long long lable[N];
Tree tree;
int main(){
	int n,T,op,pos,rim,lim;
	long long key;
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;i++)scanf("%lld",&lable[i]);
	tree.scan(lable,n);
	while(T--){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%lld",&pos,&key);
			tree.modify(pos,key);
		}else{
			scanf("%d%d",&lim,&rim);
			printf("%lld\n",tree.query(rim)-tree.query(lim-1));
		}
	}
	return 0;
} 

Question 02 [ACP2146 数星星]
二维偏序模板 
大概题意是给定一些点 (x,y) 
对于每个点求横纵坐标不大于该点横纵坐标的点的数量 
即求点(x*, y*) 使得 x*<= x 且 y*<= y 的数量
(点不会重合并且数量不算它自己)
AcCoders 的输入很良心
正常我们需要先排序来解决一维偏序 
其实按哪一维为第一关键字排序都可以
假定我们以 y 为第一关键字排序 

排序 Code
bool cmp(Shit A,Shit B){
	if(A.y==B.y)return A.x<B.x;
	return A.y<B.y; 
} 

接下来我们用树状数组再解决另一维 
我们按顺序遍历每一个点 
首先已经能够确定只要在其前面的都能保证 y* <= y 了
只需再确定 x*<= x 的数量
(由于我们在 y*== y 的时候已经保证 x 单调递增,无需考虑后面的)
接下来用树状数组类似桶排的方式再解决一维
将每一个点的 y 坐标插入树状数组
然后求和即可 
 
Code
#include<bits/stdc++.h>
using namespace std;
const int N=66666;
class Tree{ 
	public:
		inline void modify(int pos,long long key){
			while(pos<=size)data[pos]+=key,pos+=lowbit(pos);
		}
		inline long long query(int pos){
			long long ans=0;
			while(pos>0)ans+=data[pos],pos-=lowbit(pos);
			return ans;
		}
	private:
		int size=33330;
		long long data[N]={};
		inline int lowbit(int x){return x&-x;}
}; 
Tree tree;
int main(){
	int T,x,y;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&x,&y);
		++x;//x maybe zero ,And It will cause INF loops!
		printf("%lld\n",tree.query(x));
		tree.modify(x,1);
	} 
	return 0;
}