LeetCode 线段树解题技巧题解

LeetCode 线段树解题技巧题解题目描述总结线段树解题的技巧和模板。线段树解题技巧1. 区间求和使用线段树维护区间的元素和。查询时返回区间和。2. 区间最大值/最小值使用线段树维护区间的最大值/最小值。查询时返回区间最大值/最小值。3. 区间修改使用懒惰传播记录修改操作。查询时将修改操作向下传递。4. 区间合并维护区间的多个属性。合并时计算新的属性值。5. 离散化将大范围数据映射到小范围索引。减少空间复杂度。代码模板class SegmentTree: def __init__(self, nums): self.n len(nums) self.tree [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 update(self, node, l, r, idx, val): if l r: self.tree[node] val else: mid (l r) // 2 if idx mid: self.update(node * 2, l, mid, idx, val) else: self.update(node * 2 1, mid 1, r, idx, val) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def query(self, node, l, r, ql, qr): if ql r or qr l: return 0 if ql l and r qr: return self.tree[node] mid (l r) // 2 return self.query(node * 2, l, mid, ql, qr) self.query(node * 2 1, mid 1, r, ql, qr) # 测试 def test_segment_tree(): nums [1, 2, 3, 4, 5] st SegmentTree(nums) print(st.query(1, 0, 4, 0, 2)) # 输出6 if __name__ __main__: test_segment_tree()总结线段树是一种强大的数据结构掌握解题技巧可以有效地解决各种区间问题。