MATSUM  Matrix Summation
A N × N matrix is filled with numbers. BuggyD is analyzing the matrix, and he wants the sum of certain submatrices every now and then, so he wants a system where he can get his results from a query. Also, the matrix is dynamic, and the value of any cell can be changed with a command in such a system.
Assume that initially, all the cells of the matrix are filled with 0. Design such a system for BuggyD. Read the input format for further details.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
The first line of each test case contains a single integer N (1 <= N <= 1024), denoting the size of the matrix.
A list of commands follows, which will be in one of the following three formats (quotes are for clarity):
 "SET x y num"  Set the value at cell (x, y) to num (0 <= x, y < N).
 "SUM x1 y1 x2 y2"  Find and print the sum of the values in the rectangle from (x1, y1) to (x2, y2), inclusive. You may assume that x1 <= x2 and y1 <= y2, and that the result will fit in a signed 32bit integer.
 "END"  Indicates the end of the test case.
Output
For each test case, output one line for the answer to each "SUM" command. Print a blank line after each test case.
Example
Input: 1 4 SET 0 0 1 SUM 0 0 3 3 SET 2 2 12 SUM 2 2 2 2 SUM 2 2 3 3 SUM 0 0 2 2 END Output: 1 12 12 13
hide comments
7Bubble:
20150830 09:20:37
rang.. U confused me. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150728 22:08:10
[!] there are negative numbers on input :o 

Whatever:
20150611 13:43:36
Use int , long long gave me WA 

Rang:
20150602 20:22:38
its SET not update ! 

Rajat De:
20150310 11:12:04
Beware , the numbers can be negative too. costed me several WAs 

UJtriumphsâ„¢:
20150123 11:30:04
Hard to get AC!! Nice intial 2D BIT 

Mahesh Mishra:
20150105 20:47:42
1. "Print a blank line after each test case".


Archit Jain:
20141220 13:43:47
long long giving tle 

Divyank Duvedi:
20141201 20:49:02
It is very hard to get it AC using 2D segTrees (QuadTrees) 

Anant Kumar:
20141013 22:01:00
A blank line after after every test case. Seriously!

Added by:  Matthew Reeder 
Date:  20061029 
Time limit:  1.029s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  AlKhawarizm 2006 