高效区间查询数据结构 | AI生成和翻译
线段树与树状数组：概述
线段树和树状数组（又称二叉索引树）都是高效的数据结构，常用于竞赛编程和算法中处理数组的区间查询与更新操作。它们能够在对数时间内完成诸如区间求和或单点更新等操作，对于大型数据集而言，这比朴素的 O(n) 方法要快得多。
线段树
线段树是一种基于二叉树的结构，通过将数组划分为若干段（区间）来表示数组：
- 叶节点代表单个元素。
- 父节点代表其子节点范围的并集（例如子段的和、最小值、最大值）。
- 该树通常以递归方式构建，对于大小为 n 的数组，其高度为 O(log n)。
关键操作：
- 构建： 构建树的时间复杂度为 O(n)。
- 更新： 修改单个元素并在 O(log n) 时间内向上传播变更。
- 查询： 通过遍历相关节点在 O(log n) 时间内计算区间聚合值（例如求和）。
应用场景： 区间求和/最小值/最大值查询、频率统计或任何可结合的操作。它更灵活，但占用 O(4n) 空间。
简单示例（区间求和）： 假设数组为 [1, 3, 5, 7]。线段树可能如下所示：
- 根节点：[1-7] 的和 = 16
- 左子节点：[1-3] 的和 = 4
- 右子节点：[5-7] 的和 = 12
- 依此类推，直至叶节点。
树状数组
树状数组（由 Peter Fenwick 于 1994 年提出）是一种更紧凑的基于数组的结构，用于处理前缀和及类似操作。它利用位运算高效索引元素，以巧妙的方式跟踪累积和：
- 每个索引存储以该索引结尾的某个区间的和。
- 更新和查询使用低位操作（例如，
index & -index用于查找最低有效位）。
关键操作：
- 构建： O(n log n) 或优化至 O(n)。
- 更新： 在 O(log n) 时间内对某个索引进行值的加减。
- 查询： 在 O(log n) 时间内获取到某个索引的前缀和；通过前缀差计算区间和。
应用场景： 与线段树类似，但针对一维前缀和、顺序统计或逆序计数进行了优化。它占用 O(n) 空间，更为轻量。
简单示例（区间求和）： 对于数组 [1, 3, 5, 7]，树状数组可能为 [1, 4, 5, 16]（累积调整值）。查询区间 [1-3] 的和：prefix(3) - prefix(0) = 9。
对比
| 方面 | 线段树 | 树状数组 |
|---|---|---|
| 空间 | O(4n) | O(n) |
| 构建时间 | O(n) | O(n log n) |
| 灵活性 | 支持任意区间聚合操作 | 最适合前缀和/更新操作 |
| 复杂度 | 代码稍复杂 | 实现更简单 |
两者都是算法中的常客（例如在 LeetCode 或 Codeforces 上）。如果正在实现它们，可以从树状数组开始以简化操作！
深入阅读：
线段树教程 - GeeksforGeeks
树状数组详解 - CP-Algorithms