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