Max In An Interval - Range Query
You are given an array(of integers) of length n. You are required to answer q queries. In each query u are given an interval l, r both inclusive and u have to find the maximum element 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. int query(int l, int r): return max in interval [l, r]. Can u do it in O(log(n)) or better Time Complexity.
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
A number n n1 n2 .. n number of elements A number q following q lines contains queries of format l r
for each query print a single integer in seperate line
8 8 7 4 2 5 3 1 10 4 0 7 0 3 2 7 1 6
10 8 10 7