给定如下操作：
0 s 初始化一个s*s的表格，全部置成0.
1 x y a 在表格 x y处加上数会上数值a ，a可正可负。
2 l b r t 询问区间内的数值和。
3 输入结束。
你的工作是根据给定的操作，输出对应的结果。
样例：
0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3
输出：
3
4
规模
s<=1024
操作总数小于等于32767.
a 小于等于32767
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cstdio> 7 #include <queue> 8 using namespace std ; 9 10 int n ; 11 int c[1100][1100] ; 12 13 14 inline void Init( ) { 15 freopen( "10346.in" , "r" , stdin ) ; 16 freopen( "10346.out" , "w" , stdout ) ; 17 } 18 19 int lowbit( int x ) { 20 return x & ( -x ) ; 21 } 22 23 24 void update( int x , int y , int add ) { 25 for( int i = x ; i <= n ; i += lowbit( i ) ) 26 for( int j = y ; j <= n ; j += lowbit( j ) ) { 27 c[i][j] += add ; 28 29 } 30 31 } 32 33 int sum ( int x , int y ) { 34 int tem = 0 ; 35 for( int i = x ; i > 0 ; i -= lowbit(i) ) 36 for( int j = y ; j > 0 ; j -= lowbit(j) ) { 37 tem += c[i][j] ; 38 } 39 40 return tem ; 41 } 42 43 44 int sov( int x1 , int y1 , int x2 , int y2 ) { 45 return sum( x1 - 1 , y1 - 1 ) + sum( x2 , y2 ) - sum( x1 - 1 , y2 ) - sum( x2 , y1 - 1 ) ; 46 } 47 48 49 void input( ) { 50 int a ; scanf( "%d%d" ,&a , &n ) ; 51 while ( 1 ) { 52 scanf( "%d" , &a ) ; 53 if( a == 1 ) { 54 int x , y , add ; 55 scanf( "%d%d%d" , &x , &y , &add ) ; 56 update( x + 1 , y + 1 , add ) ; 57 } 58 else if( a == 2 ) { 59 int x1 , y1 , x2 , y2 ; 60 scanf( "%d%d%d%d" , &x1 , &y1 , &x2 ,&y2 ) ; 61 cout<< sov( x1 + 1 , y1 + 1 , x2 + 1 , y2 + 1 ) <<endl ; 62 } 63 else break; 64 } 65 } 66 67 68 int main ( ) { 69 // Init( ) ; 70 input( ) ; 71 // sov( ) ; 72 // output( ) ; 73 // fclose(stdin); 74 // fclose(stdout); 75 return 0 ; 76 }
就是一个很裸的二维树状数组 。