Update value at given index and propagate changes upward.
(self, index: int, value: T)
| 59 | return object # pytype: disable=bad-return-type |
| 60 | |
| 61 | def update(self, index: int, value: T) -> None: |
| 62 | """Update value at given index and propagate changes upward.""" |
| 63 | if not 0 <= index < self.size: |
| 64 | raise IndexError(f"Index {index} out of bounds for size {self.size}") |
| 65 | |
| 66 | is_max_operation = self.operation is max |
| 67 | is_non_negative_default = ( |
| 68 | isinstance(self.default_value, (int, float)) and self.default_value >= 0 |
| 69 | ) |
| 70 | is_negative_value = isinstance(value, (int, float)) and value < 0 |
| 71 | if is_max_operation and is_non_negative_default and is_negative_value: |
| 72 | raise ValueError( |
| 73 | f"Negative value {value} not supported for max operations with " |
| 74 | f"non-negative default_value={self.default_value}. This causes incorrect " |
| 75 | f"query results. Use default_value=float('-inf') for negative numbers." |
| 76 | ) |
| 77 | |
| 78 | leaf_idx = self.tree_size + index |
| 79 | self.tree[leaf_idx] = value |
| 80 | |
| 81 | parent = leaf_idx // 2 |
| 82 | while parent > 0: |
| 83 | left_child = 2 * parent |
| 84 | right_child = 2 * parent + 1 |
| 85 | self.tree[parent] = self.operation(self.tree[left_child], self.tree[right_child]) |
| 86 | parent //= 2 |
| 87 | |
| 88 | def query_range(self, left: int, right: int) -> T: |
| 89 | """Query operation result over range [left, right] inclusive.""" |
no outgoing calls
no test coverage detected