非线性数据结构之树

Fenwick 树（树状数组）

Fenwick 树（或称树状数组）是一种支持高效前缀和（Prefix Sum）查询和更新的数据结构。Fenwick 树的应用较广泛，特别是在处理频繁变动的区间数据时，能在 O(log n) 时间内完成查询和更新操作。

---

一、定义

Fenwick 树是一种使用数组结构来实现的树结构，每个元素 i 存储的值等于该位置索引的二进制表示中“最后一个 1”位所代表的区间和。例如，若 i = 6（110），则树状数组在位置 6 处存储了从索引 5 到 6 的区间和。

---

二、特点

1. 空间复杂度低：只需要一个与原数组相同大小的树状数组来记录前缀和。
2. 支持动态更新：更新某一元素后，只需更新相关节点而不影响其他数据，使其在实时更新数据的场景下高效。
3. 前缀和查询高效：每次查询通过递减“最后一个 1”位可以跳过部分区间，缩小查询范围。

三、操作

• 更新操作：修改数组的一个值并更新对应的树状数组，时间复杂度为 O(log n)。
  • 更新某个元素时，递增索引的“最后一个 1”位，更新树状数组。
• 前缀和查询：查询从起始位置到某位置的和，时间复杂度为 O(log n)。
  • 查询时不断去除索引的“最后一个 1”位，累加对应树状数组的值。

四、优缺点

• 优点：支持快速前缀和查询和单点更新，结构简单，易于实现，特别适用于频繁更新的场景。
• 缺点：仅支持单点更新，对于复杂区间操作支持有限。

五、应用

• 统计频率和排名：如在竞赛计分板中快速更新和查询分数排名。
• 区间和的实时更新：如金融数据或实时统计中需要快速响应的区间查询。

六、示例代码（Java 实现）

class FenwickTree {private int[] tree;public FenwickTree(int size) {tree = new int[size + 1];}// 单点更新public void update(int index, int delta) {while (index < tree.length) {tree[index] += delta;index += index & -index;}}// 查询前缀和public int query(int index) {int sum = 0;while (index > 0) {sum += tree[index];index -= index & -index;}return sum;}// 查询区间和public int rangeQuery(int left, int right) {return query(right) - query(left - 1);}
}

归并树（Merge Tree）

归并树是一种用于解决特定区间查询的树结构，通常用于静态数据集的查询优化，如处理区间最值查询、频数查询等。

---

一、定义

归并树是将数据分块并排序构建的一种树结构。每个节点存储一段区间，并按值排序，以方便二分查找等操作。构建过程中，归并树不断将左右子区间归并成有序的区间数组，逐层合并，形成一棵完全二叉树。

二、特点

1. 多种区间查询：支持区间求和、区间最值等操作。
2. 二分查找优化：每个节点存储有序数据，因此区间查询时可以利用二分查找优化查询速度。
3. 适用于静态数据：归并树的构建开销较大，适合于处理固定不变的静态数据集。

三、操作

• 构建树：自底向上，先将叶节点数据排序，再合并生成上层节点的有序区间数据，时间复杂度为 O(n log n)。
• 查询：递归查询左右子节点的区间内数据，复杂度 O(log n)。
• 动态更新：不支持动态更新，若数据变动需重新构建归并树。

四、优缺点

• 优点：支持高效的静态区间查询，利用二分查找和分治思想，提升区间最值和频数查询效率。
• 缺点：不支持动态更新，适用于不变的数据集；构建复杂度较高。

五、应用

• 区间频数统计：如需要统计区间内某元素出现的次数。
• 区间最值/特定范围查询：适合静态数据的区间最大值、最小值、排名等查询操作。

六、示例代码（Java 实现）

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;class MergeTree {private List<Integer>[] tree;private int size;public MergeTree(int[] data) {size = data.length;tree = new ArrayList[4 * size];buildTree(data, 0, 0, size - 1);}// 构建归并树private void buildTree(int[] data, int node, int start, int end) {tree[node] = new ArrayList<>();if (start == end) {tree[node].add(data[start]);} else {int mid = (start + end) / 2;buildTree(data, 2 * node + 1, start, mid);buildTree(data, 2 * node + 2, mid + 1, end);merge(tree[2 * node + 1], tree[2 * node + 2], tree[node]);}}// 合并子数组private void merge(List<Integer> left, List<Integer> right, List<Integer> merged) {int i = 0, j = 0;while (i < left.size() && j < right.size()) {if (left.get(i) < right.get(j)) {merged.add(left.get(i++));} else {merged.add(right.get(j++));}}while (i < left.size()) merged.add(left.get(i++));while (j < right.size()) merged.add(right.get(j++));}// 查询区间内小于给定值的元素个数public int query(int left, int right, int k) {return queryRecursive(0, 0, size - 1, left, right, k);}private int queryRecursive(int node, int start, int end, int left, int right, int k) {if (right < start || end < left) {return 0;}if (left <= start && end <= right) {return countLessThan(tree[node], k);}int mid = (start + end) / 2;return queryRecursive(2 * node + 1, start, mid, left, right, k) +queryRecursive(2 * node + 2, mid + 1, end, left, right, k);}private int countLessThan(List<Integer> list, int k) {int l = 0, r = list.size() - 1;while (l <= r) {int mid = (l + r) / 2;if (list.get(mid) < k) {l = mid + 1;} else {r = mid - 1;}}return l;}
}

总结比较

数据结构	特点	优点	缺点	应用场景
Fenwick 树	使用数组实现的树结构，支持前缀和	动态更新和查询效率高	不支持复杂区间查询	区间和、统计数据
归并树	每个节点存储有序区间，支持二分查找	高效区间查询和频数统计	不支持动态更新，构建耗时	静态数据集的区间查询和统计

Fenwick 树与归并树都在区间查询中发挥着重要作用，但其适用场景不同。Fenwick 树适用于动态更新场景，而归并树适用于静态数据集的复杂查询。