LeetCode 线段树简介题解

LeetCode 线段树简介题解

题目描述

介绍线段树（Segment Tree）的基本概念和原理。

线段树简介

什么是线段树

线段树是一种二叉树形数据结构，用于高效地处理区间查询和更新操作。它可以在 O(log n) 的时间内完成以下操作：

1. 单点更新
2. 区间查询
3. 区间更新

基本原理

线段树的每个节点代表一个区间，根节点代表整个数组区间。每个节点的左右子节点分别代表该区间的左半部分和右半部分。

应用场景

1. 区间和查询
2. 区间最大值/最小值查询
3. 区间更新

代码实现

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) 的时间内完成区间查询和更新操作。