线段树是一种树形数据结构,用于存储区间或线段,并且允许快速查询区间信息(如求和、最大值、最小值等)以及进行区间更新。线段树特别适合解决区间查询问题,其查询和更新操作的时间复杂度都是O(log n)。
线段树(Segment Tree)是一种高效的数据结构,专门用于解决区间查询和区间修改问题。与树状数组相比,线段树功能更加强大,可以支持更多种类的区间操作。
线段树的核心思想是通过分治法将一个区间划分为多个子区间,并用树的形式组织这些区间的信息。在这棵树中,每个节点代表一个区间,根节点代表整个数组区间,叶子节点代表单个元素。
核心概念解释:
下面是线段树的基础实现(以区间和为例):
▼Java复制代码public class SegmentTree { private int[] tree; // 存储线段树节点 private int[] lazy; // 懒惰标记 private int[] nums; // 原始数组的副本 private int n; // 原始数组长度 public SegmentTree(int[] array) { n = array.length; // 线段树数组大小一般为原数组大小的4倍 tree = new int[4 * n]; lazy = new int[4 * n]; nums = array.clone(); build(0, 0, n - 1); } // 构建线段树 private void build(int node, int start, int end) { if (start == end) { // 叶子节点,存储单个元素 tree[node] = nums[start]; return; } int mid = (start + end) / 2; int leftNode = 2 * node + 1; int rightNode = 2 * node + 2; // 递归构建左右子树 build(leftNode, start, mid); build(rightNode, mid + 1, end); // 合并子节点的信息 tree[node] = tree[leftNode] + tree[rightNode]; } // 单点修改 public void update(int index, int val) { // 计算与原值的差值 int diff = val - nums[index]; nums[index] = val; updateSingle(0, 0, n - 1, index, diff); } private void updateSingle(int node, int start, int end, int index, int diff) { // 检查索引是否在当前节点范围内 if (index < start || index > end) { return; } // 更新当前节点的值 tree[node] += diff; if (start != end) { int mid = (start + end) / 2; int leftNode = 2 * node + 1; int rightNode = 2 * node + 2; // 递归更新子节点 updateSingle(leftNode, start, mid, index, diff); updateSingle(rightNode, mid + 1, end, index, diff); } } // 区间查询 public int query(int left, int right) { return queryRange(0, 0, n - 1, left, right); } private int queryRange(int node, int start, int end, int left, int right) { // 如果当前节点的区间完全在查询区间外 if (right < start || left > end) { return 0; } // 如果当前节点的区间完全在查询区间内 if (left <= start && end <= right) { return tree[node]; } // 处理懒惰标记 if (lazy[node] != 0) { tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[2 * node + 1] += lazy[node]; lazy[2 * node + 2] += lazy[node]; } lazy[node] = 0; } // 查询范围部分覆盖当前节点的区间,需要分别查询左右子节点 int mid = (start + end) / 2; int leftSum = queryRange(2 * node + 1, start, mid, left, right); int rightSum = queryRange(2 * node + 2, mid + 1, end, left, right); return leftSum + rightSum; } // 区间修改 public void updateRange(int left, int right, int val) { updateRangeTree(0, 0, n - 1, left, right, val); } private void updateRangeTree(int node, int start, int end, int left, int right, int val) { // 处理当前节点的懒惰标记 if (lazy[node] != 0) { tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[2 * node + 1] += lazy[node]; lazy[2 * node + 2] += lazy[node]; } lazy[node] = 0; } // 如果当前节点的区间完全在修改区间外 if (right < start || left > end) { return; } // 如果当前节点的区间完全在修改区间内 if (left <= start && end <= right) { tree[node] += (end - start + 1) * val; if (start != end) { lazy[2 * node + 1] += val; lazy[2 * node + 2] += val; } return; } // 修改范围部分覆盖当前节点的区间,需要分别修改左右子节点 int mid = (start + end) / 2; updateRangeTree(2 * node + 1, start, mid, left, right, val); updateRangeTree(2 * node + 2, mid + 1, end, left, right, val); // 更新当前节点的值 tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; } }
▼Javascript复制代码class SegmentTree { constructor(array) { this.n = array.length; // 线段树数组大小一般为原数组大小的4倍 this.tree = new Array(4 * this.n).fill(0); this.lazy = new Array(4 * this.n).fill(0); // 克隆原始数组 this.nums = [...array]; this.build(0, 0, this.n - 1); } // 构建线段树 build(node, start, end) { if (start === end) { // 叶子节点,存储单个元素 this.tree[node] = this.nums[start]; return; } const mid = Math.floor((start + end) / 2); const leftNode = 2 * node + 1; const rightNode = 2 * node + 2; // 递归构建左右子树 this.build(leftNode, start, mid); this.build(rightNode, mid + 1, end); // 合并子节点的信息 this.tree[node] = this.tree[leftNode] + this.tree[rightNode]; } // 单点修改 update(index, val) { // 计算与原值的差值 const diff = val - this.nums[index]; this.nums[index] = val; this.updateSingle(0, 0, this.n - 1, index, diff); } updateSingle(node, start, end, index, diff) { // 检查索引是否在当前节点范围内 if (index < start || index > end) { return; } // 更新当前节点的值 this.tree[node] += diff; if (start !== end) { const mid = Math.floor((start + end) / 2); const leftNode = 2 * node + 1; const rightNode = 2 * node + 2; // 递归更新子节点 this.updateSingle(leftNode, start, mid, index, diff); this.updateSingle(rightNode, mid + 1, end, index, diff); } } // 区间查询 query(left, right) { return this.queryRange(0, 0, this.n - 1, left, right); } queryRange(node, start, end, left, right) { // 如果当前节点的区间完全在查询区间外 if (right < start || left > end) { return 0; } // 如果当前节点的区间完全在查询区间内 if (left <= start && end <= right) { return this.tree[node]; } // 处理懒惰标记 if (this.lazy[node] !== 0) { this.tree[node] += (end - start + 1) * this.lazy[node]; if (start !== end) { this.lazy[2 * node + 1] += this.lazy[node]; this.lazy[2 * node + 2] += this.lazy[node]; } this.lazy[node] = 0; } // 查询范围部分覆盖当前节点的区间,需要分别查询左右子节点 const mid = Math.floor((start + end) / 2); const leftSum = this.queryRange(2 * node + 1, start, mid, left, right); const rightSum = this.queryRange(2 * node + 2, mid + 1, end, left, right); return leftSum + rightSum; } // 区间修改 updateRange(left, right, val) { this.updateRangeTree(0, 0, this.n - 1, left, right, val); } updateRangeTree(node, start, end, left, right, val) { // 处理当前节点的懒惰标记 if (this.lazy[node] !== 0) { this.tree[node] += (end - start + 1) * this.lazy[node]; if (start !== end) { this.lazy[2 * node + 1] += this.lazy[node]; this.lazy[2 * node + 2] += this.lazy[node]; } this.lazy[node] = 0; } // 如果当前节点的区间完全在修改区间外 if (right < start || left > end) { return; } // 如果当前节点的区间完全在修改区间内 if (left <= start && end <= right) { this.tree[node] += (end - start + 1) * val; if (start !== end) { this.lazy[2 * node + 1] += val; this.lazy[2 * node + 2] += val; } return; } // 修改范围部分覆盖当前节点的区间,需要分别修改左右子节点 const mid = Math.floor((start + end) / 2); this.updateRangeTree(2 * node + 1, start, mid, left, right, val); this.updateRangeTree(2 * node + 2, mid + 1, end, left, right, val); // 更新当前节点的值 this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2]; } }
▼Python复制代码class SegmentTree: def __init__(self, array): self.n = len(array) # 线段树数组大小一般为原数组大小的4倍 self.tree = [0] * (4 * self.n) self.lazy = [0] * (4 * self.n) # 克隆原始数组 self.nums = array.copy() self.build(0, 0, self.n - 1) # 构建线段树 def build(self, node, start, end): if start == end: # 叶子节点,存储单个元素 self.tree[node] = self.nums[start] return mid = (start + end) // 2 left_node = 2 * node + 1 right_node = 2 * node + 2 # 递归构建左右子树 self.build(left_node, start, mid) self.build(right_node, mid + 1, end) # 合并子节点的信息 self.tree[node] = self.tree[left_node] + self.tree[right_node] # 单点修改 def update(self, index, val): # 计算与原值的差值 diff = val - self.nums[index] self.nums[index] = val self.update_single(0, 0, self.n - 1, index, diff) def update_single(self, node, start, end, index, diff): # 检查索引是否在当前节点范围内 if index < start or index > end: return # 更新当前节点的值 self.tree[node] += diff if start != end: mid = (start + end) // 2 left_node = 2 * node + 1 right_node = 2 * node + 2 # 递归更新子节点 self.update_single(left_node, start, mid, index, diff) self.update_single(right_node, mid + 1, end, index, diff) # 区间查询 def query(self, left, right): return self.query_range(0, 0, self.n - 1, left, right) def query_range(self, node, start, end, left, right): # 如果当前节点的区间完全在查询区间外 if right < start or left > end: return 0 # 如果当前节点的区间完全在查询区间内 if left <= start and end <= right: return self.tree[node] # 处理懒惰标记 if self.lazy[node] != 0: self.tree[node] += (end - start + 1) * self.lazy[node] if start != end: self.lazy[2 * node + 1] += self.lazy[node] self.lazy[2 * node + 2] += self.lazy[node] self.lazy[node] = 0 # 查询范围部分覆盖当前节点的区间,需要分别查询左右子节点 mid = (start + end) // 2 left_sum = self.query_range(2 * node + 1, start, mid, left, right) right_sum = self.query_range(2 * node + 2, mid + 1, end, left, right) return left_sum + right_sum # 区间修改 def update_range(self, left, right, val): self.update_range_tree(0, 0, self.n - 1, left, right, val) def update_range_tree(self, node, start, end, left, right, val): # 处理当前节点的懒惰标记 if self.lazy[node] != 0: self.tree[node] += (end - start + 1) * self.lazy[node] if start != end: self.lazy[2 * node + 1] += self.lazy[node] self.lazy[2 * node + 2] += self.lazy[node] self.lazy[node] = 0 # 如果当前节点的区间完全在修改区间外 if right < start or left > end: return # 如果当前节点的区间完全在修改区间内 if left <= start and end <= right: self.tree[node] += (end - start + 1) * val if start != end: self.lazy[2 * node + 1] += val self.lazy[2 * node + 2] += val return # 修改范围部分覆盖当前节点的区间,需要分别修改左右子节点 mid = (start + end) // 2 self.update_range_tree(2 * node + 1, start, mid, left, right, val) self.update_range_tree(2 * node + 2, mid + 1, end, left, right, val) # 更新当前节点的值 self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
▼Go复制代码package main // SegmentTree 线段树结构体 type SegmentTree struct { tree []int // 存储线段树节点 lazy []int // 懒惰标记 nums []int // 原始数组的副本 n int // 原始数组长度 } // NewSegmentTree 创建并初始化一个新的线段树 func NewSegmentTree(array []int) *SegmentTree { n := len(array) tree := make([]int, 4*n) lazy := make([]int, 4*n) nums := make([]int, n) copy(nums, array) st := &SegmentTree{ tree: tree, lazy: lazy, nums: nums, n: n, } st.build(0, 0, n-1) return st } // 构建线段树 func (st *SegmentTree) build(node, start, end int) { if start == end { // 叶子节点,存储单个元素 st.tree[node] = st.nums[start] return } mid := (start + end) / 2 leftNode := 2*node + 1 rightNode := 2*node + 2 // 递归构建左右子树 st.build(leftNode, start, mid) st.build(rightNode, mid+1, end) // 合并子节点的信息 st.tree[node] = st.tree[leftNode] + st.tree[rightNode] } // Update 单点修改 func (st *SegmentTree) Update(index, val int) { // 计算与原值的差值 diff := val - st.nums[index] st.nums[index] = val st.updateSingle(0, 0, st.n-1, index, diff) } func (st *SegmentTree) updateSingle(node, start, end, index, diff int) { // 检查索引是否在当前节点范围内 if index < start || index > end { return } // 更新当前节点的值 st.tree[node] += diff if start != end { mid := (start + end) / 2 leftNode := 2*node + 1 rightNode := 2*node + 2 // 递归更新子节点 st.updateSingle(leftNode, start, mid, index, diff) st.updateSingle(rightNode, mid+1, end, index, diff) } } // Query 区间查询 func (st *SegmentTree) Query(left, right int) int { return st.queryRange(0, 0, st.n-1, left, right) } func (st *SegmentTree) queryRange(node, start, end, left, right int) int { // 如果当前节点的区间完全在查询区间外 if right < start || left > end { return 0 } // 如果当前节点的区间完全在查询区间内 if left <= start && end <= right { return st.tree[node] } // 处理懒惰标记 if st.lazy[node] != 0 { st.tree[node] += (end - start + 1) * st.lazy[node] if start != end { st.lazy[2*node+1] += st.lazy[node] st.lazy[2*node+2] += st.lazy[node] } st.lazy[node] = 0 } // 查询范围部分覆盖当前节点的区间,需要分别查询左右子节点 mid := (start + end) / 2 leftSum := st.queryRange(2*node+1, start, mid, left, right) rightSum := st.queryRange(2*node+2, mid+1, end, left, right) return leftSum + rightSum } // UpdateRange 区间修改 func (st *SegmentTree) UpdateRange(left, right, val int) { st.updateRangeTree(0, 0, st.n-1, left, right, val) } func (st *SegmentTree) updateRangeTree(node, start, end, left, right, val int) { // 处理当前节点的懒惰标记 if st.lazy[node] != 0 { st.tree[node] += (end - start + 1) * st.lazy[node] if start != end { st.lazy[2*node+1] += st.lazy[node] st.lazy[2*node+2] += st.lazy[node] } st.lazy[node] = 0 } // 如果当前节点的区间完全在修改区间外 if right < start || left > end { return } // 如果当前节点的区间完全在修改区间内 if left <= start && end <= right { st.tree[node] += (end - start + 1) * val if start != end { st.lazy[2*node+1] += val st.lazy[2*node+2] += val } return } // 修改范围部分覆盖当前节点的区间,需要分别修改左右子节点 mid := (start + end) / 2 st.updateRangeTree(2*node+1, start, mid, left, right, val) st.updateRangeTree(2*node+2, mid+1, end, left, right, val) // 更新当前节点的值 st.tree[node] = st.tree[2*node+1] + st.tree[2*node+2] }
▼C++复制代码#include <vector> #include <algorithm> class SegmentTree { private: std::vector<int> tree; // 存储线段树节点 std::vector<int> lazy; // 懒惰标记 std::vector<int> nums; // 原始数组的副本 int n; // 原始数组长度 // 构建线段树 void build(int node, int start, int end) { if (start == end) { // 叶子节点,存储单个元素 tree[node] = nums[start]; return; } int mid = (start + end) / 2; int leftNode = 2 * node + 1; int rightNode = 2 * node + 2; // 递归构建左右子树 build(leftNode, start, mid); build(rightNode, mid + 1, end); // 合并子节点的信息 tree[node] = tree[leftNode] + tree[rightNode]; } // 单点修改辅助函数 void updateSingle(int node, int start, int end, int index, int diff) { // 检查索引是否在当前节点范围内 if (index < start || index > end) { return; } // 更新当前节点的值 tree[node] += diff; if (start != end) { int mid = (start + end) / 2; int leftNode = 2 * node + 1; int rightNode = 2 * node + 2; // 递归更新子节点 updateSingle(leftNode, start, mid, index, diff); updateSingle(rightNode, mid + 1, end, index, diff); } } // 区间查询辅助函数 int queryRange(int node, int start, int end, int left, int right) { // 如果当前节点的区间完全在查询区间外 if (right < start || left > end) { return 0; } // 如果当前节点的区间完全在查询区间内 if (left <= start && end <= right) { return tree[node]; } // 处理懒惰标记 if (lazy[node] != 0) { tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[2 * node + 1] += lazy[node]; lazy[2 * node + 2] += lazy[node]; } lazy[node] = 0; } // 查询范围部分覆盖当前节点的区间,需要分别查询左右子节点 int mid = (start + end) / 2; int leftSum = queryRange(2 * node + 1, start, mid, left, right); int rightSum = queryRange(2 * node + 2, mid + 1, end, left, right); return leftSum + rightSum; } // 区间修改辅助函数 void updateRangeTree(int node, int start, int end, int left, int right, int val) { // 处理当前节点的懒惰标记 if (lazy[node] != 0) { tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[2 * node + 1] += lazy[node]; lazy[2 * node + 2] += lazy[node]; } lazy[node] = 0; } // 如果当前节点的区间完全在修改区间外 if (right < start || left > end) { return; } // 如果当前节点的区间完全在修改区间内 if (left <= start && end <= right) { tree[node] += (end - start + 1) * val; if (start != end) { lazy[2 * node + 1] += val; lazy[2 * node + 2] += val; } return; } // 修改范围部分覆盖当前节点的区间,需要分别修改左右子节点 int mid = (start + end) / 2; updateRangeTree(2 * node + 1, start, mid, left, right, val); updateRangeTree(2 * node + 2, mid + 1, end, left, right, val); // 更新当前节点的值 tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; } public: // 构造函数 SegmentTree(const std::vector<int>& array) { n = array.size(); // 线段树数组大小一般为原数组大小的4倍 tree.resize(4 * n, 0); lazy.resize(4 * n, 0); nums = array; build(0, 0, n - 1); } // 单点修改 void update(int index, int val) { // 计算与原值的差值 int diff = val - nums[index]; nums[index] = val; updateSingle(0, 0, n - 1, index, diff); } // 区间查询 int query(int left, int right) { return queryRange(0, 0, n - 1, left, right); } // 区间修改 void updateRange(int left, int right, int val) { updateRangeTree(0, 0, n - 1, left, right, val); } };
线段树的结构:
线段树是一棵完全二叉树,其中:
懒惰标记(Lazy Propagation):
懒惰标记是一种优化技术,用于延迟区间修改的传播。当一个节点的所有子节点都需要被修改时,我们不立即修改这些子节点,而是在节点上标记修改信息,只有在需要访问子节点时才将修改下推,提高区间修改的效率。
线段树在许多实际问题中有广泛应用,特别是在需要同时支持区间查询和区间修改的情况下:
当区间范围非常大,但实际有值的点比较稀疏时,可以使用动态线段树(通常使用指针实现)来节省空间:
▼Java复制代码public class DynamicSegmentTree { private class Node { int val; // 节点值 int lazy; // 懒惰标记 Node left; // 左子节点 Node right; // 右子节点 int start; // 区间起点 int end; // 区间终点 Node(int start, int end) { this.start = start; this.end = end; this.val = 0; this.lazy = 0; } } private Node root; public DynamicSegmentTree(int start, int end) { root = new Node(start, end); } // 区间更新 public void update(int left, int right, int val) { update(root, left, right, val); } private void update(Node node, int left, int right, int val) { // 如果区间完全在更新范围外 if (node.end < left || node.start > right) { return; } // 如果区间完全在更新范围内 if (node.start >= left && node.end <= right) { node.val += (node.end - node.start + 1) * val; if (node.start != node.end) { node.lazy += val; } return; } // 下推懒惰标记 pushDown(node); // 更新左右子节点 if (node.left != null) { update(node.left, left, right, val); } if (node.right != null) { update(node.right, left, right, val); } // 更新当前节点的值 node.val = (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0); } // 区间查询 public int query(int left, int right) { return query(root, left, right); } private int query(Node node, int left, int right) { // 如果区间完全在查询范围外 if (node.end < left || node.start > right) { return 0; } // 如果区间完全在查询范围内 if (node.start >= left && node.end <= right) { return node.val; } // 下推懒惰标记 pushDown(node); int sum = 0; if (node.left != null) { sum += query(node.left, left, right); } if (node.right != null) { sum += query(node.right, left, right); } return sum; } // 下推懒惰标记 private void pushDown(Node node) { if (node.lazy == 0) { return; } int mid = (node.start + node.end) / 2; // 创建左子节点(如果不存在) if (node.left == null) { node.left = new Node(node.start, mid); } // 创建右子节点(如果不存在) if (node.right == null) { node.right = new Node(mid + 1, node.end); } // 更新子节点的值和懒惰标记 node.left.val += (node.left.end - node.left.start + 1) * node.lazy; node.right.val += (node.right.end - node.right.start + 1) * node.lazy; if (node.left.start != node.left.end) { node.left.lazy += node.lazy; } if (node.right.start != node.right.end) { node.right.lazy += node.lazy; } // 清除当前节点的懒惰标记 node.lazy = 0; } }
可持久化线段树是线段树的一种变体,它可以保存历史版本,允许查询任意历史状态:
▼Java复制代码public class PersistentSegmentTree { private class Node { int val; // 节点值 Node left; // 左子节点 Node right; // 右子节点 Node(int val) { this.val = val; this.left = null; this.right = null; } Node(Node other) { this.val = other.val; this.left = other.left; this.right = other.right; } } private Node[] roots; // 存储历史版本的根节点 private int n; // 数组大小 private int versionCount; // 版本数量 public PersistentSegmentTree(int[] array, int maxVersions) { n = array.length; roots = new Node[maxVersions]; versionCount = 0; // 构建初始版本 roots[versionCount++] = build(0, n - 1, array); } // 构建线段树 private Node build(int start, int end, int[] array) { if (start == end) { return new Node(array[start]); } int mid = (start + end) / 2; Node node = new Node(0); node.left = build(start, mid, array); node.right = build(mid + 1, end, array); node.val = node.left.val + node.right.val; return node; } // 创建新版本并更新单个元素 public void update(int index, int val) { roots[versionCount] = update(roots[versionCount - 1], 0, n - 1, index, val); versionCount++; } private Node update(Node node, int start, int end, int index, int val) { if (index < start || index > end) { return node; } // 创建新节点(路径复制) Node newNode = new Node(node); if (start == end) { newNode.val = val; return newNode; } int mid = (start + end) / 2; if (index <= mid) { newNode.left = update(node.left, start, mid, index, val); } else { newNode.right = update(node.right, mid + 1, end, index, val); } newNode.val = newNode.left.val + newNode.right.val; return newNode; } // 查询特定版本的区间和 public int query(int version, int left, int right) { if (version >= versionCount) { throw new IllegalArgumentException("版本不存在"); } return query(roots[version], 0, n - 1, left, right); } private int query(Node node, int start, int end, int left, int right) { if (right < start || left > end) { return 0; } if (left <= start && end <= right) { return node.val; } int mid = (start + end) / 2; return query(node.left, start, mid, left, right) + query(node.right, mid + 1, end, left, right); } }
测验答案
- 线段树的每个节点代表一个区间[start, end],存储该区间的聚合信息(如区间和、最大值等)。与二叉搜索树不同,线段树的组织方式不是基于节点值的大小比较,而是基于区间的划分:每个非叶节点的左子节点代表区间的左半部分,右子节点代表右半部分。
- 懒惰标记是一种延迟更新的技术,用于优化区间修改操作。当需要对一个节点的所有子孙节点进行同样的修改时,不会立即递归地修改所有子节点,而是在当前节点上标记修改信息,只在需要访问子节点时才将修改信息下推。这样可以将区间修改的时间复杂度从O(n)优化到O(log n)。
- 一个长度为n的数组,构建出的线段树恰好有2n-1个节点:n个叶节点各对应一个元素,每个非叶节点都恰好有两个子节点,所以非叶节点有n-1个。但用数组按堆的方式存储(节点i的子节点为2i和2i+1)时,由于n不一定是2的幂,树的最后一层不一定从左到右连续填满,下标可能超过2n,因此通常分配4n大小的数组来确保足够。
- 线段树中执行区间查询的时间复杂度是O(log n)。这是因为在最坏情况下,一个区间查询需要访问O(log n)个节点:当查询区间与线段树的区间部分重叠时,需要分别查询左右子树;但由于树的高度是log n,因此最多需要访问O(log n)个节点。
- 线段树和树状数组的比较:
- 线段树的优点:功能更强大,可以支持区间修改和多种区间查询(最大值、最小值等),适用范围更广。
- 线段树的缺点:实现复杂,内存消耗大,常数因子较大。
- 树状数组的优点:实现简单,内存消耗小,常数因子小,更加高效。
- 树状数组的缺点:功能有限,主要支持区间和查询和单点修改。
- 应选择线段树的情况:需要支持区间修改操作,或需要查询区间最大值/最小值等非可加性质的聚合信息时。