7.2 线段树与树状数组（Fenwick Tree）

文档摘要

7.2 线段树与树状数组（Fenwick Tree） 7.2 线段树与树状数组（Fenwick Tree）线段树和树状数组都是用于解决区间查询问题的有效数据结构。它们都可以在对数时间内完成区间求和、区间最大/最小值等操作，并在某些情况下进行区间更新。虽然它们解决的问题类似，但其实现原理和适用场景有所不同。 7.2.1 线段树 (Segment Tree) 概念：线段树是一种二叉树结构，用于存储区间或线段的信息，并允许快速查询和更新这些区间的信息。树的每一个节点代表一个区间。根节点代表整个区间，叶子节点代表单个元素。结构：每个节点存储一个区间的信息，通常是区间和、最大值、最小值等。每个非叶子节点都有两个子节点，分别代表其父节点的左半区间和右半区间。