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 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()总结线段树是一种强大的数据结构可以应用于多种场景包括区间和查询、区间最大值/最小值查询、区间修改等。