树状数组

适用场景

树状数组（Fenwick Tree / Binary Indexed Tree）维护一个数组 $a$ ，支持：

单点修改： $a_p \gets a_p + v$ ；
前缀查询： $\sum_{i<p} a_i$ ，进而得到任意区间和。

只要运算满足结合律且可逆（加法、异或），就能求区间值；如果不可逆（例如 $\max$ ），只能求前缀值。

和线段树相比，树状数组的代码更短、常数更小，但能维护的信息种类更少。下面这些场景常用树状数组：

区间和、逆序对计数；
配合离散化做”值域上的计数”，例如统计比 $x$ 小的数有多少个；
二维数点（离线排序加一维树状数组）。

核心思路

定义 $\operatorname{lowbit}(x) = x \mathbin{\&} (-x)$ ，即 $x$ 二进制表示中最低位的 $1$ 对应的值。树状数组中下标从 $1$ 开始的 t[i] 保存区间 $(i - \operatorname{lowbit}(i),\ i]$ 内的和。

前缀查询： $[1, p]$ 可以拆成 t[p]、t[p - lowbit(p)]……每一步去掉最低位的 $1$ ，最多 $\log n$ 步。
单点修改：所有覆盖位置 $p$ 的 t[i] 依次是 $p,\ p + \operatorname{lowbit}(p), \dots$ ，最多 $\log n$ 个。

树状数组上二分

如果所有元素非负，前缀和单调不减，就可以从高位到低位逐位确定答案：尝试把当前位置加上 $2^b$ ，如果 t[p + 2^b] 不超过剩余的 $k$ 就前进。这样只需 $O(\log n)$ ，而”二分 + 前缀查询”需要 $O(\log^2 n)$ 。模板中的 upper 就是这个操作，常用于求第 $k$ 小。

区间修改

区间加、单点查：对差分数组建树状数组，区间加变成两次单点加。
区间加、区间查：维护两个树状数组 $d_i$ 和 $i \cdot d_i$ ，利用

\sum_{i=1}^{p} a_i = (p+1)\sum_{i=1}^{p} d_i - \sum_{i=1}^{p} i \cdot d_i

复杂度

操作	时间
建树（逐个 `add`）	$O(n \log n)$ ；先算前缀再线性建树可做到 $O(n)$
单点修改、前缀查询	$O(\log n)$
树状数组上二分	$O(\log n)$

空间复杂度为 $O(n)$ 。

模板

模板对外使用 0 下标、左闭右开区间，这和 Library Checker 的输入格式一致；内部仍然用 1 下标存储。

// 树状数组（Fenwick Tree）：单点加、前缀和，下标从 0 开始
template <class T>
struct BIT {
    int n;
    vector<T> t;

    BIT(int n) : n(n), t(n + 1) {}

    // a[p] += v
    void add(int p, T v) {
        for (p++; p <= n; p += p & -p) t[p] += v;
    }

    // 返回 a[0] + ... + a[p-1]
    T pre(int p) {
        T s = 0;
        for (; p > 0; p -= p & -p) s += t[p];
        return s;
    }

    // 返回 a[l] + ... + a[r-1]
    T sum(int l, int r) { return pre(r) - pre(l); }

    // 在所有元素非负时，返回满足 pre(p) <= k 的最大 p
    int upper(T k) {
        int p = 0;
        for (int b = __lg(max(n, 1)); b >= 0; b--) {
            int q = p + (1 << b);
            if (q <= n && t[q] <= k) p = q, k -= t[q];
        }
        return p;
    }
};

模板题

void solve() {
    int n, q;
    cin >> n >> q;
    BIT<LL> b(n);
    for (int i = 0; i < n; i++) {
        LL x;
        cin >> x;
        b.add(i, x);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 0) {
            int p; LL x;
            cin >> p >> x;
            b.add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << b.sum(l, r) << '\n';
        }
    }
}

常见坑

下标 0 导致死循环：lowbit(0) = 0，如果在 1 下标的实现里传入 $0$ ，add 会一直循环。模板在内部做了 p++。
溢出：区间和通常需要 long long，模板用 BIT<LL>。
树上二分的前提：upper 要求所有元素非负，否则前缀和不单调，结果没有意义。
维护最值： $\max$ 不可逆，不能用 pre(r) - pre(l) 求区间最值。

树状数组

适用场景

核心思路

树状数组上二分

区间修改

复杂度

模板

模板题

常见坑

延伸阅读