| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
50题留念 也是第一个二维的树状数组 希望自己继续努力哦#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator