| 1 | class SegmentTree: # Every node has an index and a segment range |
| 2 | def __init__(self,arr): |
| 3 | self.arr=arr |
| 4 | self.seg=[0]*(4*len(arr)) |
| 5 | |
| 6 | def build(self,ind,low,high): # [low,high] = segment range |
| 7 | if low==high: |
| 8 | self.seg[ind]=self.arr[low] |
| 9 | return |
| 10 | mid=(low+high)//2 |
| 11 | self.build(2*ind+1,low,mid) |
| 12 | self.build(2*ind+2,mid+1,high) |
| 13 | self.seg[ind]=max(self.seg[2*ind+1],self.seg[2*ind+2]) # changes |
| 14 | |
| 15 | def update(self,ind,low,high,i,val): # i in arr and idx in seg |
| 16 | if low==high: |
| 17 | self.arr[i]=val |
| 18 | self.seg[ind]=val |
| 19 | return |
| 20 | mid=(low+high)//2 |
| 21 | if low<=i<=mid: |
| 22 | self.update(2*ind+1,low,mid,i,val) |
| 23 | else: |
| 24 | self.update(2*ind+2,mid+1,high,i,val) |
| 25 | self.seg[ind]=max(self.seg[2*ind+1],self.seg[2*ind+2]) |
| 26 | |
| 27 | def query(self,ind,low,high,l,r): # [l,r] = query range |
| 28 | if l<=low and high<=r: # if s range is completely inside q range |
| 29 | return self.seg[ind] |
| 30 | if high<l or r<low: # if s range is completely outside q range |
| 31 | return -float('inf') # changes |
| 32 | mid=(low+high)//2 |
| 33 | left=self.query(2*ind+1,low,mid,l,r) |
| 34 | right=self.query(2*ind+2,mid+1,high,l,r) |
| 35 | return max(left,right) # changes |
| 36 | |
| 37 | |
| 38 | t=SegmentTree([2,3,1,4,0,7,4,9,3,0]) |