POJ 1195(Mobile phones)简单二维树状数组

spoiler posted @ 2011年4月11日 16:39 in 树状数组经典题目 , 1216 阅读

题目大意:给定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;

}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter