{"id":"a16ee1a3-d33b-4da0-a36f-8e134b1fba64","name":"2d Binary Indexed 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 <= n,m <= 10^3\r\n1 <= Q <= 10^5\r\n1 <= x1,y1,x2,y2 <= N\r\n-10^9 <= arr[i] <= 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\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\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\n3\r\nq 1 1 2 2\r\nq 1 2 3 3\r\nq 2 1 3 2","sampleOutput":"12\r\n33\r\n24\r\n","questionVideo":"https://www.youtube.com/embed/74tokuW415A","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":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"cd4ad84c-95ed-49ea-a5b5-25ed0d9bbd4b","name":"2d Binary Indexed Tree","slug":"2d-binary-indexed-tree","type":1}],"next":{"id":"179d9606-6fc5-4e3a-935e-46a5c0060175","name":"Create Sorted Array Through Instructions","type":1,"slug":"create-sorted-array-through-instructions"},"prev":{"id":"fdd2de13-c7b3-4164-99ff-1ce1cf78529b","name":"Fenwick Tree","type":1,"slug":"fenwick-tree"}}}

2d Binary Indexed 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":"a16ee1a3-d33b-4da0-a36f-8e134b1fba64","name":"2d Binary Indexed 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 <= n,m <= 10^3\r\n1 <= Q <= 10^5\r\n1 <= x1,y1,x2,y2 <= N\r\n-10^9 <= arr[i] <= 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\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\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\n3\r\nq 1 1 2 2\r\nq 1 2 3 3\r\nq 2 1 3 2","sampleOutput":"12\r\n33\r\n24\r\n","questionVideo":"https://www.youtube.com/embed/74tokuW415A","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":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"cd4ad84c-95ed-49ea-a5b5-25ed0d9bbd4b","name":"2d Binary Indexed Tree","slug":"2d-binary-indexed-tree","type":1}],"next":{"id":"179d9606-6fc5-4e3a-935e-46a5c0060175","name":"Create Sorted Array Through Instructions","type":1,"slug":"create-sorted-array-through-instructions"},"prev":{"id":"fdd2de13-c7b3-4164-99ff-1ce1cf78529b","name":"Fenwick Tree","type":1,"slug":"fenwick-tree"}}}
plane

Editor


Loading...

2d Binary Indexed 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

3 3 1 2 3 4 5 6 7 8 9 3 q 1 1 2 2 q 1 2 3 3 q 2 1 3 2

Sample Output

12 33 24

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode