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()总结
线段树的优化技巧包括懒惰传播、离散化、动态开点和区间合并，可以提高线段树的性能。
