MATSUM - Matrix Summation

no tags 

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.


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):

  1. "SET x y num" - Set the value at cell (x, y) to num (0 <= x, y < N).
  2. "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 32-bit integer.
  3. "END" - Indicates the end of the test case.


For each test case, output one line for the answer to each "SUM" command. Print a blank line after each test case.


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

Warning: large Input/Output data, be careful with certain languages

hide comments
Kraken: 2015-09-12 21:18:06

using n log log get tle , Lol

7Bubble: 2015-08-30 09:20:37

rang.. U confused me.

(Tjandra Satria Gunawan)(曾毅昆): 2015-07-28 22:08:10

[!] there are negative numbers on input :-o

Whatever: 2015-06-11 13:43:36

Use int , long long gave me WA

Rang: 2015-06-02 20:22:38

its SET not update !

Rajat De: 2015-03-10 11:12:04

Beware , the numbers can be negative too. costed me several WAs

UJtriumphsâ„¢: 2015-01-23 11:30:04

Hard to get AC!! Nice intial 2-D BIT

Mahesh Mishra: 2015-01-05 20:47:42

1. "Print a blank line after each test case".
2. Very difficult to get AC by 2D segment tree.

Archit Jain: 2014-12-20 13:43:47

long long giving tle

Divyank Duvedi: 2014-12-01 20:49:02

It is very hard to get it AC using 2D segTrees (QuadTrees)

Added by:Matthew Reeder
Time limit:1.029s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006