树状数组（Fenwick Tree）详解：从原理到实战

1. 什么是树状数组树状数组Fenwick Tree是一种用于高效处理前缀和查询与单点更新的数据结构。它能在 O(log n) 时间内完成这两种操作空间复杂度为 O(n)比朴素的前缀和数组更新 O(n)查询 O(1)和线段树功能更强但代码更复杂在特定场景下更加简洁高效。树状数组由 Peter Fenwick 于 1994 年提出主要用于解决以下问题频繁修改数组中的某个元素频繁查询数组某个前缀区间的和2. 核心原理2.1 二进制低位技术Lowbit树状数组的核心是一个巧妙的二进制操作lowbit(x) x -x。这个操作可以取出 x 二进制表示中最低位的 1 及其后面的 0。例如lowbit(6) lowbit(110₂) 10₂ 2lowbit(12) lowbit(1100₂) 100₂ 4这个操作决定了树状数组中每个元素管理的区间范围。2.2 树状数组的结构假设原数组为arr[1..n]通常下标从 1 开始树状数组tree[1..n]的每个元素tree[i]管理原数组的一段区间tree[i]管理原数组从i - lowbit(i) 1到i的元素和这种设计使得更新操作修改arr[i]时需要更新所有包含 i 的tree[j]通过j i lowbit(i)不断向上跳转查询操作查询前缀和sum[1..i]时通过i i - lowbit(i)不断向前累加3. 基本操作实现3.1 单点更新// 在位置 i 增加 delta void update(int i, int delta) { while (i n) { tree[i] delta; i lowbit(i); } }3.2 前缀和查询// 查询前缀和 sum[1..i] int query(int i) { int sum 0; while (i 0) { sum tree[i]; i - lowbit(i); } return sum; }3.3 区间和查询// 查询区间和 sum[l..r] int rangeQuery(int l, int r) { return query(r) - query(l - 1); }4. 初始化构建树状数组有多种初始化方式逐个插入对每个元素调用 update时间复杂度 O(n log n)前缀和预处理利用 tree[i] sum[i] - sum[i - lowbit(i)]时间复杂度 O(n)// 高效初始化 void init(int[] arr) { n arr.length; tree new int[n 1]; int[] prefix new int[n 1]; for (int i 1; i n; i) { prefix[i] prefix[i - 1] arr[i - 1]; tree[i] prefix[i] - prefix[i - lowbit(i)]; } }5. 实战应用场景5.1 逆序对问题树状数组可以高效统计逆序对数量int countInversions(int[] nums) { // 离散化处理 int[] sorted nums.clone(); Arrays.sort(sorted); MapInteger, Integer rank new HashMap(); for (int i 0; i sorted.length; i) { rank.put(sorted[i], i 1); } int count 0; FenwickTree ft new FenwickTree(nums.length); for (int i nums.length - 1; i 0; i--) { int r rank.get(nums[i]); count ft.query(r - 1); // 统计比当前数小的数量 ft.update(r, 1); } return count; }5.2 区间更新 单点查询通过差分数组技巧树状数组可以支持区间更新// 区间 [l, r] 每个元素增加 delta void rangeUpdate(int l, int r, int delta) { update(l, delta); update(r 1, -delta); } // 单点查询 int pointQuery(int i) { return query(i); }5.3 二维树状数组扩展到二维平面支持矩阵的子矩阵求和与单点更新class FenwickTree2D { private int[][] tree; private int rows, cols; public FenwickTree2D(int m, int n) { rows m; cols n; tree new int[m 1][n 1]; } void update(int x, int y, int delta) { for (int i x; i rows; i lowbit(i)) { for (int j y; j cols; j lowbit(j)) { tree[i][j] delta; } } } int query(int x, int y) { int sum 0; for (int i x; i 0; i - lowbit(i)) { for (int j y; j 0; j - lowbit(j)) { sum tree[i][j]; } } return sum; } }6. 与线段树的对比特性树状数组线段树代码复杂度简单约 20 行较复杂约 50-100 行时间复杂度O(log n) 更新/查询O(log n) 更新/查询空间复杂度O(n)O(4n)功能范围前缀和、逆序对、差分任意区间操作最大/最小值、区间修改等适用场景前缀和频繁操作复杂区间查询与更新7. 常见问题与优化7.1 下标从 1 开始树状数组通常下标从 1 开始因为 lowbit(0) 0 会导致死循环。实际使用时需要注意下标转换。7.2 离散化技巧当数值范围很大但数据量不大时可以通过离散化将原始值映射到紧凑的整数区间减少树状数组大小。7.3 负数和浮点数处理树状数组本身支持负数和浮点数但需要注意更新时 delta 可以是负数查询结果可能溢出需要使用更大的数据类型如 long8. 总结树状数组是一种优雅高效的数据结构特别适合处理前缀和相关的动态统计问题。它的核心优势在于代码简洁核心操作仅需几行代码效率高O(log n) 的时间复杂度满足大多数竞赛和工程需求扩展性强可以扩展到二维、支持差分技巧等掌握树状数组的关键在于理解 lowbit 操作的原理以及如何通过二进制分解将前缀和分解为若干子区间的和。在实际应用中树状数组经常用于统计问题、逆序对计算、区间更新等场景是算法竞赛和面试中的常考知识点。