| 156 | self.build_segment_tree() |
| 157 | |
| 158 | class SegmentTreeUpdate(SegmentTreeBase): |
| 159 | def __init__(self, **kwargs): |
| 160 | super().__init__(**kwargs) |
| 161 | |
| 162 | def find_element(self, node, val, new_val): |
| 163 | if not node: |
| 164 | return |
| 165 | if node.l==node.r and node.v == val: |
| 166 | n = self.tree.get_node(node.id) |
| 167 | self.play(n.set_color, RED) |
| 168 | self.show_message("修改元素") |
| 169 | n.set_text(str(new_val)) |
| 170 | n.set_color(RED) |
| 171 | node.v = new_val |
| 172 | return |
| 173 | |
| 174 | if node.l == node.r: |
| 175 | return |
| 176 | |
| 177 | self.find_element(node.left, val, new_val) |
| 178 | self.find_element(node.right, val, new_val) |
| 179 | old_v = node.v |
| 180 | node.v = node.left.v + node.right.v |
| 181 | if old_v != node.v: |
| 182 | n = self.tree.get_node(node.id) |
| 183 | self.show_message("更新元素%d -> %d"%(old_v, node.v)) |
| 184 | self.play(FocusOn(n)) |
| 185 | n.set_text(str(node.v)) |
| 186 | self.play(n.set_color, RED) |
| 187 | |
| 188 | def construct(self): |
| 189 | self.start_logo(animate=False) |
| 190 | self.init_message("更新线段树") |
| 191 | array = AlgoVector(self, self.datas) |
| 192 | array.set_color(BLUE) |
| 193 | self.play(ShowCreation(array)) |
| 194 | self.play(array.to_edge, LEFT) |
| 195 | self.array = array |
| 196 | |
| 197 | self.tree = AlgoSegTree(self, self.datas).scale(0.9) |
| 198 | self.tree.to_edge(edge=RIGHT).shift(LEFT) |
| 199 | self.play(ShowCreation(self.tree)) |
| 200 | # 3 -> 7 |
| 201 | self.show_messaged("比如将3更新为7") |
| 202 | new_node = AlgoNode("7", color=RED) |
| 203 | self.play(ShowCreation(new_node)) |
| 204 | self.play(new_node.next_to, self.array.get_node(3), DOWN) |
| 205 | arrow = Arrow(new_node, self.array.get_node(3)).set_color(BLUE) |
| 206 | self.play(ShowCreation(arrow)) |
| 207 | |
| 208 | self.show_message("首先是找到元素") |
| 209 | |
| 210 | # find |
| 211 | self.find_element(self.tree.root, 3, 7) |
| 212 | self.wait(10) |
| 213 | |
| 214 | class SegmentTreeQuery(SegmentTreeBase): |
| 215 | def __init__(self, **kwargs): |
nothing calls this directly
no outgoing calls
no test coverage detected