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()总结
动态线段树可以有效地减少空间复杂度，只在需要时创建节点。
