{"id":"d06104d0-857b-406f-99a5-5085505fb101","name":"2d Segment Tree","description":"Mr. Pepcoder has a 2D Array, and his Friend love to do operations on thearray. The operations can be a query or an update.\r\n\r\nFor 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.\r\n\r\nWhen 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 ).\r\n\r\nBecause indexing the array from zero is too obscure for friend, all indices start from 1.","inputFormat":"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.\r\nQuery operations are of the form \"q x1 y1 x2 y2\", while update operations are of the form \"u x1 x2 x\".","outputFormat":"You have to print the answer for every query in a different line, in the same order of the input.","constraints":"1 &lt;= n,m &lt;= 10^3\r\n1 &lt;= Q &lt;= 10^5\r\n1 &lt;= x1,y1,x2,y2 &lt;= N\r\n-10^9 &lt;= arr[i] &lt;= 10^9","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws IOException {\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"3 3\r\n1 2 3 \r\n4 5 6\r\n7 8 9\r\n5\r\nq 1 1 2 2\r\nq 1 2 3 3\r\nq 2 1 3 2\r\nu 1 1 1\r\nq 1 1 2 2\r\n","sampleOutput":"12\r\n33\r\n24\r\n13\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9b3d7d76-b2ca-458f-80a8-4b37d548024a","name":"Segment Tree For Experts","slug":"segment-tree-for-experts-953","type":0},{"id":"5eccc617-64f0-4ca6-8282-6acb4e1c5160","name":"2d Segment Tree","slug":"2d-segment-tree","type":1}],"next":{"id":"9167f274-6395-4fa1-b521-a700d2d14ff1","name":"Toggle Bulbs","type":1,"slug":"toggle-bulbs"},"prev":{"id":"ae20c9d9-8ab3-41f2-8b1e-72f4092fc46f","name":"Sum Of Squares","type":1,"slug":"sum-of-squares"}}}

2d Segment Tree

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.

{"id":"d06104d0-857b-406f-99a5-5085505fb101","name":"2d Segment Tree","description":"Mr. Pepcoder has a 2D Array, and his Friend love to do operations on thearray. The operations can be a query or an update.\r\n\r\nFor 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.\r\n\r\nWhen 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 ).\r\n\r\nBecause indexing the array from zero is too obscure for friend, all indices start from 1.","inputFormat":"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.\r\nQuery operations are of the form \"q x1 y1 x2 y2\", while update operations are of the form \"u x1 x2 x\".","outputFormat":"You have to print the answer for every query in a different line, in the same order of the input.","constraints":"1 &lt;= n,m &lt;= 10^3\r\n1 &lt;= Q &lt;= 10^5\r\n1 &lt;= x1,y1,x2,y2 &lt;= N\r\n-10^9 &lt;= arr[i] &lt;= 10^9","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws IOException {\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"3 3\r\n1 2 3 \r\n4 5 6\r\n7 8 9\r\n5\r\nq 1 1 2 2\r\nq 1 2 3 3\r\nq 2 1 3 2\r\nu 1 1 1\r\nq 1 1 2 2\r\n","sampleOutput":"12\r\n33\r\n24\r\n13\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9b3d7d76-b2ca-458f-80a8-4b37d548024a","name":"Segment Tree For Experts","slug":"segment-tree-for-experts-953","type":0},{"id":"5eccc617-64f0-4ca6-8282-6acb4e1c5160","name":"2d Segment Tree","slug":"2d-segment-tree","type":1}],"next":{"id":"9167f274-6395-4fa1-b521-a700d2d14ff1","name":"Toggle Bulbs","type":1,"slug":"toggle-bulbs"},"prev":{"id":"ae20c9d9-8ab3-41f2-8b1e-72f4092fc46f","name":"Sum Of Squares","type":1,"slug":"sum-of-squares"}}}

Editor

2d Segment Tree

hard

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.

Constraints

1 <= n,m <= 10^3 1 <= Q <= 10^5 1 <= x1,y1,x2,y2 <= N -10^9 <= arr[i] <= 10^9

Format

Input

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

You have to print the answer for every query in a different line, in the same order of the input.

Example

Sample Input

.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}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

.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}12 33 24 13 

Discussions

Show Discussion

Related Resources