{"id":"9948ec9f-e579-4538-9814-402bb9d56d57","name":"Fenwick Tree","description":"Mr. Pepcoder has an array A, and his Friend love to do operations on the\r\narray. The operations can be a query or an update.\r\n\r\nFor each query the Friend say two indices l and r , and their father answers back with the sum\r\nof the elements from indices l to r (both included).\r\n\r\nWhen there is an update, the friend says an index i and a value x , and Pepcoder will add x to\r\nith index of array (so the new value of arr[i] is arr[i] + x ).\r\n\r\nBecause indexing the array from zero is too obscure for children, all indices start from 1.\r\n","inputFormat":"The first line of the input contains N. The second line contains N integers, the initial values of the array. The third 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 l r ) , while update operations are of the form (u i 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 <= 10^6\r\n1 <= Q <= 10^5\r\n1 <= l,r,i <= N\r\n-10^9 <= arr[i] <= 10^9\r\n","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":"10\r\n1 23 4 10 24 33 -1 -9 7 4\r\n6\r\nq 2 5\r\nq 1 9\r\nu 3 -2\r\nq 4 5\r\nu 6 10\r\nq 4 9","sampleOutput":"61\r\n92\r\n34\r\n74\r\n\r\n","questionVideo":"https://www.youtube.com/embed/pTg7NezkV28","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":"fdd2de13-c7b3-4164-99ff-1ce1cf78529b","name":"Fenwick Tree","slug":"fenwick-tree","type":1}],"next":{"id":"cd4ad84c-95ed-49ea-a5b5-25ed0d9bbd4b","name":"2d Binary Indexed Tree","type":1,"slug":"2d-binary-indexed-tree"},"prev":{"id":"09980edb-846f-4c16-9720-812d81e5ed58","name":"Point Update In Square Root Decomposition","type":1,"slug":"point-update-in-square-root-decomposition"}}}

Fenwick Tree

Mr. Pepcoder has an array A, and his Friend love to do operations on the array. The operations can be a query or an update. For each query the Friend say two indices l and r , and their father answers back with the sum of the elements from indices l to r (both included). When there is an update, the friend says an index i and a value x , and Pepcoder will add x to ith index of array (so the new value of arr[i] is arr[i] + x ). Because indexing the array from zero is too obscure for children, all indices start from 1.

{"id":"9948ec9f-e579-4538-9814-402bb9d56d57","name":"Fenwick Tree","description":"Mr. Pepcoder has an array A, and his Friend love to do operations on the\r\narray. The operations can be a query or an update.\r\n\r\nFor each query the Friend say two indices l and r , and their father answers back with the sum\r\nof the elements from indices l to r (both included).\r\n\r\nWhen there is an update, the friend says an index i and a value x , and Pepcoder will add x to\r\nith index of array (so the new value of arr[i] is arr[i] + x ).\r\n\r\nBecause indexing the array from zero is too obscure for children, all indices start from 1.\r\n","inputFormat":"The first line of the input contains N. The second line contains N integers, the initial values of the array. The third 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 l r ) , while update operations are of the form (u i 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 <= 10^6\r\n1 <= Q <= 10^5\r\n1 <= l,r,i <= N\r\n-10^9 <= arr[i] <= 10^9\r\n","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":"10\r\n1 23 4 10 24 33 -1 -9 7 4\r\n6\r\nq 2 5\r\nq 1 9\r\nu 3 -2\r\nq 4 5\r\nu 6 10\r\nq 4 9","sampleOutput":"61\r\n92\r\n34\r\n74\r\n\r\n","questionVideo":"https://www.youtube.com/embed/pTg7NezkV28","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":"fdd2de13-c7b3-4164-99ff-1ce1cf78529b","name":"Fenwick Tree","slug":"fenwick-tree","type":1}],"next":{"id":"cd4ad84c-95ed-49ea-a5b5-25ed0d9bbd4b","name":"2d Binary Indexed Tree","type":1,"slug":"2d-binary-indexed-tree"},"prev":{"id":"09980edb-846f-4c16-9720-812d81e5ed58","name":"Point Update In Square Root Decomposition","type":1,"slug":"point-update-in-square-root-decomposition"}}}
plane

Editor


Loading...

Fenwick Tree

hard

Mr. Pepcoder has an array A, and his Friend love to do operations on the array. The operations can be a query or an update. For each query the Friend say two indices l and r , and their father answers back with the sum of the elements from indices l to r (both included). When there is an update, the friend says an index i and a value x , and Pepcoder will add x to ith index of array (so the new value of arr[i] is arr[i] + x ). Because indexing the array from zero is too obscure for children, all indices start from 1.

Constraints

1 <= N <= 10^6 1 <= Q <= 10^5 1 <= l,r,i <= N -10^9 <= arr[i] <= 10^9

Format

Input

The first line of the input contains N. The second line contains N integers, the initial values of the array. The third 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 l r ) , while update operations are of the form (u i 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

10 1 23 4 10 24 33 -1 -9 7 4 6 q 2 5 q 1 9 u 3 -2 q 4 5 u 6 10 q 4 9

Sample Output

61 92 34 74

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode