Segment Tree Range Minimum (OOP)
Programming Interview
Hard
8 views
Problem Description
You get {x}. Build SegmentTree class with update(i,x) and query(l,r) returning minimum. Output query answers.
Input Format
First line n q. Second line n integers. Next q lines: 1 i x (update) or 2 l r (min).
Output Format
Outputs for type 2.
Sample Test Case
Input:
5 5
5 2 7 3 9
2 2 4
1 3 1
2 1 3
1 5 0
2 4 5
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
it=iter(p)
n=int(next(it)); q=int(next(it))
a=[int(next(it)) for _ in range(n)]
INF=10**30
class SegmentTree:
def __init__(self,arr):
self.n=len(arr)
size=1
while size<self.n:
size*=2
self.size=size
self.seg=[INF]*(2*size)
for i,v in enumerate(arr):
self.seg[size+i]=v
for i in range(size-1,0,-1):
self.seg[i]=self.seg[2*i] if self.seg[2*i]<self.seg[2*i+1] else self.seg[2*i+1]
def update(self,idx,val):
pos=self.size+(idx-1)
self.seg[pos]=val
pos//=2
while pos:
self.seg[pos]=self.seg[2*pos] if self.seg[2*pos]<self.seg[2*pos+1] else self.seg[2*pos+1]
pos//=2
def query(self,l,r):
l=self.size+(l-1)
r=self.size+(r-1)
res=INF
while l<=r:
if l%2==1:
if self.seg[l]<res:
res=self.seg[l]
l+=1
if r%2==0:
if self.seg[r]<res:
res=self.seg[r]
r-=1
l//=2
r//=2
return res
st=SegmentTree(a)
out=[]
for _ in range(q):
t=int(next(it))
if t==1:
i=int(next(it)); x=int(next(it))
st.update(i,x)
else:
l=int(next(it)); r=int(next(it))
out.append(str(st.query(l,r)))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!