| 2 | import math |
| 3 | |
| 4 | class SegmentTree: |
| 5 | |
| 6 | def __init__(self, A): |
| 7 | self.N = len(A) |
| 8 | self.st = [0] * (4 * self.N) # approximate the overall size of segment tree with array N |
| 9 | self.build(1, 0, self.N - 1) |
| 10 | |
| 11 | def left(self, idx): |
| 12 | return idx * 2 |
| 13 | |
| 14 | def right(self, idx): |
| 15 | return idx * 2 + 1 |
| 16 | |
| 17 | def build(self, idx, l, r): |
| 18 | if l == r: |
| 19 | self.st[idx] = A[l] |
| 20 | else: |
| 21 | mid = (l + r) // 2 |
| 22 | self.build(self.left(idx), l, mid) |
| 23 | self.build(self.right(idx), mid + 1, r) |
| 24 | self.st[idx] = max(self.st[self.left(idx)] , self.st[self.right(idx)]) |
| 25 | |
| 26 | def update(self, a, b, val): |
| 27 | return self.update_recursive(1, 0, self.N - 1, a - 1, b - 1, val) |
| 28 | |
| 29 | def update_recursive(self, idx, l, r, a, b, val): # update(1, 1, N, a, b, v) for update val v to [a,b] |
| 30 | if r < a or l > b: |
| 31 | return True |
| 32 | if l == r : |
| 33 | self.st[idx] = val |
| 34 | return True |
| 35 | mid = (l+r)//2 |
| 36 | self.update_recursive(self.left(idx), l, mid, a, b, val) |
| 37 | self.update_recursive(self.right(idx), mid+1, r, a, b, val) |
| 38 | self.st[idx] = max(self.st[self.left(idx)] , self.st[self.right(idx)]) |
| 39 | return True |
| 40 | |
| 41 | def query(self, a, b): |
| 42 | return self.query_recursive(1, 0, self.N - 1, a - 1, b - 1) |
| 43 | |
| 44 | def query_recursive(self, idx, l, r, a, b): #query(1, 1, N, a, b) for query max of [a,b] |
| 45 | if r < a or l > b: |
| 46 | return -math.inf |
| 47 | if l >= a and r <= b: |
| 48 | return self.st[idx] |
| 49 | mid = (l+r)//2 |
| 50 | q1 = self.query_recursive(self.left(idx), l, mid, a, b) |
| 51 | q2 = self.query_recursive(self.right(idx), mid + 1, r, a, b) |
| 52 | return max(q1, q2) |
| 53 | |
| 54 | def showData(self): |
| 55 | showList = [] |
| 56 | for i in range(1,N+1): |
| 57 | showList += [self.query(i, i)] |
| 58 | print (showList) |
| 59 | |
| 60 | |
| 61 | if __name__ == '__main__': |