I tried to solve the problem range minimum query in hacker earth Range Minimum Query | Practice Problems First test case is passing but second is not passing. There is a logic mistake in my code but I am unable to debug it kindly please help.
Question
Problem
Given an array A of size N, there are two types of queries on this array.
- qlr: In this query you need to print the minimum in the sub-array A[l:r].
- uxy: In this query you need to update A[x]=y.
Input:
First line of the test case contains two integers, N and Q, size of array A and number of queries.
Second line contains N space separated integers, elements of A.
Next Q lines contain one of the two queries.
Output:
For each type 1 query, print the minimum element in the sub-array A[l:r].
Contraints:
1≤N,Q,y≤105
1≤l,r,x≤N
Sample Input
5 5
1 5 2 4 3
q 1 5
q 1 3
q 3 5
u 3 6
q 1 5
Sample Output
1
1
2
1
def segment_build(a,s,e,tree,index):
if (s==e):
tree[index]=a[s]
return
mid=(s+e)//2
segment_build(a,s,mid,tree,2*index)
segment_build(a,mid+1,e,tree,2*index+1)
tree[index]=min(tree[2*index],tree[2*index+1])
return
def query(tree,s,e,range1,range2,index):
if s>=range1 and range2>=e:
return tree[index]
if range2<s or range1>e:
return 99999999999
mid=(s+e)//2
leftside=query(tree,s,mid,range1,range2,2*index)
rightside=query(tree,mid+1,e,range1,range2,2*index+1)
return min(leftside,rightside)
def update_oneindex(tree,s,e,givenindex,assign,index):
if(givenindex>e or givenindex<s):
return
if(s==e):
tree[index]=assign
return
else:
mid=(s+e)//2
update_oneindex(tree,s,mid,givenindex,assign,2*index)
update_oneindex(tree,mid+1,e,givenindex,assign,2*index+1)
tree[index]=min(tree[2*index],tree[2*index+1])
n,t=map(int,input().split())
a=[int(x) for x in input().split()]
tree=[0]*(4*n+1)
segment_build(a,0,n-1,tree,1)
for _ in range(t):
no,range1,range2=input().split()
range1,range2=int(range1),int(range2)
if no=='q':
print(query(tree,0,n-1,range1-1,range2-1,1))
else:
update_oneindex(tree,0,n-1,range1-1,range2-1,1)