{"id":"e23e9c37-3462-4c7c-a22d-c18643a35527","name":"Max In A Interval - Range Query Point Update","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\n0. 0 pos val : In this you have to update arr[pos] to val.\r\n1. 1 l r: In this query u have to find the max among all elements in this interval.\r\n\r\n\r\nTo do the above task u have to create a datastructure as follows :-\r\n\r\nImplement the SegmentTree class:\r\n1. SegmentTree(int arr[]): Initializes the SegmentTree object with an array,\r\n2. void update(int pos, int val): updates the arr[pos] to val,\r\n3. int query(int l, int r): return max of all element's in interval [l, r].\r\n\r\nCan u do it in O(log(n)) or better Time Complexity.","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 pos val,\r\n1 l r","outputFormat":"for each query 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. 10^9 &lt;= arr[i] &lt;= 10^9\r\n4. all input and output will fit in 32bit signed integer","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static class SegmentTree {\r\n\r\n SegmentTree(int arr[]) {\r\n\r\n }\r\n\r\n void update(int pos, int val) {\r\n\r\n }\r\n\r\n int query(int l, int r) {\r\n\r\n }\r\n\r\n }\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 int n = Integer.parseInt(read.readLine());\r\n int arr[] = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(read.readLine());\r\n }\r\n\r\n SegmentTree obj = new SegmentTree(arr);\r\n\r\n int q = Integer.parseInt(read.readLine());\r\n\r\n StringBuilder out = new StringBuilder();\r\n while (q-- > 0) {\r\n String[]inp = read.readLine().split(\" \");\r\n\r\n int t = Integer.parseInt(inp[0]);\r\n int l = Integer.parseInt(inp[1]);\r\n int r = Integer.parseInt(inp[2]);\r\n\r\n if (t == 0) {\r\n obj.update(l, r);\r\n } else {\r\n int ans = obj.query(l, r);\r\n out.append(ans);\r\n out.append(\"\\n\");\r\n }\r\n }\r\n\r\n System.out.println(out);\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"4\r\n1\r\n2\r\n3\r\n4\r\n10\r\n1 0 3\r\n0 1 3\r\n1 0 3\r\n1 1 2\r\n0 2 5\r\n1 2 2\r\n1 2 3\r\n1 0 1\r\n1 0 2\r\n1 1 3\r\n","sampleOutput":"4\r\n4\r\n3\r\n5\r\n5\r\n3\r\n5\r\n5\r\n\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":"5c055372-d5a6-4fce-ba24-91184cb9ac98","name":"Max In A Interval - Range Query Point Update","slug":"max-in-a-interval-range-query-point-update","type":1}],"next":{"id":"059f9009-7e44-4ad2-9a06-fd536d21bea1","name":"What's At Idx - Point Query Range Update","type":1,"slug":"what-s-at-idx-point-query-range-update"},"prev":{"id":"1761e131-94fb-4631-8e27-e7bf0e70621a","name":"Sum Of Interval","type":1,"slug":"sum-of-interval"}}}

Max In A Interval - Range Query Point Update

You are given an array(of integers) of length n. You are required to answer q queries. Queries can be of two types 0. 0 pos val : In this you have to update arr[pos] to val. 1. 1 l r: In this query u have to find the max among all elements in this interval. To do the above task u have to create a datastructure as follows :- Implement the SegmentTree class: 1. SegmentTree(int arr[]): Initializes the SegmentTree object with an array, 2. void update(int pos, int val): updates the arr[pos] to val, 3. int query(int l, int r): return max of all element's in interval [l, r]. Can u do it in O(log(n)) or better Time Complexity.

{"id":"e23e9c37-3462-4c7c-a22d-c18643a35527","name":"Max In A Interval - Range Query Point Update","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\n0. 0 pos val : In this you have to update arr[pos] to val.\r\n1. 1 l r: In this query u have to find the max among all elements in this interval.\r\n\r\n\r\nTo do the above task u have to create a datastructure as follows :-\r\n\r\nImplement the SegmentTree class:\r\n1. SegmentTree(int arr[]): Initializes the SegmentTree object with an array,\r\n2. void update(int pos, int val): updates the arr[pos] to val,\r\n3. int query(int l, int r): return max of all element's in interval [l, r].\r\n\r\nCan u do it in O(log(n)) or better Time Complexity.","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 pos val,\r\n1 l r","outputFormat":"for each query 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. 10^9 &lt;= arr[i] &lt;= 10^9\r\n4. all input and output will fit in 32bit signed integer","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static class SegmentTree {\r\n\r\n SegmentTree(int arr[]) {\r\n\r\n }\r\n\r\n void update(int pos, int val) {\r\n\r\n }\r\n\r\n int query(int l, int r) {\r\n\r\n }\r\n\r\n }\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 int n = Integer.parseInt(read.readLine());\r\n int arr[] = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(read.readLine());\r\n }\r\n\r\n SegmentTree obj = new SegmentTree(arr);\r\n\r\n int q = Integer.parseInt(read.readLine());\r\n\r\n StringBuilder out = new StringBuilder();\r\n while (q-- > 0) {\r\n String[]inp = read.readLine().split(\" \");\r\n\r\n int t = Integer.parseInt(inp[0]);\r\n int l = Integer.parseInt(inp[1]);\r\n int r = Integer.parseInt(inp[2]);\r\n\r\n if (t == 0) {\r\n obj.update(l, r);\r\n } else {\r\n int ans = obj.query(l, r);\r\n out.append(ans);\r\n out.append(\"\\n\");\r\n }\r\n }\r\n\r\n System.out.println(out);\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"4\r\n1\r\n2\r\n3\r\n4\r\n10\r\n1 0 3\r\n0 1 3\r\n1 0 3\r\n1 1 2\r\n0 2 5\r\n1 2 2\r\n1 2 3\r\n1 0 1\r\n1 0 2\r\n1 1 3\r\n","sampleOutput":"4\r\n4\r\n3\r\n5\r\n5\r\n3\r\n5\r\n5\r\n\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":"5c055372-d5a6-4fce-ba24-91184cb9ac98","name":"Max In A Interval - Range Query Point Update","slug":"max-in-a-interval-range-query-point-update","type":1}],"next":{"id":"059f9009-7e44-4ad2-9a06-fd536d21bea1","name":"What's At Idx - Point Query Range Update","type":1,"slug":"what-s-at-idx-point-query-range-update"},"prev":{"id":"1761e131-94fb-4631-8e27-e7bf0e70621a","name":"Sum Of Interval","type":1,"slug":"sum-of-interval"}}}
plane

Editor

Loading...

Max In A Interval - Range Query Point Update

medium

You are given an array(of integers) of length n. You are required to answer q queries. Queries can be of two types 0. 0 pos val : In this you have to update arr[pos] to val. 1. 1 l r: In this query u have to find the max among all elements in this interval. To do the above task u have to create a datastructure as follows :- Implement the SegmentTree class: 1. SegmentTree(int arr[]): Initializes the SegmentTree object with an array, 2. void update(int pos, int val): updates the arr[pos] to val, 3. int query(int l, int r): return max of all element's in interval [l, r]. Can u do it in O(log(n)) or better Time Complexity.

Constraints

1. 1 <= n, q <= 10^5 2. 0 <= l <= r < n 3. 10^9 <= arr[i] <= 10^9 4. all input and output will fit in 32bit signed integer

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 pos val, 1 l r

Output

for each query print a single integer in seperate line

Example

Sample Input

4 1 2 3 4 10 1 0 3 0 1 3 1 0 3 1 1 2 0 2 5 1 2 2 1 2 3 1 0 1 1 0 2 1 1 3

Sample Output

4 4 3 5 5 3 5 5

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode