LeetCode 线段树简介题解

LeetCode 线段树简介题解题目描述介绍线段树Segment Tree的基本概念和原理。线段树简介什么是线段树线段树是一种二叉树形数据结构用于高效地处理区间查询和更新操作。它可以在 O(log n) 的时间内完成以下操作单点更新区间查询区间更新基本原理线段树的每个节点代表一个区间根节点代表整个数组区间。每个节点的左右子节点分别代表该区间的左半部分和右半部分。应用场景区间和查询区间最大值/最小值查询区间更新代码实现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 st.update(1, 0, 4, 1, 10) print(st.query(1, 0, 4, 0, 2)) # 输出16 if __name__ __main__: test_segment_tree()总结线段树是一种高效的数据结构可以在 O(log n) 的时间内完成区间查询和更新操作。