{"id":"52eb742d-c1db-496a-898c-d2d5ac9a7f60","name":"Maximum Sum","description":"You are given an array(of integers) of length n.\r\nYou are required to answer q queries.\r\n\r\nQueries can be of two types :-\r\nUpdate\r\n0 idx val : set arr[idx] to val.\r\nQuery\r\n1 l r: find i,j such that l <= i < j <= r, such that arr[i]+arr[j] is maximized. return arr[i]+arr[j].","inputFormat":"A number n\r\nn1\r\nn2\r\n.. n number of elements\r\nA number q\r\nfollowing q lines contains queries of format either of two \r\n0 idx val\r\n1 l r","outputFormat":"for each query of type 1 print a single integer in seperate line","constraints":"1. 1 &lt;= n, q &lt;= 10^5\r\n2. 0 &lt;= l &lt; r &lt; n\r\n3. 0 &lt;= idx &lt; n\r\n4. 1 &lt;= arr[i], val &lt;= 10^4.\r\n","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"8\r\n2\r\n6\r\n1\r\n5\r\n4\r\n10\r\n10\r\n9\r\n5\r\n1 0 4\r\n0 0 10\r\n1 0 4\r\n1 0 7\r\n1 3 4\r\n","sampleOutput":"11\r\n16\r\n20\r\n9\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":"9031427d-cb38-4373-8193-f988b61bdeed","name":"Maximum Sum","slug":"maximum-sum","type":1}],"next":{"id":"ae20c9d9-8ab3-41f2-8b1e-72f4092fc46f","name":"Sum Of Squares","type":1,"slug":"sum-of-squares"},"prev":{"id":"049f89aa-c540-40f2-b90a-57097e32045c","name":"Sum Of Range - Range Query Range Update","type":1,"slug":"sum-of-range-range-query-range-update"}}}

Maximum Sum

You are given an array(of integers) of length n. You are required to answer q queries. Queries can be of two types :- Update 0 idx val : set arr[idx] to val. Query 1 l r: find i,j such that l <= i < j <= r, such that arr[i]+arr[j] is maximized. return arr[i]+arr[j].

{"id":"52eb742d-c1db-496a-898c-d2d5ac9a7f60","name":"Maximum Sum","description":"You are given an array(of integers) of length n.\r\nYou are required to answer q queries.\r\n\r\nQueries can be of two types :-\r\nUpdate\r\n0 idx val : set arr[idx] to val.\r\nQuery\r\n1 l r: find i,j such that l <= i < j <= r, such that arr[i]+arr[j] is maximized. return arr[i]+arr[j].","inputFormat":"A number n\r\nn1\r\nn2\r\n.. n number of elements\r\nA number q\r\nfollowing q lines contains queries of format either of two \r\n0 idx val\r\n1 l r","outputFormat":"for each query of type 1 print a single integer in seperate line","constraints":"1. 1 &lt;= n, q &lt;= 10^5\r\n2. 0 &lt;= l &lt; r &lt; n\r\n3. 0 &lt;= idx &lt; n\r\n4. 1 &lt;= arr[i], val &lt;= 10^4.\r\n","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"8\r\n2\r\n6\r\n1\r\n5\r\n4\r\n10\r\n10\r\n9\r\n5\r\n1 0 4\r\n0 0 10\r\n1 0 4\r\n1 0 7\r\n1 3 4\r\n","sampleOutput":"11\r\n16\r\n20\r\n9\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":"9031427d-cb38-4373-8193-f988b61bdeed","name":"Maximum Sum","slug":"maximum-sum","type":1}],"next":{"id":"ae20c9d9-8ab3-41f2-8b1e-72f4092fc46f","name":"Sum Of Squares","type":1,"slug":"sum-of-squares"},"prev":{"id":"049f89aa-c540-40f2-b90a-57097e32045c","name":"Sum Of Range - Range Query Range Update","type":1,"slug":"sum-of-range-range-query-range-update"}}}
plane

Editor

Loading...

Maximum Sum

medium

You are given an array(of integers) of length n. You are required to answer q queries. Queries can be of two types :- Update 0 idx val : set arr[idx] to val. Query 1 l r: find i,j such that l

Constraints

1. 1 <= n, q <= 10^5 2. 0 <= l < r < n 3. 0 <= idx < n 4. 1 <= arr[i], val <= 10^4.

Format

Input

A number n n1 n2 .. n number of elements A number q following q lines contains queries of format either of two 0 idx val 1 l r

Output

for each query of type 1 print a single integer in seperate line

Example

Sample Input

8 2 6 1 5 4 10 10 9 5 1 0 4 0 0 10 1 0 4 1 0 7 1 3 4

Sample Output

11 16 20 9

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode