深入解析树状数组：核心逻辑与高效算法

核心逻辑与数学原理

树状数组（Binary Indexed Tree, BIT，亦称 Fenwick Tree）的核心逻辑在于利用正整数的二进制拆分，实现前缀和的动态维护。它能在 $O(\log N)$ 的时间复杂度内完成“单点修改”与“区间查询”，从根本上打破了普通数组“修改 $O(1)$、查询 $O(N)$”或前缀和数组“修改 $O(N)$、查询 $O(1)$”的常数僵局。

1. $\text{lowbit}$ 的数学机理

定义函数 $\text{lowbit}(x)$ 为非负整数 $x$ 在二进制表示下“最低位的 $1$ 及其后面的 $0$”所代表的数值。利用计算机底层的补码（Two's Complement）机制，正数 $x$ 的源码与其相反数 $-x$ 的补码执行按位与运算，可瞬时提取该特征位。其数学恒等式为：

$$\text{lowbit}(x) = x \ \& \ (-x)$$

证明：设 $x$ 的二进制最低位 $1$ 在第 $k$ 位，则 $x$ 可表示为 $\dots 10\dots0$（后面有 $k$ 个 $0$）。$-x$ 的补码为 $x$ 的按位取反再加 $1$。取反后变为 $\dots 01\dots1$，加 $1$ 后第 $k$ 位及其低位因进位变为 $10\dots0$，而高位与 $x$ 完全相反。两者执行 & 运算，高位全清零，仅保留第 $k$ 位的 $1$。

2. 树形覆盖拓扑

树状数组的存储阵列 tree[x] 并非记录单点值，而是负责维护原数组 A[] 中一段长度为 $\text{lowbit}(x)$ 的连续区间的和。其管辖的左闭右闭区间边界为：

$$\text{tree}[x] = \sum_{i = x - \text{lowbit}(x) + 1}^{x} A[i]$$

根据此拓扑几何关系，演化出两条本质的拓扑链条：

直系父亲链（用于单点修改）：节点 $x$ 的父亲节点下标为 $x + \text{lowbit}(x)$。
前缀拆分链（用于区间查询）：计算前缀和 $S_x$ 时，下一个需要累加的独立区间块首节点下标为 $x - \text{lowbit}(x)$。

状态设计与算法推导

树状数组的状态仅需一个与原数组等大的静态空间 tree[]，有效下标从 $1$ 开始。

1. 单点修改（Add）算法推导

当原数组元素 $A[x]$ 增加 $\Delta$ 时，根据树形拓扑结构，所有管辖了 $A[x]$ 的祖先节点 tree 值都必须同步追加 $\Delta$。

状态转移路径：从 $x$ 开始，每次通过 $x \leftarrow x + \text{lowbit}(x)$ 向上跳跃，直到超越全局边界 $N$。
复杂度推导：由于 $x$ 每次加上 $\text{lowbit}(x)$，其二进制表示中尾部的 $1$ 必然不断向高位推进，本质上是在完全二叉树上沿单条链向上攀升，迭代次数严格约束在 $\lfloor \log_2 N \rfloor$ 内，复杂度为 $O(\log N)$。

2. 前缀查询（Query）算法推导

要求解前缀和 $S_x = \sum_{i=1}^x A[i]$，利用二进制拆分，可将大区间 $[1, x]$ 离散化地拆分为若干个由 tree 数组直接维护的独立子区间之和。

状态转移路径：累加当前的 tree[x]，随后通过 $x \leftarrow x - \text{lowbit}(x)$ 剥离掉当前最低位的 $1$，切入前一个不相交的独立维护区间，直到 $x = 0$。
区间查询推广：利用前缀和的容斥原理，任意闭区间 $[L, R]$ 的区间和可一针见血地转化为两个前缀和的差值：

$$\text{Sum}(L, R) = \text{Query}(R) - \text{Query}(L - 1)$$

复杂度推导：$x$ 每次减去 $\text{lowbit}(x)$，等价于将其二进制表示中的 $1$ 从低到高逐个清空。迭代次数等于 $x$ 的二进制中 $1$ 的个数（Popcount），最坏复杂度为 $O(\log N)$。

C++ 标准源码

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 500005;

struct BinaryIndexedTree {
    int tree[MAXN];
    int n;

    // 显式初始化
    void init(int _n) {
        this->n = _n;
        // 关键规范：在多组数据测试中，务必显式清理整个有效空间
        std::fill(tree, tree + n + 1, 0);
    }

    // 内联 lowbit 运算，压制函数调用常数开销
    inline int lowbit(int x) const {
        return x & (-x);
    }

    // 单点修改：在位置 x 加上 val
    void add(int x, int val) {
        // 致命踩坑点：树状数组下标严格从 1 开始，若传入 x = 0 会引发 x + lowbit(0) = 0 的死循环
        for (; x <= n; x += lowbit(x)) {
            tree[x] += val;
        }
    }

    // 查询前缀和：计算 [1, x] 的区间和
    int query(int x) const {
        int sum = 0;
        // 退出条件为 x > 0，x = 0 时自增或自减链条终止
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }

    // 区间查询：计算 [l, r] 的标准区间和
    int query_range(int l, int r) const {
        if (l > r) return 0;
        // 致命踩坑点：利用容斥计算区间时，左端点必须是 l - 1，且需注意边界 l=1 时 query(0) 正确返回 0
        return query(r) - query(l - 1);
    }
};

int main() {
    // 强制解除 I/O 绑定，榨干读写性能
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    if (std::cin >> n >> m) {
        BinaryIndexedTree bit;
        bit.init(n);

        for (int i = 1; i <= n; ++i) {
            int val;
            std::cin >> val;
            bit.add(i, val); // 初始建树，单次 $O(\log N)$，总建树 $O(N \log N)$
        }

        for (int i = 0; i < m; ++i) {
            int type, x, y;
            std::cin >> type >> x >> y;
            if (type == 1) {
                bit.add(x, y); // 单点修改
            } else if (type == 2) {
                std::cout << bit.query_range(x, y) << "\n"; // 区间查询
            }
        }
    }

    return 0;
}

NOIP 实战避坑指南

传入下标 0 导致死循环击穿系统栈 树状数组的全部算术逻辑建立在下标 $\ge 1$ 的正整数集合上。如果在代码中错误地触发了 add(0, val) 或 query(0)：由于 $\text{lowbit}(0) = 0 \ \& \ (-0) = 0$，执行 x += lowbit(x) 相当于 0 += 0。for 循环的状态永远无法发生实质性跃迁，程序在评测机上会卡死并触发 Time Limit Exceeded。铁律：凡是涉及离散化坐标或计数模型，必须整体右移一位，保证树状数组输入端点 $\ge 1$。
数据未做 long long 转化导致区间求和符号位溢出 在诸如“区间动态频次统计”或大数值区间和问题中，原数组单点值虽然在 int 范围内，但经过数十万次 add 操作后，前缀和 tree[x] 的真实值会轻松击穿 $2^{31}-1$。若执着于使用 int tree[]，在执行 query(r) - query(l-1) 时会发生算术整型溢出，数值直接变为负数，输出诡异的错误结果。警惕：只要有频繁累加或区间求和要求，tree 数组与 query 函数返回值一律锁死 `long long`。

经典 NOIP/洛谷真题

1. 洛谷 P3374 【模板】树状数组 1

题意描述：已知一个数列，你需要进行两种操作：一是将某一个数加上 $x$，二是求出某区间内所有数的和。
问题本质：最标准的动态单点修改与区间和查询。
核心解题思路：此题为树状数组的底层直接映射。使用静态 tree 数组，读入初始序列时遍历执行 add(i, a[i]) 完成基础拓扑填充。后续面对修改操作直接调用 add(x, k)，面对询问操作直接输出 query_range(x, y)，用标准的 $O(\log N)$ 算术跃迁完美通过全部评测点。

2. 洛谷 P3368 【模板】树状数组 2

题意描述：已知一个数列，你需要进行两种操作：一是将某区间每一个数加上 $x$，二是求出某一个数的值。
问题本质：区间修改与单点查询的对偶转化。
核心解题思路：引入核心数学工具——差分（Difference）。设差分数组 $D[i] = A[i] - A[i-1]$。此时，对原数组 $A$ 在区间 $[L, R]$ 整体加上 $v$ 的区间修改操作，在差分数组上等价于两点变动：$D[L] \leftarrow D[L] + v$ 且 $D[R+1] \leftarrow D[R+1] - v$。而求原数组单点值 $A[x]$ 的操作，根据差分定义有 $A[x] = \sum_{i=1}^x D[i]$，即等价于求差分数组 $D$ 的前缀和。因此，用树状数组直接去维护差分数组 $D$，即可将“区间改、单点查”完美逆转为标准的树状数组“单点改、前缀查”模型，复杂度仍为硬核的 $O(\log N)$。