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

树状数组（Fenwick Tree）是一种利用二进制低位特性（lowbit）高效维护序列前缀和的数据结构。相比线段树，其常数极小、代码极短、空间减半，在算法竞赛与面试中应用极其广泛。

1. 树状数组的数学原理与正确性证明¶

1.1 `lowbit` 运算性质与管辖区间定义¶

计算机中负数采用二进制补码表示，满足 \(-x = \sim x + 1\)。

设正整数 \(x\) 的二进制表示中最低位的 \(1\) 处于第 \(k\) 位（从 \(0\) 开始计数），则 \(x\) 可唯一表示为：

\[ x = A \cdot 2^{k+1} + 2^k \]

对其按位取反得到：

\[ \sim x = (\sim A) \cdot 2^{k+1} + \sum_{j=0}^{k-1} 2^j = (\sim A) \cdot 2^{k+1} + 2^k - 1 \]

末位加 1 产生进位：

\[ -x = \sim x + 1 = (\sim A) \cdot 2^{k+1} + 2^k \]

将 \(x\) 与 \(-x\) 进行按位与运算，由于 \(A \ \& \ (\sim A) = 0\)，高位全部清零，仅保留最低位的 \(1\)：

\[ \text{lowbit}(x) = x \ \& \ (-x) = 2^k \]

管辖区间定义：在树状数组中，下标为 \(x\) 的节点 tree[x] 存储的是原数组在一个长度为 \(\text{lowbit}(x)\)、以 \(x\) 为右端点的左开右闭区间内的元素之和：

\[ I(x) = (x - \text{lowbit}(x), x] = [x - \text{lowbit}(x) + 1, x] \]

\[ \text{tree}[x] = \sum_{i \in I(x)} a[i] = \sum_{i = x - \text{lowbit}(x) + 1}^{x} a[i] \]

1.2 前缀和查询算法的正确性证明¶

算法流程：求前缀和 \(S(x) = \sum_{i=1}^x a[i]\) 时，初始令 \(\text{sum} = 0\)；在 \(x > 0\) 时循环执行：

\[ \text{sum} \leftarrow \text{sum} + \text{tree}[x], \quad x \leftarrow x - \text{lowbit}(x) \]

【定理 1（前缀区间的不重不漏完全划分）】 对于任意正整数 \(x\)，上述循环生成的区间序列 \(\{I(x_0), I(x_1), \dots, I(x_{m-1})\}\) 构成了连续区间 \((0, x] = [1, x]\) 的一个互不相交的完全划分（Disjoint Partition）。

【数学归纳证明】 设 \(x\) 的二进制表示中所有为 1 的位从高到低依次为 \(p_1 > p_2 > \dots > p_m \ge 0\)，即：

\[ x = \sum_{j=1}^m 2^{p_j} \]

其中共有 \(m = \text{popcount}(x)\) 个非零二进制位。

第一步：当前最低位为 \(p_m\)，即 \(\text{lowbit}(x) = 2^{p_m}\)。对应管辖区间为：

\[ I_1 = (x - 2^{p_m}, x] = \left( \sum_{j=1}^{m-1} 2^{p_j}, \sum_{j=1}^m 2^{p_j} \right] \]

更新后：\(x_1 = x - \text{lowbit}(x) = \sum_{j=1}^{m-1} 2^{p_j}\)。
第二步：当前最低位为 \(p_{m-1}\)，\(\text{lowbit}(x_1) = 2^{p_{m-1}}\)。对应管辖区间为：

\[ I_2 = (x_1 - 2^{p_{m-1}}, x_1] = \left( \sum_{j=1}^{m-2} 2^{p_j}, \sum_{j=1}^{m-1} 2^{p_j} \right] \]

注意：\(I_2\) 的右端点恰好等于 \(I_1\) 的左端点！
第 \(k\) 步（归纳步）：以此类推，对任意第 \(k\) 步（\(1 \le k \le m\)），所取区间为：

\[ I_k = \left( \sum_{j=1}^{m-k} 2^{p_j}, \sum_{j=1}^{m-k+1} 2^{p_j} \right] \]

所有区间首尾紧密相接，且两两互不相交（\(I_a \cap I_b = \emptyset, \forall a \neq b\)）。
终止状态：当 \(k = m\) 时，更新后的左端点为 \(\sum_{j=1}^0 2^{p_j} = 0\)，循环终止于 \(x = 0\)。

将这 \(m\) 个互不相交的区间并起来：

\[ \bigcup_{k=1}^m I_k = (0, x] = [1, x] \]

由于每个管辖区间的元素和均准确存储在对应的 tree[x_k] 中，累加和严格满足：

\[ \sum_{k=1}^m \text{tree}[x_k] = \sum_{k=1}^m \sum_{i \in I_k} a[i] = \sum_{i=1}^x a[i] \]

且总循环次数恰好为 \(m = \text{popcount}(x) \le \lfloor \log_2 x \rfloor + 1\)，算法时间复杂度为 \(\mathcal{O}(\log n)\)。\(\blacksquare\)

1.3 单点修改算法的正确性证明¶

算法流程：当原数组元素 \(a[i]\) 增加 \(\Delta\) 时，从 \(x = i\) 开始，循环执行：

\[ \text{tree}[x] \leftarrow \text{tree}[x] + \Delta, \quad x \leftarrow x + \text{lowbit}(x) \]

直到 \(x > n\) 结束。

核心命题：该算法必须且仅须更新所有满足 \(i \in I(y)\)（即 \(y - \text{lowbit}(y) < i \le y\)）的节点 \(y\)。我们需要证明：序列 \(x_{k+1} = x_k + \text{lowbit}(x_k)\) 包含且仅包含所有管辖 \(i\) 的节点，且不重不漏。

【定理 2（树形父子包含定理）】 定义节点 \(x\) 的直接父节点为 \(\text{parent}(x) = x + \text{lowbit}(x)\)，则子节点的管辖区间严格被父节点的管辖区间真包含：

\[ I(x) \subset I(\text{parent}(x)) \]

【证明】 设 \(x = A \cdot 2^{k+1} + 2^k\)（即 \(\text{lowbit}(x) = 2^k\)）。此时子节点管辖区间为：

\[ I(x) = (x - 2^k, x] = (A \cdot 2^{k+1}, A \cdot 2^{k+1} + 2^k] \]

计算直接父节点编号：

\[ \text{parent}(x) = x + 2^k = (A + 1) \cdot 2^{k+1} \]

由于 \(\text{parent}(x)\) 是 \(2^{k+1}\) 的倍数，其最低非零位权值至少为 \(2^{k+1}\)，记 \(\text{lowbit}(\text{parent}(x)) = 2^r\)（其中 \(r \ge k + 1\)）。

考查父节点的管辖区间 \(I(\text{parent}(x)) = (\text{parent}(x) - 2^r, \text{parent}(x)]\)：

左端点比较：

\[ \text{parent}(x) - 2^r = (A + 1) \cdot 2^{k+1} - 2^r \le (A + 1) \cdot 2^{k+1} - 2^{k+1} = A \cdot 2^{k+1} \]

父节点左端点 \(\le\) 子节点左端点。
右端点比较：

\[ \text{parent}(x) = (A + 1) \cdot 2^{k+1} > A \cdot 2^{k+1} + 2^k = x \]

父节点右端点严格大于子节点右端点。

因此，\(I(x) \subset I(\text{parent}(x))\)。由集合包含关系的传递性，若 \(i \in I(x)\)，则必有 \(i \in I(\text{parent}(x))\)。\(\blacksquare\)

【定理 3（最小性与无遗漏定理）】 若 \(i \in I(x)\)，则在开区间 \((x, \text{parent}(x))\) 内不存在任何整数节点 \(z\) 使得 \(i \in I(z)\)。

【证明】 任意选取整数 \(z \in (x, x + 2^k)\)，可将 \(z\) 写作：

\[ z = x + d, \quad 0 < d < 2^k \]

因为 \(x\) 是 \(2^{k+1}\) 或 \(2^k\) 的倍数，而 \(d < 2^k\)，所以 \(z\) 的最低有效位必然完全由 \(d\) 的最低有效位决定：

\[ \text{lowbit}(z) = \text{lowbit}(d) \le d < 2^k \]

考查节点 \(z\) 的管辖区间左端点：

\[ z - \text{lowbit}(z) \ge z - d = x \]

由于已知 \(i \in I(x) \implies i \le x\)，因此必定有：

\[ i \le x \le z - \text{lowbit}(z) \]

这说明下标 \(i\) 必定落在 \(z\) 的管辖区间左端点的左侧（或重合），即 \(i \notin I(z)\)！

【结论】 任何严格介于 \(x\) 与 \(\text{parent}(x)\) 之间的节点都不可能包含 \(i\)。因此，包含下标 \(i\) 的下一个最小节点唯一且必须是 \(\text{parent}(x) = x + \text{lowbit}(x)\)。从 \(i\) 开始沿父节点指针向上遍历，既不会跳过任何包含 \(i\) 的节点，也不会访问任何无关节点，严格保证了单点修改的正确性。\(\blacksquare\)

1.4 倍增二分求第 \(k\) 小的正确性证明¶

在权值树状数组中，若要求满足前缀和 \(\ge k\) 的最小下标，传统外部二分需要 \(\mathcal{O}(\log^2 n)\)。而利用树状数组的二进制结构直接倍增跳步仅需 \(\mathcal{O}(\log n)\)。

【核心引理（倍增区间对齐性质）】 若当前确定的下标 \(idx\) 是 \(2^{p+1}\) 的倍数（即 \(idx\) 的二进制表示中低于 \(p+1\) 的位均为 0），尝试向右探测步长 \(2^p\)：

\[ \text{lowbit}(idx + 2^p) = 2^p \]

根据树状数组管辖区间的定义：

\[ I(idx + 2^p) = \big((idx + 2^p) - 2^p, idx + 2^p\big] = (idx, idx + 2^p] \]

这意味着：节点 tree[idx + 2^p] 内部保存的恰好就是连续开区间 \((idx, idx + 2^p]\) 内部的原数组元素和，无需通过任何减法即可在 \(\mathcal{O}(1)\) 内获得此区间的累积和！

若 tree[idx + 2^p] < k：说明跨过整个 \((idx, idx + 2^p]\) 区间后的总和依然达不到 \(k\)，则第 \(k\) 小元素必定处于该区间右侧，可以安全跳步：令 \(idx \leftarrow idx + 2^p\) 并扣除该区间贡献 \(k \leftarrow k - \text{tree}[idx]\)；
若 tree[idx + 2^p] >= k：说明目标元素就落在当前探测区间内部，不进行跳步，步长折半继续细化探测。

从最高有效位依次尝试至最低位，严格执行 \(\lfloor \log_2 n \rfloor + 1\) 次，最终 \(idx + 1\) 即为目标答案。

2. 基础树状数组 (单点修改 + 区间查询 + 倍增二分)¶

标准 1-indexed 树状数组，支持 \(\mathcal{O}(\log n)\) 的单点增减、前缀和查询，以及利用二进制跳步在 \(\mathcal{O}(\log n)\) 时间内查找第 \(k\) 小元素（无需外部二分的 \(\mathcal{O}(\log^2 n)\)）。

#include <vector>

template <typename T = long long>
struct Fenwick {
    int n;
    std::vector<T> tree;

    Fenwick(int n) : n(n), tree(n + 1, 0) {}

    static inline int lowbit(int x) {
        return x & (-x);
    }

    // 单点增加: a[i] += delta (1 <= i <= n)
    void add(int i, T delta) {
        for (; i <= n; i += lowbit(i)) {
            tree[i] += delta;
        }
    }

    // 前缀和查询: sum(a[1...i])
    T query(int i) const {
        T sum = 0;
        for (; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }

    // 区间和查询: sum(a[l...r])
    T query(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }

    // 倍增二分: 寻找满足 query(idx) >= k 的最小下标 idx
    // 前提: 数组元素非负 (前缀和单调不降)。复杂度严格 O(log n)
    int find_kth(T k) const {
        int idx = 0;
        // 从最高有效二进制位向下尝试跳步
        for (int i = 1 << (31 - __builtin_clz(n)); i > 0; i >>= 1) {
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

3. 高阶树状数组 (区间修改 + 区间查询)¶

利用差分数组 \(d[i] = a[i] - a[i-1]\)，有：

\[ \sum_{i=1}^{p} a[i] = \sum_{i=1}^{p} \sum_{j=1}^{i} d[j] = \sum_{i=1}^{p} (p - i + 1) d[i] = (p + 1) \sum_{i=1}^{p} d[i] - \sum_{i=1}^{p} (i \cdot d[i]) \]

因此只需维护两个树状数组：\(t_1\) 维护 \(d[i]\)，\(t_2\) 维护 \(i \cdot d[i]\)。

template <typename T = long long>
struct RangeFenwick {
    int n;
    Fenwick<T> t1, t2; // t1 维护 d[i], t2 维护 i * d[i]

    RangeFenwick(int n) : n(n), t1(n), t2(n) {}

    // 区间增加: a[l...r] += delta
    void range_add(int l, int r, T delta) {
        t1.add(l, delta);
        t1.add(r + 1, -delta);
        t2.add(l, delta * l);
        t2.add(r + 1, -delta * (r + 1));
    }

    // 前缀和: sum(a[1...i])
    T query(int i) const {
        return (i + 1) * t1.query(i) - t2.query(i);
    }

    // 区间和: sum(a[l...r])
    T range_query(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

4. 二维树状数组 (2D Fenwick Tree)¶

用于二维网格上的单点修改与矩形区域和查询，单次操作复杂度均为 \(\mathcal{O}(\log R \log C)\)。

template <typename T = long long>
struct Fenwick2D {
    int n, m;
    std::vector<std::vector<T>> tree;

    Fenwick2D(int n, int m) : n(n), m(m), tree(n + 1, std::vector<T>(m + 1, 0)) {}

    static inline int lowbit(int x) { return x & (-x); }

    void add(int r, int c, T delta) {
        for (int i = r; i <= n; i += lowbit(i)) {
            for (int j = c; j <= m; j += lowbit(j)) {
                tree[i][j] += delta;
            }
        }
    }

    // 矩阵前缀和: (1, 1) 到 (r, c)
    T query(int r, int c) const {
        T sum = 0;
        for (int i = r; i > 0; i -= lowbit(i)) {
            for (int j = c; j > 0; j -= lowbit(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }

    // 矩形区域和: (r1, c1) 到 (r2, c2)
    T query(int r1, int c1, int r2, int c2) const {
        if (r1 > r2 || c1 > c2) return 0;
        return query(r2, c2) - query(r1 - 1, c2) - query(r2, c1 - 1) + query(r1 - 1, c1 - 1);
    }
};

5. 权值树状数组与离散化¶

求解序列逆序对¶

将树状数组用于离散化后的元素频次统计。从后往前扫描，查询并累加在当前元素之后出现的、严格小于当前值的元素个数。

#include <vector>
#include <algorithm>

long long count_inversions(std::vector<int> &a) {
    int n = a.size();
    std::vector<int> vals = a;
    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());

    Fenwick<int> bit(vals.size());
    long long inversions = 0;
    for (int i = n - 1; i >= 0; --i) {
        int rank = std::lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
        inversions += bit.query(rank - 1);
        bit.add(rank, 1);
    }
    return inversions;
}

6. LeetCode 经典好题与模型精选¶

树状数组在 LeetCode 题目中主要有五大应用方向：单点/区间求和维护、权值树状数组逆序对变种、下标映射与三元组计数、贪心位移消去模拟以及树状数组优化 DP。

LeetCode 307 - 区域和检索 - 数组可修改 (Range Sum Query - Mutable) 中等

提示

树状数组的入门基准题。初始化时建树可采用 \(\mathcal{O}(N)\) 线性递推：遍历 \(i\)，直接令 tree[i + lowbit(i)] += tree[i]。单点更新差值 \(\Delta = val - nums[i]\)，并在 \(\mathcal{O}(\log N)\) 内更新树状数组与原数组；区间查询调用 query(r) - query(l - 1)。
LeetCode 315 - 计算右侧小于当前元素的个数 (Count of Smaller Numbers After Self) 困难
提示

权值树状数组标杆题。
- 数值范围较大（存在负数），先将全数组去重排序进行离散化，映射到 \([1, M]\)（\(M \le N\)）。
- 从右至左反向遍历数组：对于当前元素 \(x\)（离散化后排名为 \(rank\)），当前树状数组已维护了其右侧所有元素的出现频次。
- 调用 bit.query(rank - 1) 即可在 \(\mathcal{O}(\log M)\) 内求得右侧严格小于 \(x\) 的元素个数。
- 随后执行 bit.add(rank, 1) 将当前元素计入频次。总体时间复杂度 \(\mathcal{O}(N \log N)\)。
LeetCode 493 - 翻转对 (Reverse Pairs) 困难
提示

条件为 \(i < j\) 且 \(nums[i] > 2 \cdot nums[j]\)。
- 乘 2 容易越界，需使用 long long。
- 联合离散化技巧：将数组中的所有 \(nums[i]\) 以及所有 \(2 \cdot nums[i]\) 一同放入离散化列表中排序去重。
- 从右向左遍历数组：
- 寻找当前 \(nums[i]\) 在离散化列表中的排名 \(rank_1\)；
- 查询树状数组中严格小于 \(nums[i]\) 的“翻倍后数值”数量，即 \(2 \cdot nums[j] < nums[i]\) 的 \(j\) 的个数；
- 随后将 \(2 \cdot nums[i]\) 对应的离散化排名 \(rank_2\) 在树状数组中增加 1。
LeetCode 1649 - 通过指令创建有序数组 (Create Sorted Array through Instructions) 困难
提示

每次插入数字 \(x\) 时，代价为 \(\min(\text{严格小于 } x \text{ 的个数}, \text{严格大于 } x \text{ 的个数})\)。
- 元素大小不超过 \(10^5\)，可直接开大小为 \(100001\) 的树状数组（无需离散化）。
- 设当前总共已插入 \(i\) 个数：
- 严格小于 \(x\) 的个数为 bit.query(x - 1)；
- 严格大于 \(x\) 的个数为 \(i - \text{bit.query}(x)\)；
- 累加代价 \(\min(\text{less}, \text{greater})\) 并对 \(10^9 + 7\) 取模；
- 执行 bit.add(x, 1)。
LeetCode 2179 - 统计数组中好三元组数目 (Count Good Triplets in an Array) 困难
提示

下标排列映射 + 中间元枚举 + 容斥计数。
- 两个数组均为 \(0 \sim n-1\) 的排列。记 \(pos[v]\) 为元素 \(v\) 在 \(nums2\) 中的下标。
- 将 \(nums1\) 中的每个元素 \(nums1[i]\) 替换为它在 \(nums2\) 中的下标 \(P_i = pos[nums1[i]]\)。问题等价于：在序列 \(P\) 中寻找上升三元组（\(i < j < k\) 且 \(P_i < P_j < P_k\)）。
- 枚举中间元素下标 \(j\)（对应数值 \(x = P_j\)）：
- 左侧小于 \(x\) 的元素个数 \(L\)：用权值树状数组动态维护 \(P_0 \dots P_{j-1}\) 的出现情况，\(L = \text{bit.query}(x)\)；
- 右侧大于 \(x\) 的元素个数 \(R\)：利用全集容斥——在整个排列中大于 \(x\) 的数共有 \(n - 1 - x\) 个，其中处于 \(j\) 左侧的大于 \(x\) 的数有 \((j - L)\) 个。因此处于 \(j\) 右侧的大于 \(x\) 的数恰有 \(R = (n - 1 - x) - (j - L)\) 个；
- 中间元 \(j\) 对答案的贡献为 \(L \times R\)，累加即为总数。
LeetCode 1505 - 最多 K 次交换相邻数位后得到的最小整数 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits) 困难
提示

贪心选位 + 树状数组动态统计位移偏移量。
- 为了让数字字典序最小，应尽量把更小的数位移到最前面。
- 用 10 个队列 pos[0...9] 预存数位 \(0 \sim 9\) 在原字符串中出现的全部下标（均为单调递增）。
- 从位置 1 到 \(n\) 依次确定最终字符：
- 依次尝试数位 \(d \in [0, 9]\)；
- 若队列 pos[d] 不为空，设其队首原下标为 \(p\)。由于在 \(p\) 之前已经有若干数位被移走了，数位 \(p\) 当前的实际位置为 \(p - \text{bit.query}(p)\)；
- 把它移到当前确定位置所需的交换次数就是真实位移步数。若该步数 \(\le k\)：
  - 消耗相应步数 \(k \mathrel{-}= \text{cost}\)；
  - 将数位 \(d\) 放入答案，弹出队首；
  - 在树状数组中执行 bit.add(p, 1)（标记该位置的数已被移走，后续所有后面的数真实坐标都左移 1）；
  - 选定完毕，进入下一位的确定。
LeetCode 1626 - 无矛盾的最佳球队 (Best Team With No Conflicts) 中等

提示

树状数组优化动态规划。按照 (年龄, 分数) 双关键字升序排序。排序后，后面的球员年龄必然 \(\ge\) 前面的球员。要使球队无矛盾，排序后被选入的球员分数序列必须是单调不降的。问题转化为在分数维度上求带权最大上升子序列和。设 \(dp[score]\) 为以分数为 \(score\) 结尾的球队最大得分之和，状态转移方程为：

\[ dp[score] = score + \max_{s \le score} dp[s] \]

使用树状数组维护前缀最大值（query_max(score)），每次转移 \(\mathcal{O}(\log M)\)，更新 update_max(score, val) \(\mathcal{O}(\log M)\)。将总复杂度从 \(\mathcal{O}(N^2)\) 优化至 \(\mathcal{O}(N \log M)\)。
LeetCode 2659 - 将数组清空 (Make Array Empty) 困难
提示

循环数组模拟 + 树状数组统计已删除元素。
- 按照数值大小升序排序，确定删除顺序。
- 设上一次删除的位置为 \(prev\)，当前要删除的目标位置为 \(curr\)：
- 若 \(curr > prev\)：指针在环形数组中顺次向前移动，移动步数等于两点间的原元素个数 \((curr - prev)\) 减去该区间内已经删除的元素个数（树状数组区间查询）；
- 若 \(curr < prev\)：指针绕回一圈，移动步数等于从 \(prev\) 到数组末尾的未删元素数加上从开头到 \(curr\) 的未删元素数；
- 计算完步数后累加到答案，并在树状数组中标记位置 \(curr\) 已被删除（bit.add(curr, 1)）。
LeetCode 308 - 二维区域和检索 - 可变 (Range Sum Query 2D - Mutable) 困难

提示

二维树状数组模板题。单点修改 update(row, col, val) 计算增量 \(\Delta = val - matrix[row][col]\)，在二维树状数组对应坐标累加。区域和检索通过二维前缀和容斥原理求解：

\[ \text{sum} = Q(r_2, c_2) - Q(r_1 - 1, c_2) - Q(r_2, c_1 - 1) + Q(r_1 - 1, c_1 - 1) \]

单次修改与查询耗时均为 \(\mathcal{O}(\log R \log C)\)。