query(1, 1, size, a, b) for query max of [a,b] >>> A = [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8] >>> segment_tree = SegmentTree(15) >>> segment_tree.build(1, 1, 15, A) >>> segment_tree.query(1, 1, 15, 4, 6) 7 >>> segment_tree.query
(
self, idx: int, left_element: int, right_element: int, a: int, b: int
)
| 87 | |
| 88 | # query with O(lg n) |
| 89 | def query( |
| 90 | self, idx: int, left_element: int, right_element: int, a: int, b: int |
| 91 | ) -> int | float: |
| 92 | """ |
| 93 | query(1, 1, size, a, b) for query max of [a,b] |
| 94 | >>> A = [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8] |
| 95 | >>> segment_tree = SegmentTree(15) |
| 96 | >>> segment_tree.build(1, 1, 15, A) |
| 97 | >>> segment_tree.query(1, 1, 15, 4, 6) |
| 98 | 7 |
| 99 | >>> segment_tree.query(1, 1, 15, 7, 11) |
| 100 | 14 |
| 101 | >>> segment_tree.query(1, 1, 15, 7, 12) |
| 102 | 15 |
| 103 | """ |
| 104 | if self.flag[idx] is True: |
| 105 | self.segment_tree[idx] = self.lazy[idx] |
| 106 | self.flag[idx] = False |
| 107 | if left_element != right_element: |
| 108 | self.lazy[self.left(idx)] = self.lazy[idx] |
| 109 | self.lazy[self.right(idx)] = self.lazy[idx] |
| 110 | self.flag[self.left(idx)] = True |
| 111 | self.flag[self.right(idx)] = True |
| 112 | if right_element < a or left_element > b: |
| 113 | return -math.inf |
| 114 | if left_element >= a and right_element <= b: |
| 115 | return self.segment_tree[idx] |
| 116 | mid = (left_element + right_element) // 2 |
| 117 | q1 = self.query(self.left(idx), left_element, mid, a, b) |
| 118 | q2 = self.query(self.right(idx), mid + 1, right_element, a, b) |
| 119 | return max(q1, q2) |
| 120 | |
| 121 | def __str__(self) -> str: |
| 122 | return str([self.query(1, 1, self.size, i, i) for i in range(1, self.size + 1)]) |
no test coverage detected