LeetCode 动态线段树题解题目描述实现一个动态开点的线段树。解题思路方法动态线段树思路只在需要时创建节点。每个节点维护左右子节点的指针。复杂度分析时间复杂度O(log n)。空间复杂度O(k log n)k 是操作次数。代码实现class Node: def __init__(self): self.left None self.right None self.val 0 self.lazy 0 class DynamicSegmentTree: def __init__(self): self.root Node() def update(self, node, l, r, ql, qr, val): if ql r or qr l: return if ql l and r qr: node.val val * (r - l 1) node.lazy val return mid (l r) // 2 if node.left is None: node.left Node() if node.right is None: node.right Node() self.push_down(node, l, r) self.update(node.left, l, mid, ql, qr, val) self.update(node.right, mid 1, r, ql, qr, val) node.val node.left.val node.right.val def push_down(self, node, l, r): if node.lazy ! 0: mid (l r) // 2 if node.left is None: node.left Node() if node.right is None: node.right Node() node.left.val node.lazy * (mid - l 1) node.right.val node.lazy * (r - mid) node.left.lazy node.lazy node.right.lazy node.lazy node.lazy 0 def query(self, node, l, r, ql, qr): if ql r or qr l: return 0 if ql l and r qr: return node.val mid (l r) // 2 if node.left is None: node.left Node() if node.right is None: node.right Node() self.push_down(node, l, r) return self.query(node.left, l, mid, ql, qr) self.query(node.right, mid 1, r, ql, qr) # 测试 def test_dynamic_segment_tree(): dst DynamicSegmentTree() dst.update(dst.root, 0, 4, 0, 2, 1) print(dst.query(dst.root, 0, 4, 0, 2)) # 输出6 if __name__ __main__: test_dynamic_segment_tree()总结动态线段树可以有效地减少空间复杂度只在需要时创建节点。