HDU 1166（敌兵布阵）
题目大意：(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
题目分析：目的是纪念我线段树的开端，也是为了今后的回顾。其实就是基本操作，更新跟建树。
源程序+部分注释：
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct node{
int sum,a,b;
}s[140000];
int t[52005],ans;
void Build(int x,int y,int num){
s[num].a=x; s[num].b=y;
if(x==y)
s[num].sum=t[x];
else{
Build(x,(x+y)/2,num+num);
Build(((x+y)/2)+1,y,num+num+1);
s[num].sum=s[num+num].sum+s[num+num+1].sum;
}
}
void Query(int x,int y,int num){
if(x<=s[num].a&&y>=s[num].b)
ans+=s[num].sum;
else{
if(x>(s[num].a+s[num].b)/2)
Query(x,y,num+num+1);
else if(y<=(s[num].a+s[num].b)/2)
Query(x,y,num+num);
else{
Query(x,y,num+num);
Query(x,y,num+num+1);
}
}
}
void Add(int x,int y,int num){
s[num].sum+=y;
if(s[num].a==x&&s[num].b==x)
return ;
else{
if(x<=(s[num].a+s[num].b)/2)
Add(x,y,num+num);
else
Add(x,y,num+num+1);
}
}
int Sub(int x,int y,int num){
s[num].sum-=y;
if(s[num].a==x&&s[num].b==x)
return 0;
else{
if(x<=(s[num].a+s[num].b)/2)
Sub(x,y,num+num);
else
Sub(x,y,num+num+1);
}
}
int main(){
int cas,n,i,k,x,y;
char c[20];
scanf("%d",&cas);
k=1;
while(cas--){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&t[i]);
}
Build(1,n,1);
cout<<"Case "<<k<<":"<<endl;
k++;
while(1){
scanf("%s",c);
if(c[0]=='E')
break;
scanf("%d %d",&x,&y);
if(c[0]=='Q'){
ans=0;
Query(x,y,1);
cout<<ans<<endl;
}
else if(c[0]=='A'){
Add(x,y,1);
}
else{
if(c[0]=='S')
Sub(x,y,1);
}
}
}
return 0;
}
HDU 2852（KiKi's K-Number）
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define max 100000
#define lowbit(x) (x&(-x))
using namespace std;
const int N=100001;
int c[100005],a[100005];
int getsum(int x){
int sum=0;
while(x){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int modify(int x,int num){
while(x<=N){
c[x]+=num;
x+=lowbit(x);
}
return 0;
}
int main(){
int n,i,left,right,md;
int sign,m,t,num1;
while(scanf("%d",&n)!=EOF){
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
while(n--){
scanf("%d",&sign);
if(sign==0){
scanf("%d",&t);
a[t]++;
modify(t,1);
}
else if(sign==1){
scanf("%d",&t);
if(!a[t])
cout<<"No Elment!"<<endl;
else{
a[t]--;
modify(t,-1);
}
}
else if(sign==2){
scanf("%d %d",&m,&t);
num1=getsum(m)+t;
if(num1>getsum(max)){
cout<<"Not Find!"<<endl;
continue;
}
left=m+1;
right=max;
while(right-left>1){
md=getsum((right+left)/2);
if(md>num1){
right=(right+left)/2;
}
else if(md<num1){
left=(right+left)/2;
}
else {
if(a[(right+left)/2]){
cout<<(right+left)/2<<endl;
break;
}
else
right=(right+left)/2;
}
}
if(right-left<=1){
if(getsum(left)>=num1)
cout<<left<<endl;
else
cout<<right<<endl;
}
}
}
}
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;
}