An array A is given to you containing N integers. You need to operate Q queries on the array. Queries are of two types.
1 U P: You need to update value of Au to P.
2 L R P: You need to find Ak such that Ak - P is minimum and Ak > P and L<=k<=R
Input Format:
First Line of input contains a single integer N. Next line contains N space-separated integers, elements of array A.
Next line of input contains a single inter Q.
Q lines follow each containing a query as per described in statement.
Output Format:
For query of type 2,you need to print the value of Ak.if there is no such K print -1.Print answer for each query in new line.
Example Input: Example Output:
5 2
3 2 1 1 5 -1
3
2 1 5 1
1 4 4
2 1 4 5
Explanation: For first query in the range [1,5] and P=1, the required Ak is 2.
I am thinking of a segment tree solution with O(log(N)) for query type 2.But not able to figure out how to do.
Let's consider the above example and build our algorithm on top of it.
So our Input looks like this:-
Example Input: Example Output:
5 2
3 2 1 1 5 -1
3
2 1 5 1
1 4 4
2 1 4 5
Now I am building a Segment tree that keeps two values at each node of (min, max) , the min corresponds to the minimum value in that range and max value corresponds to the maximum value in that range.
Now our segment tree after running the build method for the above example will look something like this:-
[0:4] (1,5)
/ \
/ \
[0:2] (1,3) [3:4] (1,5)
/ \ / \
/ \ / \
[0:1] (2,3) [2:2](1,1) [3:3](1,1) [4:4](5,5)
/ \
/ \
[0:0](3,3) [1:1](2,2)
So you can see in the above segment tree, how at each level, each node consists of pair of (min, max) in that interval.
Now let's look at our update query in terms of pseudocode. It's pretty straightforward.
void update(int node, int start, int end, int idx, int val)
{
if(start == end)
{
// Leaf node
A[idx] = val;
tree[node] = val;
}
else
{
int mid = (start + end) / 2;
if(start <= idx and idx <= mid)
{
// If idx is in the left child, recurse on the left child
update(2*node, start, mid, idx, val);
}
else
{
// if idx is in the right child, recurse on the right child
update(2*node+1, mid+1, end, idx, val);
}
// Internal node will have the min and max of both of its children
tree[node] = pair(min(tree[2*node].min, tree[2*node+1].min), max(tree[2*node].max, tree[2*node+1].max);
}
}
Update is pretty clear, we just have to reach the leaf value and update the value at that index and then recursing back to top, we will keep updating our other nodes with min and max values.
Time complexity of update query is O(logn).
Now let's take a look at our main component of the problem i.e query part of the problem.
So our query part of the code will look something like this:-
// P here is the value for which our Ak > P and Ak - P shoudl be minimum
// l and r is our range provided in the input for each query
int query(int node, int start, int end, int l, int r, int P)
{
// If the maximum element at this particular node of the tree is less than P,
// then there is no point in going down as we need to find the element which is greater than P.
if(tree[node].max < P)
{
return -1;
}
if(r < start or end < l)
{
// range represented by a node is completely outside the given range
return -1;
}
if(l<=start and end <= r and start==end) {
return tree[node] - P;
}
// range represented by a node is partially inside and partially outside the given range
int mid = (start + end) / 2;
int p1 = query(2*node, start, mid, l, r);
int p2 = query(2*node+1, mid+1, end, l, r);
return min(p1 + p2);
}
I have added as many comments, I can in the pseudo code, Please have a look and let me know, if I am making any mistakes.
Hope this helps!