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.

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

  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.

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
Warning: large Input/Output data, be careful with certain languages

hide comments
miamimagna: 2024-10-30 06:55:18

@manuver thanks man you're great

anuragkanwar: 2023-10-03 14:54:37

Guys please always use that algorithm which is faster and easier to code.

You beautiful, BIT...

1. I used BIT (easier to code)
2. I have used C++ cin
3. I have used C++ string
4. I have used "\n" instead of endl
5. I have used
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

Accepted...

dil_shad22: 2022-10-04 22:52:56

Thanks @arunjain9988 !
We are learning from your learnings.

hv22: 2022-08-03 19:05:59

good problem to learn 2d BIT

minhnguyent546: 2022-05-13 16:21:07

SET not add :))). Caution !

amisin3: 2021-07-07 20:53:26

Getting TLE even the algorithm is running for O(nlogn). Used Fenwick Trees

arunjain9988: 2021-03-13 11:35:00

Learned:- never use endl :)

manuver: 2020-10-19 09:13:00

things to keep in mind
1. set the new values (don't add to previous)
2. use below for c++ optimization
ios::sync_with_stdio(false);
cin.tie(0);
3. don't use cin for string input. don't use c++ string class. use char array. (cost me 5 + WA)
4. no need to print blank Line after test case. just print the sum with new Line appended.
5. I used Fenwick a.k.a Binary Indexed Tree.
6. don't give up

nemesys: 2020-08-19 22:08:29

Iterative 2D segment tree passed without problems.

EDIT: actually it passed with 0.9s, so the time limit is very tight! After a few optimizations, it passed with 0.71s.

Last edit: 2020-08-20 14:10:57
pareksha: 2020-04-29 12:59:42

No matter how much optimisation is done, 2-D segment tree isn't working. Time Limit is too strict for it.


Added by:Matthew Reeder
Date:2006-10-29
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