HDU 1892（See you~ 简单二维树状数组）
题目大意：
S x1 y1 x2 y2 means you should tell me the total books of the rectangle used (x1,y1)-(x2,y2) as the diagonal, including the two points.
A x1 y1 n1 means I put n1 books on the position (x1,y1)
D x1 y1 n1 means I move away n1 books on the position (x1,y1), if less than n1 books at that position, move away all of them.
M x1 y1 x2 y2 n1 means you move n1 books from (x1,y1) to (x2,y2), if less than n1 books at that position, move away all of them.
就这几个操作
题目分析：
这题唯一注意的地方是给出的点不一定是前面的比后面的小，我是说查询以这两点为对角线的矩形里面的书的数量的时候，还有你要更新到1001，因为你为防止0的死循环，所以把每个坐标，都加1 这样可以防止死循环；如果他输入 是（1000 ，1000） ，你要计算的是(1001,1001) 所以你要更新到1001！
#include<iostream>
#include<cstdio>
#include<cstring>
#define lowbit(x) (x&(-x))
using namespace std;
int s[1005][1005],num[1005][1005];
int getsum(int x,int y){
int t,sum;
sum=0;
while(x>0){
t=y;
while(t>0){
sum+=s[x][t];
t-=lowbit(t);
}
x-=lowbit(x);
}
return sum;
}
void modify(int x,int y,int count){
int t;
while(x<=1001){
t=y;
while(t<=1001){
s[x][t]+=count;
t+=lowbit(t);
}
x+=lowbit(x);
}
return ;
}
int main(){
int cas,times,i,j,k;
int x1,x2,y1,y2,n;
int maxx,maxy,minx,miny;
char ch[10];
scanf("%d",&cas);
for(k=1;k<=cas;k++){
printf("Case %d:\n",k);
for(i=1;i<=1002;i++)
for(j=1;j<=1002;j++){
num[i][j]=1;
s[i][j]=lowbit(i)*lowbit(j);
}
scanf("%d",×);
while(times--){
scanf("%s",ch);
if(ch[0]=='S'){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++; y1++; x2++; y2++;
maxx=x1>x2?x1:x2;
maxy=y1>y2?y1:y2;
minx=x1<x2?x1:x2;
miny=y1<y2?y1:y2;
x2=maxx; x1=minx;
y2=maxy; y1=miny;
int ans=getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1);
printf("%d\n",ans);
}
if(ch[0]=='A'){
scanf("%d %d %d",&x1,&y1,&n);
x1++; y1++;
num[x1][y1]+=n;
modify(x1,y1,n);
}
if(ch[0]=='D'){
scanf("%d %d %d",&x1,&y1,&n);
x1++; y1++;
if(num[x1][y1]<=n){
n=num[x1][y1];
}
num[x1][y1]-=n;
n=-n;
modify(x1,y1,n);
}
if(ch[0]=='M'){
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&n);
x1++; y1++; x2++; y2++;
if(num[x1][y1]<=n){
n=num[x1][y1];
}
num[x1][y1]-=n;
num[x2][y2]+=n;
modify(x1,y1,-n);
modify(x2,y2,n);
}
}
}
return 0;
}
POJ 1990（MooFest）经典题目
题目概括：由n头牛，不同的听力值v，当i,j想要通话时，需要max(v(i),v(j))*(dist[i]-dist[j])的volume，问这n*(n-1)/2对牛总共的volume时多少。
题目分析：这里先把各个牛的信息都存放在结构体数组(s[i])里面，然后对这个结构体排序，按volume升序排序。因为这样可以保证先插入的必定比当前这头牛的volume小！首先解决了题目的一个要求，然后就是有效的计算出，各个牛距离当前牛的dist距离和，首先利用树状数组，计算出左边牛的头数(count)和左边牛的x轴坐标和(total)；然后计算出整个区间上牛的坐标和(alltotal)。
根据公式：sum+= s[i].v* [ s[i].x * count - total + alltotal - ( i- count - 1 ) * s[i].x ] ;
源程序+部分注释：
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#define lowbit(x) (x&(-x))
#define N 20020
using namespace std;
struct node{
long long v;
int x;
}s[N];
int cmp(struct node a,struct node b){
return a.v<b.v;
}
long long sim[N],c[N];
long long getsum(long long t[],int x){
//因为每个函数都要进行两个操作，分别在不同数组里建图
//所以要把数组作为参量写入！
long long sum=0;
while(x>0){
sum+=t[x];
x-=lowbit(x);
}
return sum;
}
int modify(long long t[],int x,long long num){
while(x<=N){
t[x]+=num;
x+=lowbit(x);
}
return 0;
}
int main(){
long long sum,total,alltotal,count;
int i,cas;
while(scanf("%d",&cas)!=EOF){
sum=0;
memset(c,0,sizeof(c));
memset(sim,0,sizeof(sim));
for(i=1;i<=cas;i++){
scanf("%lld %d",&s[i].v,&s[i].x);
}
sort(s+1,s+1+cas,cmp);
for(i=1;i<=cas;i++){
alltotal=getsum(c,20001);
total=getsum(c,s[i].x);
count=getsum(sim,s[i].x);
sum+=s[i].v*(count*s[i].x-total+alltotal-total-s[i].x*(i-count-1));
modify(c,s[i].x,s[i].x);
modify(sim,s[i].x,1);
}
printf("%lld\n",sum);
}
return 0;
}
POJ 2155（Matrix）非常规思路
颠覆树状数组的常规模式，这题有些地方还有疑点！关于怎么计算点的翻转次数，为什么是他前面比他大的个数呢？回来再好好想想！
#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 2001
#define lowbit(x) (x&(-x))
using namespace std;
int c[N][N];
int UPdate(int x,int y,int num){
int k;
while(x>0){
k=y;
while(k>0){
c[x][k]^=num;
k-=lowbit(k);
}
x-=lowbit(x);
}
return 0;
}
int getsum(int x,int y){
int sum=0,k;
while(x<=N){
k=y;
while(k<=N){
sum^=c[x][k];
k+=lowbit(k);
}
x+=lowbit(x);
}
return sum;
}
int main(){
int cas,i,n,q;
int x1,x2,y1,y2;
char sign;
cin>>cas;
while(cas--){
memset(c,0,sizeof(c));
scanf("%d %d",&n,&q);
while(q--){
cin>>sign;
//getchar();
if(sign=='C'){
cin>>x1>>y1>>x2>>y2;
x1++; x2++; y1++; y2++;
//printf("%d %d %d %d",x1,y1,x2,y2);
UPdate(x2,y2,1); UPdate(x1-1,y2,1);
UPdate(x2,y1-1,1); UPdate(x1-1,y1-1,1);
}
if(sign=='Q'){
scanf("%d %d",&x1,&y1);
x1++; y1++;
printf("%d\n",1&getsum(x1,y1));
}
}
printf("\n");
}
return 0;
}
POJ 2029（Get Many Persimmon Trees）
题目大意：一个H * W的大矩形，里面的某些格子种有树。现在要你找出一个h * w的小矩形，使得里面树的数量最多，问最多有多少棵树
题目分析：就是求二维的矩形和，然后枚举各个满足条件矩形和的最大值。
源程序+部分注释：
#include<iostream>
#include<stdio.h>
#include<string.h>
#define lowbit(x) (x&(-x))
using namespace std;
int w,h;
int c[120][120];
int getsum(int x,int y){
int i=x,j,sum=0;
while(i){
j=y;
while(j){
sum+=c[i][j];
j-=lowbit(j);
}
i-=lowbit(i);
}
return sum;
}
int modify(int x,int y){
int k;
while(x<=w){
k=y;
while(k<=h){
c[x][k]+=1;
k+=lowbit(k);
}
x+=lowbit(x);
}
return 0;
}
int count_sum(int x,int y,int xm,int ym){
int sum=0;
sum=getsum(x,y)-getsum(x-xm,y)-getsum(x,y-ym)+getsum(x-xm,y-ym);
return sum;
}
int main(){
int n,s,t;
int i,j,x,y,max,ans;
while(scanf("%d",&n),n){
memset(c,0,sizeof(c));
max=0;
scanf("%d %d",&w,&h);
for(i=1;i<=n;i++){
scanf("%d %d",&x,&y);
modify(x,y);
}
scanf("%d %d",&s,&t);
for(i=s;i<=w;i++)
for(j=t;j<=h;j++){
ans=count_sum(i,j,s,t);
if(max<ans)
max=ans;
}
cout<<max<<endl;
}
return 0;
}
POJ 3067(Japan)树状数组求线的交点
题目大意： 顺序给两组平行的点依次编号1~N和1~M，给定K个线段在两组点之间，求相交(cross)的线段对有多少个，同一个起点或终点不算相交
题目分析：把N从大到小排序，注意：当N相等的时候按M的从大到到小！因为我们计算的时候，求N点构成的交点的个数只需要遍历他前面的点对，因为他前面的点对的N值肯定比他大，所以只要M的值比他小肯定就构成了1个交点，所以转换为计算比当前值小的数的个数！这就是树状数组的真谛！然后如果当N相等的时候时候，如果把M小的放前面，计算他后面那个N值相等的点的时候，前面M比他小错误的加上了1，所以当N相等的时候必须按M从大到小的安放！
源程序+部分注释：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
long long c[1010];
const int N=1005;
struct node{
int w;
int v;
}s[1000002];
bool cmp(struct node a,struct node b){
if(a.w==b.w)
return a.v>b.v;
else
return a.w>b.w;
}
//关键在排序注意一下！
long long getsum(int x){
long long sum=0;
while(x){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int modify(int pos){
while(pos<=N){
c[pos]+=1;
pos+=lowbit(pos);
}
return 0;
}
int main(){
int cas,k,r,m ,i,t;
scanf("%d",&cas);
while(cas--){
k=1;
scanf("%d %d %d ",&r,&m,&t);
memset(c,0,sizeof(c));
long long ans=0;
for(i=1;i<=t;i++)
scanf("%d %d",&s[i].w,&s[i].v);
sort(s+1,s+1+t,cmp);
for(i=1;i<=t;i++){
ans+=getsum(s[i].v-1);
modify(s[i].v);
}
printf("Test case %d: %lld \n", k++, ans);
}
return 0;
}
POJ 2481（Cows）树状数组
题目分析：题意大概是这样的，给一些组数据，每i组有两个数S(i)和 E(i)，对于每组，求出有多少组满足 S(t) <= S(i), E(t) >= E(i), E(t)-S(t) > E(i)-S(i);
首先将S[i]降序排序，如果相等则按E[i]的升序。除去特殊情况，所有都满足公式！如果遇到完全重合的数据，则单独考虑，也就是不需求和计算，只需把前面的值赋值给他，
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define lowbit(x) (x&(-x))
#define N 100010
using namespace std;
int c[100002],sim[100002];
struct node{
int s;
int order;
int e;
}s[100002];
bool cmp(struct node a,struct node b){
if(a.e!=b.e)
return a.e>b.e;
else
return a.s<b.s;
}
int getsum(int x){
int sum=0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int modify(int pos,int num){
while(pos<N){
c[pos]+=num;
pos+=lowbit(pos);
}
return 0;
}
int main(){
int cas,i,st,et;
while(~scanf("%d",&cas)&&cas){
memset(c,0,sizeof(c));
for(i=1;i<=cas;i++){
scanf("%d%d",&s[i].s,&s[i].e);
s[i].s++; s[i].e++;
s[i].order=i;
}
sort(s+1,s+1+cas,cmp);
int ans=getsum(s[1].s);
sim[s[1].order]=ans;
modify(s[1].s,1);
st=s[1].s; et=s[1].e;
for(i=2;i<=cas;i++){
if(s[i].s==st&&s[i].e==et){
sim[s[i].order]=sim[s[i-1].order];
//重复的就不需要求和，直接把前面的给他
modify(s[i].s,1);
//但是还得修改哦{^_^}
continue;
}
st=s[i].s; et=s[i].e;
int ans=getsum(s[i].s);
sim[s[i].order]=ans;
modify(s[i].s,1);
}
for(i=1; i<=cas; i++) {
if( i != 1 )
printf(" ");
printf("%d",sim[i]);
}
printf("\n");
}
return 0;
}
POJ 1195（Mobile phones）简单二维树状数组
题目大意：给定n*n矩阵，和几种在线操作，包括对某一点(x,y)值修改，查询一个矩形(x1,y1,x2,y2)的元素和。
题目思路：在这里稍微注意一下，每个输入的坐标都加上1，这样防止有0现象发生！Lowbit(0) = 0，这会导致x递增的那条路径发生死循环！求和的公式sum(x2-x1,y2-y1)=getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1);
源程序+部分注释：
#include<iostream>
#include<string.h>
#include<stdio.h>
#define lowbit(x) (x&(-x))
using namespace std;
int c[1050][1050];
int N;
int getsum(int x,int y){
int sum=0;
int j;
while(x){
j=y;
while(j){
sum+=c[x][j];
j-=lowbit(j);
}
x-=lowbit(x);
}
return sum;
}
int modify(int i,int j ,int num){
int k;
while(i<=N){
k=j;
while(k<=N){
c[i][k]+=num;
k+=lowbit(k);
}
i+=lowbit(i);
}
return 0;
}
int main(){
int i,x1,y1,x2,y2;
int cas,a,b,num,t,j;
scanf("%d %d",&cas,&N);
memset(c,0,sizeof(c));
while(scanf("%d",&t),t!=3){
if(1==t){
scanf("%d%d%d",&a,&b,&num);
modify(a+1,b+1,num);
}
else {
if(2==t){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++; y1++; x2++; y2++;
//防止0现象，造成死循环！
printf("%d\n",getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1));
//这个公式就是去除多余的部分，加上在去除过程中重复减去的部分，正好等于所求区域
}
}
}
return 0;
}
POJ 2352（Stars）树状数组
题目分析：就是让您求位于没颗星星左下方的包括自己正下方的星星个数。因为他已经按Y轴排好序的输入了，所以只需要按着顺序在X轴上建立树状数组就可以了。
#include<iostream>
#include<stdio.h>
#define lowbit(x) (x&(-x))
using namespace std;
const int N=32100;
int c[32100],level[15010];
int getsum(int x){
int sum=0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int modify(int pos,int num){
while(pos<=N){
c[pos]+=num;
pos+=lowbit(pos);
}
return 0;
}
int main(){
int m, i,x,y,t;
while(scanf("%d",&t)!=EOF){
m=t;
for(i=0;i<=N;i++){
c[i]=0;
}
for(i=0;i<=15000;i++)
level[i]=0;
while(m--){
scanf("%d %d",&x,&y);
level[getsum(x+1)]++;
//用这个表记录leve出现的次数
modify(x+1,1);
}
for(i=0;i<t;i++)
cout<<level[i]<<endl;
}
return 0;
}
POJ 2299（Ultra-QuickSort）树状数组解逆序数
题目分析：这个题目就是用一个结构体数组，把每个数的值记录下来，还有他初始在数组里的位置，然后进行从小到大排序。
这样就够成了条件1）先插入的必定是值比前面大的！然后每次进行求和，2）只要初始位置也就是坐标轴上的X在我前面的个数就是当前这个数构成逆序的对数。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
inline int lowbit(int x){
return x&(-x);
}
long long c[500001];
long long sum;
struct node{
int num,sert;
}t[500001];
long long getsum(int n){
int ans=0;
while(n>0){
ans+=c[n];
n-=lowbit(n);
}
return ans;
}
int modify(int num,int count){
while(num<500001){
c[num]+=count;
num+=lowbit(num);
}
return 0;
}
int cmp(struct node a,struct node b){
return a.num>b.num;
}
int main(){
int i,N;
while(scanf("%d",&N),N){
sum=0;
memset(c,0,sizeof(c));
for(i=1;i<=N;i++){
cin>>t[i].num;
t[i].sert=i;
}
sort(t+1,t+1+N,cmp);
for(i=1;i<=N;i++){
sum+=getsum(t[i].sert);
//先求和在修改，这样因为第一个插入的肯定
//为0，符号实际意义
modify(t[i].sert,1);
//修改的时候只需要把该位置改为1，也就是代表个数
}
cout<<sum<<endl;
}
return 0;
}