{"id":"8af2baaf-9057-401b-b5ee-76d63db47a63","name":"Point Update In Square Root Decomposition","description":"You are given a list of N numbers and Q queries. There are two types of queries:\r\n\r\n1. f l r : In a line, the first character would be f, and 2 index l and r, you have to find the sum of numbers between l and r.\r\n2. u i d : In a line, the first character would be u, and we have to change the value at index i in the original array by d.","inputFormat":"The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain one of the 2 queries.","outputFormat":"Output the sum from l to r for type 1 query and update the value at index i for type 2 query.","constraints":"1 <= N <= 10^6\r\n1 <= Q <= 10^5\r\n1 <= arr[i] <= 10^9","sampleCode":{"cpp":{"code":""},"java":{"code":"\r\nimport java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\nimport java.util.Arrays;\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\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5\r\n1 5 3 9 -2\r\n3\r\nf 0 4\r\nu 2 3\r\nf 0 4","sampleOutput":"16\r\n19\r\n","questionVideo":"https://www.youtube.com/embed/yP48ylKOsA8","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":"09980edb-846f-4c16-9720-812d81e5ed58","name":"Point Update In Square Root Decomposition","slug":"point-update-in-square-root-decomposition","type":1}],"next":{"id":"fdd2de13-c7b3-4164-99ff-1ce1cf78529b","name":"Fenwick Tree","type":1,"slug":"fenwick-tree"},"prev":{"id":"8df650ba-ffc6-4622-b357-34779040e18e","name":"Square Root Decomposition","type":1,"slug":"square-root-decomposition"}}}

Point Update In Square Root Decomposition

You are given a list of N numbers and Q queries. There are two types of queries: 1. f l r : In a line, the first character would be f, and 2 index l and r, you have to find the sum of numbers between l and r. 2. u i d : In a line, the first character would be u, and we have to change the value at index i in the original array by d.

{"id":"8af2baaf-9057-401b-b5ee-76d63db47a63","name":"Point Update In Square Root Decomposition","description":"You are given a list of N numbers and Q queries. There are two types of queries:\r\n\r\n1. f l r : In a line, the first character would be f, and 2 index l and r, you have to find the sum of numbers between l and r.\r\n2. u i d : In a line, the first character would be u, and we have to change the value at index i in the original array by d.","inputFormat":"The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain one of the 2 queries.","outputFormat":"Output the sum from l to r for type 1 query and update the value at index i for type 2 query.","constraints":"1 <= N <= 10^6\r\n1 <= Q <= 10^5\r\n1 <= arr[i] <= 10^9","sampleCode":{"cpp":{"code":""},"java":{"code":"\r\nimport java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\nimport java.util.Arrays;\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\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5\r\n1 5 3 9 -2\r\n3\r\nf 0 4\r\nu 2 3\r\nf 0 4","sampleOutput":"16\r\n19\r\n","questionVideo":"https://www.youtube.com/embed/yP48ylKOsA8","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":"09980edb-846f-4c16-9720-812d81e5ed58","name":"Point Update In Square Root Decomposition","slug":"point-update-in-square-root-decomposition","type":1}],"next":{"id":"fdd2de13-c7b3-4164-99ff-1ce1cf78529b","name":"Fenwick Tree","type":1,"slug":"fenwick-tree"},"prev":{"id":"8df650ba-ffc6-4622-b357-34779040e18e","name":"Square Root Decomposition","type":1,"slug":"square-root-decomposition"}}}
plane

Editor


Loading...

Point Update In Square Root Decomposition

hard

You are given a list of N numbers and Q queries. There are two types of queries: 1. f l r : In a line, the first character would be f, and 2 index l and r, you have to find the sum of numbers between l and r. 2. u i d : In a line, the first character would be u, and we have to change the value at index i in the original array by d.

Constraints

1 <= N <= 10^6 1 <= Q <= 10^5 1 <= arr[i] <= 10^9

Format

Input

The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain one of the 2 queries.

Output

Output the sum from l to r for type 1 query and update the value at index i for type 2 query.

Example

Sample Input

5 1 5 3 9 -2 3 f 0 4 u 2 3 f 0 4

Sample Output

16 19

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode