树状数组 (Fenwick Tree / Binary Indexed Tree)

支持单点修改与前缀和查询的高效二进制对数结构

什么是树状数组？

树状数组（Fenwick Tree）是一种通过二进制位运算设计的高效数据结构。它巧妙地利用二进制数的特性，将一个大小为 $N$ 的数组组织成森林或树状形态，使得区间前缀和查询与单点修改均能在 $O(\log N)$ 时间内完成。

核心二进制性质：lowbit

树状数组的核心支柱是 lowbit 操作。lowbit(x) 表示整型变量 $x$ 在二进制下最低位 1 所代表的数值：

lowbit(x) = x & (-x)
  • 区间负责制：节点 $C[i]$ 负责存储原数组中区间 $[i - \text{lowbit}(i) + 1, \, i]$ 的累加和。
  • 更新上浮路径：对位置 $i$ 进行修改时，下一个受影响的父节点为 i + lowbit(i).
  • 查询下沉路径：计算前 $i$ 项的前缀和时，下一个累加的前驱节点为 i - lowbit(i).
数据加载中...

C++ 核心源码对照

树状数组标准模板实现 (C++)
#define MAXN 100005
int c[MAXN], n;

// 1. lowbit: 获取最低位的 1 所代表的数值
inline int lowbit(int x) {
    return x & (-x);
}

// 2. 单点修改：原数组 A[i] 增加 delta，自底向上维护区间和 C
void update(int i, int delta) {
    for (; i <= n; i += lowbit(i)) {
        c[i] += delta;
    }
}

// 3. 前缀和查询：求和 A[1..i]，自顶向下合并区间
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) {
        sum += c[i];
    }
    return sum;
}

// 4. 区间和查询：求和 A[l..r]，利用差分性质完成计算
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

应用场景

  • 动态维护区间：需要在频繁更改数组单点值的同时，多次快速查询区间的和（如果不需要修改，直接使用静态前缀和更佳）。
  • 求逆序对：配合离散化，可以作为桶计数器，在 $O(N \log N)$ 复杂度内求出数组中所有的逆序对。
  • 二分查找位置：若要找前缀和大于等于某个值的最小位置，可以在树状数组上直接进行类似倍增的分治查找，耗时仅 $O(\log N)$。