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 32-bit 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
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.
|
|
dil_shad22:
2022-10-04 22:52:56
Thanks @arunjain9988 !
|
|
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
|
|
nemesys:
2020-08-19 22:08:29
Iterative 2D segment tree passed without problems.
|
|
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 |