Redirecting to
NADOS

2d Segment Tree

  Prev   Next 
Mr. Pepcoder has a 2D Array, and his Friend love to do operations on thearray. The operations can be a query or an update.

For each query the Friend say four indices x1, y1, x2 and y2, and their father answers back with the sum of the elements of the rectangle whose top left index is x1, y1 and bottom right is x2, y2.

When there is an update, the friend says index (x1,y1) and a value x , and Pepcoder will add x to arr[x1][y1] (so the new value of arr[x1][y1]  is arr[x1][y1] + x ).

Because indexing the array from zero is too obscure for friend, all indices start from 1.
Input Format 
The first line of the input contains n and m. The next n lines contain m integers each, the initial values of the array.Next line contains Q, the number of operations that will be made. Each of the next Q lines contains an operation.
Query operations are of the form "q x1 y1 x2 y2", while update operations are of the form "u x1 x2 x".
Output Format 
You have to print the answer for every query in a different line, in the same order of the input.
Question Video
Constraints 
1 <= n,m <= 10^3
1 <= Q <= 10^5
1 <= x1,y1,x2,y2 <= N
-10^9 <= arr[i] <= 10^9
Sample Input 
3 3
1 2 3 
4 5 6
7 8 9
5
q 1 1 2 2
q 1 2 3 3
q 2 1 3 2
u 1 1 1
q 1 1 2 2
Sample Output 
12
33
24
13


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name