非线性数据结构之树
Fenwick 树（树状数组）
Fenwick 树（或称树状数组）是一种支持高效前缀和（Prefix Sum）查询和更新的数据结构。Fenwick 树的应用较广泛，特别是在处理频繁变动的区间数据时，能在 O(log n) 时间内完成查询和更新操作。
一、定义
Fenwick 树是一种使用数组结构来实现的树结构，每个元素 i 存储的值等于该位置索引的二进制表示中“最后一个 1”位所代表的区间和。例如，若 i = 6（110），则树状数组在位置 6 处存储了从索引 5 到 6 的区间和。
二、特点
- 空间复杂度低：只需要一个与原数组相同大小的树状数组来记录前缀和。
- 支持动态更新：更新某一元素后，只需更新相关节点而不影响其他数据，使其在实时更新数据的场景下高效。
- 前缀和查询高效：每次查询通过递减“最后一个 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）
归并树是一种用于解决特定区间查询的树结构，通常用于静态数据集的查询优化，如处理区间最值查询、频数查询等。
一、定义
归并树是将数据分块并排序构建的一种树结构。每个节点存储一段区间，并按值排序，以方便二分查找等操作。构建过程中，归并树不断将左右子区间归并成有序的区间数组，逐层合并，形成一棵完全二叉树。
二、特点
- 多种区间查询：支持区间求和、区间最值等操作。
- 二分查找优化：每个节点存储有序数据，因此区间查询时可以利用二分查找优化查询速度。
- 适用于静态数据：归并树的构建开销较大，适合于处理固定不变的静态数据集。
三、操作
- 构建树：自底向上，先将叶节点数据排序，再合并生成上层节点的有序区间数据，时间复杂度为 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 树适用于动态更新场景，而归并树适用于静态数据集的复杂查询。
原文地址：https://blog.csdn.net/m0_61840987/article/details/143396134
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！