LeetCode 线段树优化题解

LeetCode 线段树优化题解题目描述介绍线段树的优化技巧。线段树优化技巧1. 懒惰传播延迟更新操作减少不必要的更新。将更新操作记录在懒标记中后续需要时再向下传递。2. 离散化将大范围数据映射到小范围索引。减少线段树的空间复杂度。3. 动态开点只在需要时创建节点。减少空间复杂度。4. 区间合并预先计算区间合并的结果。减少查询时的计算量。代码实现class LazySegmentTree: def __init__(self, nums): self.n len(nums) self.tree [0] * (4 * self.n) self.lazy [0] * (4 * self.n) self.build(1, 0, self.n - 1, nums) def build(self, node, l, r, nums): if l r: self.tree[node] nums[l] else: mid (l r) // 2 self.build(node * 2, l, mid, nums) self.build(node * 2 1, mid 1, r, nums) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def push_down(self, node, l, r): if self.lazy[node] ! 0: mid (l r) // 2 self.tree[node * 2] self.lazy[node] * (mid - l 1) self.tree[node * 2 1] self.lazy[node] * (r - mid) self.lazy[node * 2] self.lazy[node] self.lazy[node * 2 1] self.lazy[node] self.lazy[node] 0 def update(self, node, l, r, ql, qr, val): if ql r or qr l: return if ql l and r qr: self.tree[node] val * (r - l 1) self.lazy[node] val return self.push_down(node, l, r) mid (l r) // 2 self.update(node * 2, l, mid, ql, qr, val) self.update(node * 2 1, mid 1, r, ql, qr, val) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] # 测试 def test_lazy_segment_tree(): nums [1, 2, 3, 4, 5] lst LazySegmentTree(nums) lst.update(1, 0, 4, 0, 2, 1) print(lst.tree[1]) # 输出9 if __name__ __main__: test_lazy_segment_tree()总结线段树的优化技巧包括懒惰传播、离散化、动态开点和区间合并可以提高线段树的性能。