Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

50题留念 也是第一个二维的树状数组 希望自己继续努力哦

Posted by 20081727 at 2010-06-16 11:09:37 on Problem 1195
#include<iostream>

using namespace std;
const int M = 1024;

int m[M + 10][M + 10];

inline int lowbit(int x)
{
	return(x & (-x));
}

void update(int x,int y,int val)
{
	for(int i = x; i <= M; i += lowbit(i))
	{
		 for(int j = y; j <= M; j += lowbit(j))
		 {
			  m[i][j] += val;
		 }
	}
}


int sum(int x,int y)
{
	int i,j,s = 0;
	for(i = x; i > 0; i -= lowbit(i))
	{
	    for(j = y; j > 0; j -=lowbit(j))
		{
			s += m[i][j];
		}
	}
    return(s);	
}

int getsum(int x1,int y1,int x2,int y2)
{
    return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
}

int main()
{
	 int flag,x,y,a,t;
	 scanf("%d%d",&x,&y);      //矩阵大小
	 memset(m,0,sizeof(m));
	 
	 while(scanf("%d",&flag) && flag != 3)
	 {
	      if(flag == 1)
		  {
			   scanf("%d%d%d",&x,&y,&a);
			   update(x + 1,y + 1,a);
		  }
		  else
		  {
			   scanf("%d%d%d%d",&x,&y,&a,&t);   // (a,t) --> (x,y)
			   printf("%d\n",getsum(x + 1,y + 1,a + 1, t + 1));
		  }
   
		  

		  
	 }
	 return(0);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator