update with O(lg n) (Normal segment tree without lazy update will take O(nlg n) for each update) update(1, 1, size, a, b, v) for update val v to [a,b]
(
self, idx: int, left_element: int, right_element: int, a: int, b: int, val: int
)
| 50 | ) |
| 51 | |
| 52 | def update( |
| 53 | self, idx: int, left_element: int, right_element: int, a: int, b: int, val: int |
| 54 | ) -> bool: |
| 55 | """ |
| 56 | update with O(lg n) (Normal segment tree without lazy update will take O(nlg n) |
| 57 | for each update) |
| 58 | |
| 59 | update(1, 1, size, a, b, v) for update val v to [a,b] |
| 60 | """ |
| 61 | if self.flag[idx] is True: |
| 62 | self.segment_tree[idx] = self.lazy[idx] |
| 63 | self.flag[idx] = False |
| 64 | if left_element != right_element: |
| 65 | self.lazy[self.left(idx)] = self.lazy[idx] |
| 66 | self.lazy[self.right(idx)] = self.lazy[idx] |
| 67 | self.flag[self.left(idx)] = True |
| 68 | self.flag[self.right(idx)] = True |
| 69 | |
| 70 | if right_element < a or left_element > b: |
| 71 | return True |
| 72 | if left_element >= a and right_element <= b: |
| 73 | self.segment_tree[idx] = val |
| 74 | if left_element != right_element: |
| 75 | self.lazy[self.left(idx)] = val |
| 76 | self.lazy[self.right(idx)] = val |
| 77 | self.flag[self.left(idx)] = True |
| 78 | self.flag[self.right(idx)] = True |
| 79 | return True |
| 80 | mid = (left_element + right_element) // 2 |
| 81 | self.update(self.left(idx), left_element, mid, a, b, val) |
| 82 | self.update(self.right(idx), mid + 1, right_element, a, b, val) |
| 83 | self.segment_tree[idx] = max( |
| 84 | self.segment_tree[self.left(idx)], self.segment_tree[self.right(idx)] |
| 85 | ) |
| 86 | return True |
| 87 | |
| 88 | # query with O(lg n) |
| 89 | def query( |
no test coverage detected