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
sachit9_: 2020-02-04 16:02:33

getting tle after using int ,scanf,printf,fastio,BIT , plz someone help

urielguz33: 2020-01-17 03:55:09

Things to look out for:
You must only subtract 1 to the coordinates with 1 (eg: x1, y1). Cost me several WA
It says SET, not ADD. This one cost me half of the other several WA.

Last edit: 2020-01-17 03:57:08
s_anand98: 2019-09-05 08:57:53

Its giving TLE in JAVA using 2D segment tree. Doesn't SPOJ provide extra time for slow languages like JAVA?

knir0103: 2019-04-19 08:28:39

use scanf & printf instead :), if u got TLE in spite of your right algorithm

mahbubkuet08: 2019-03-15 18:40:47

Isn't it really possible to get AC using Segment tree in CPP? Is there anybody? Please share what you have done?

saurabhs_1206: 2019-01-22 19:13:53

in java, it is giving TLE using 2D BIT...please suggest what to do

Erick: 2019-01-05 11:05:45

Don't worry using int, every op in the problem fits in it.

tien0903: 2018-12-10 15:39:21

musn't use long if u want 2 AC :D use scanf and prinf is much faster

imkiller: 2018-06-07 17:00:00

1 hour But Finally Solved
Learn new Concept 2D BIT

Last edit: 2018-06-07 17:00:11
flyingduchman_: 2017-09-20 21:46:30

A nice 2D BIT problem, int works


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