InoueMoby's Blog

前言

上一篇我们学了线段树——它能处理区间查询和区间修改，是”万能选手”。但如果你的问题只需要单点修改 + 前缀查询呢？线段树 100 多行的代码是不是有点杀鸡用牛刀？

树状数组（Binary Indexed Tree, BIT / Fenwick Tree）就是为这个场景量身定制的。它只有不到 20 行的核心代码，却能在 $O(\log n)$ 时间内完成单点修改和前缀求和。

而且，很多问题可以巧妙地转化为”前缀查询”，所以 BIT 的适用范围远比你想象的广。逆序对计数就是经典案例。

问题的本质

前缀和的升级版

普通前缀和数组 $O(1)$ 查询，但修改一个元素要 $O(n)$ 更新所有后续的前缀和。

BIT 的巧妙之处：把前缀和拆成 $\log n$ 段。每段覆盖一个”二进制区间”，修改时只需要更新 $\log n$ 段。查询时也只需要合并 $\log n$ 段。

lowbit：二进制的魔法

一个数 $x$ 的 lowbit 是它二进制表示中最低位的 1 所代表的值。例如：

$x = 6 = (110)_2$ ，lowbit = $(10)_2 = 2$
$x = 12 = (1100)_2$ ，lowbit = $(100)_2 = 4$

计算方法：lowbit(x) = x & (-x)。

BIT 中，位置 $i$ 管辖的区间长度恰好是 $\text{lowbit}(i)$ 。也就是说，tree[i] 负责区间 $[i - \text{lowbit}(i) + 1, i]$ 的和。

位置:   1  2  3  4  5  6  7  8
lowbit: 1  2  1  4  1  2  1  8
管辖:   [1] [1,2] [3] [1,4] [5] [5,6] [7] [1,8]

注意：位置 4 管辖 $[1,4]$ （长度 4），位置 8 管辖 $[1,8]$ （长度 8）。

理论 + 代码

核心操作

前缀查询 sum(i)：求 $a_1 + a_2 + \cdots + a_i$ 。

从 $i$ 开始，不断把 tree[i] 累加，然后 i -= lowbit(i) 跳到上一段。每步减去 lowbit，所以最多 $\log n$ 步。

int sum(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i)  // ① 每步减去 lowbit
        s += tree[i];
    return s;
}

单点修改 add(i, v)：把 $a_i$ 加上 $v$ 。

从 $i$ 开始，更新所有覆盖 $i$ 的 tree 节点。每次 i += lowbit(i) 跳到下一个覆盖者。

void add(int i, int v) {
    for (; i <= n; i += i & -i)  // ② 每步加上 lowbit
        tree[i] += v;
}

模拟走一遍

初始 tree 全 0，对长度为 8 的数组执行 add(3, 5), add(6, 2)：

操作	tree 变化	说明
add(3,5)	tree[3]+=5, tree[4]+=5, tree[8]+=5	3→4→8
add(6,2)	tree[6]+=2, tree[8]+=2	6→8
sum(5)	tree[5]+tree[4] = 0+5 = 5	5→4→0
sum(7)	tree[7]+tree[6]+tree[4] = 0+2+5 = 7	7→6→4→0

逆序对

逆序对：满足 $i < j$ 且 $A_i > A_j$ 的对数。

用 BIT 的做法：从右往左扫，对每个 $A_i$ ，查询”右边已经出现了多少个比 $A_i$ 小的数”= sum(A_i - 1)。然后把 $A_i$ 加入 BIT：add(A_i, 1)。

例题

例题 1：TB B59 — Number of Inversions

题目：给定 $1$ 到 $N$ 的排列 $A$ ，求逆序对数（满足 $i < j$ 且 $A_i > A_j$ 的对数）。

数据范围： $1 \le N \le 1.5 \times 10^5$

—— AtCoder Tessoku Book B59

分析： $A$ 是 $1$ 到 $N$ 的排列，值域恰好 $[1, N]$ ，不需要离散化。从右往左扫，用 BIT 查”右边有多少个比 $A_i$ 小的”。

代码：

#include <cstdio>
using namespace std;

const int MAXN = 150006;
int tree[MAXN], n;

void add(int i, int v) { for (; i <= n; i += i & -i) tree[i] += v; }
int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }

int main() {
    scanf("%d", &n);
    int A[MAXN];
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    long long ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        ans += sum(A[i] - 1);  // ① 查右边有几个比 A[i] 小的
        add(A[i], 1);          // ② 把 A[i] 加入 BIT
    }
    printf("%lld\n", ans);
    return 0;
}

逐行解析：

① sum(A[i]-1) 查的是 BIT 中当前有多少个值 $< A[i]$ 。因为我们从右往左扫，BIT 中存的都是 $A_i$ 右边的元素。所以这查的就是”右边有多少个比 $A_i$ 小的”。
② 每处理完一个元素就把它加入 BIT。
因为 $A$ 是排列，值域 $[1,N]$ ，BIT 大小 $N$ 就够了。

验证： $A=[2,4,1,3]$ 。从右往左：

i=3, A[3]=3: sum(2)=0, add(3,1). ans=0
i=2, A[2]=1: sum(0)=0, add(1,1). ans=0
i=1, A[1]=4: sum(3)=2, add(4,1). ans=2
i=0, A[0]=2: sum(1)=1, add(2,1). ans=3 ✓

例题 2：ACL Practice B — Fenwick Tree

题目：长度为 $N$ 的数组 $a_0, a_1, \ldots, a_{N-1}$ 。 $Q$ 个查询：

0 p x： $a_p \mathrel{+}= x$

1 l r：输出 $\sum_{i=l}^{r-1} a_i$

数据范围： $1 \le N, Q \le 5 \times 10^5$ ，0-indexed

—— AtCoder ACL Practice B

分析：BIT 的模板题。注意 0-indexed，需要统一转成 1-indexed。区间和 $[l, r)$ = sum(r) - sum(l)。

代码：

#include <cstdio>
using namespace std;

const int MAXN = 500006;
long long tree[MAXN];
int n;

void add(int i, long long v) { for (; i <= n; i += i & -i) tree[i] += v; }
long long sum(int i) { long long s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }

int main() {
    int Q;
    scanf("%d%d", &n, &Q);
    for (int i = 0; i < n; i++) {
        long long a;
        scanf("%lld", &a);
        add(i + 1, a);            // ① 0-indexed 转 1-indexed
    }
    while (Q--) {
        int t;
        scanf("%d", &t);
        if (t == 0) {
            int p; long long x;
            scanf("%d%lld", &p, &x);
            add(p + 1, x);        // ② 单点加
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", sum(r) - sum(l)); // ③ 区间 [l, r) 的和
        }
    }
    return 0;
}

逐行解析：

① BIT 是 1-indexed 的，而题目是 0-indexed，所以要 +1。
③ sum(r) - sum(l) = $[1, r-1]$ 的和 $-$ $[1, l-1]$ 的和 = $[l, r-1]$ 的和。

例题 3：TB A59 — RSQ (Range Sum Queries)

题目：长度 $N$ 的数组，初始全 0。 $Q$ 个查询：

1 pos x： $A_{pos} = x$ （赋值，不是加）

2 l r：输出 $A_l + \cdots + A_{r-1}$

数据范围： $1 \le N, Q \le 10^5$

—— AtCoder Tessoku Book A59

分析：BIT 只支持”加”操作。赋值怎么办？维护当前值，add(pos, x - current[pos])。

代码：

#include <cstdio>
using namespace std;

const int MAXN = 100006;
long long tree[MAXN];
int cur[MAXN];  // 当前值
int n;

void add(int i, long long v) { for (; i <= n; i += i & -i) tree[i] += v; }
long long sum(int i) { long long s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }

int main() {
    int Q;
    scanf("%d%d", &n, &Q);
    while (Q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int pos; long long x;
            scanf("%d%lld", &pos, &x);
            add(pos, x - cur[pos]);  // ① 差值更新
            cur[pos] = x;
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", sum(r - 1) - sum(l - 1)); // ② [l, r-1]
        }
    }
    return 0;
}

逐行解析：

① BIT 只支持”加”操作，但题目要求”赋值”。所以维护当前值数组 cur，每次 add(pos, x - cur[pos]) 来补差值。
② 区间 $[l, r-1]$ 的和 = sum(r-1) - sum(l-1)。注意题目查询 2 l r 查的是 $A_l$ 到 $A_{r-1}$ 。

例题 4（练习）：T90 017 — Crossing Segments（★7）

题目：圆周上有 $N$ 个点， $M$ 条线段（连接点 $L_i$ 和 $R_i$ ）。求有多少对线段在端点以外相交。

数据范围： $3 \le N \le 3 \times 10^5$

—— AtCoder Typical 90 017

思路提示：这是一道 BIT 的高级应用（★7 难题）。圆上两条线段相交 ⟺ 它们的端点交错。关键转化：把线段 $(L, R)$ 看成区间，两条线段相交当且仅当一个区间的端点恰好在另一个区间内（即 $L_a < L_b < R_a < R_b$ ）。利用排序 + BIT 计数可以 $O(M \log N)$ 解决。

参考文献

教材讲解 — 競技プログラミングの鉄則

第 8 章 8.9 BIT 求逆序对（B59 Number of Inversions 解说，含 dat[] 数组管理原理）

系统练习 — 競技プログラミングの鉄則

实战练习 — 競プロ典型 90 問

017 Crossing Segments（★7，BIT 计数）【例题】

模板练习 — ACL Practice Contest

B Fenwick Tree（BIT 模板题）【例题】

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

树状数组

线段树的小兄弟——功能少一点，但代码短到令人感动

前言

问题的本质

前缀和的升级版

lowbit：二进制的魔法

理论 + 代码

核心操作

模拟走一遍

逆序对

例题

例题 1：TB B59 — Number of Inversions

例题 2：ACL Practice B — Fenwick Tree

例题 3：TB A59 — RSQ (Range Sum Queries)

例题 4（练习）：T90 017 — Crossing Segments（★7）

参考文献

系列索引

树状数组