这里为您整理了一份关于**树状数组（Binary Indexed Tree, 简称 BIT / Fenwick Tree）**的算法讲义。讲义中将涵盖树状数组的核心原理、优缺点、复杂度分析、基础模板代码，以及如何通过树状数组配合“离散化”来高效解决“逆序对”等经典问题。

---

# 算法讲义：树状数组（Fenwick Tree / Binary Indexed Tree）

## 1. 什么是树状数组（定义）
树状数组（Binary Indexed Tree）是一种用于高效维护**前缀和**与**单点修改**的数据结构。与线段树类似，它常用于处理动态数组的区间查询问题，但在结构上更为轻量。

树状数组的底层是一个普通数组 `tree[]`，它的下标必须从 `1` 开始。每一个位置 `x` 并不像普通前缀和那样存储 $[1, x]$ 的所有元素和，而是维护一段特定长度的区间和。

---

## 2. 工作原理与核心概念

### (1) 核心原理：二进制分解
任何一个正整数 $x$ 都可以唯一地分解为若干个 $2$ 的幂次之和。树状数组正是利用这一特性来划分区间的。
对于节点 `x`，它所维护的区间长度等于 $x$ 的二进制表示中**最低位的 $1$ 对应的数值**。我们通常用 `lowbit(x)` 来表示这个值。

* 节点 `tree[x]` 存储的区间是：$(x - \text{lowbit}(x), x]$。
* 区间长度为 $\text{lowbit}(x)$。

**举例说明：**
* $x = 6$（二进制为 $0110_2$），$\text{lowbit}(6) = 2$（二进制 $0010_2$）。
  因此 `tree[6]` 维护的区间是 $(6-2, 6] = (4, 6]$，即 `tree[6] = arr[5] + arr[6]`。
* $x = 8$（二进制为 $1000_2$），$\text{lowbit}(8) = 8$（二进制 $1000_2$）。
  因此 `tree[8]` 维护的区间是 $(8-8, 8] = (0, 8]$，即整个前缀的和。

### (2) 核心函数：`lowbit`
利用计算机中整型的**补码**表示法，我们可以通过位运算在 $O(1)$ 的时间内求得 `lowbit(x)`：
```cpp
inline int lowbit(int x) {
    return x & -x;
}
```
*原理：在补码表示下，`-x` 等于 `~x + 1`（按位取反再加 1）。当两者进行按位与（`&`）操作时，除了最低位的 $1$ 被保留之外，其余高位由于取反而相反，均变为 $0$。*

### (3) 操作逻辑
* **前缀和查询（Query）**：
  若要查询前缀和 $S[x]$，我们需要将拆分出来的区间值依次相加。
  每次累加 `tree[x]`，然后将 `x` 减去 `lowbit(x)`（相当于抹去二进制中的最后一个 $1$），直到 `x` 变为 $0$。
* **单点修改（Update）**：
  若要给 `arr[x]` 增加一个值 `val`，我们需要更新所有包含位置 `x` 的树状数组节点。
  这些受影响的节点可以通过不断加上自身的 `lowbit` 获得：每次更新 `tree[x]` 后，让 `x` 加上 `lowbit(x)`，直到 `x` 超过数组的最大边界 $N$。

---

## 3. 算法复杂度

| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
| :--- | :--- | :--- | :--- |
| **单点修改** | $O(\log N)$ | $O(1)$ | 每次往上跳转，二进制位数减少，最多跳转 $\log N$ 次。 |
| **前缀查询** | $O(\log N)$ | $O(1)$ | 每次往下减少 `lowbit`，最多跳转 $\log N$ 次。 |
| **空间开销** | — | $O(N)$ | 仅需要一个与原数组等大的 `tree` 数组，空间利用率极高。 |

---

## 4. 优缺点与不足之处

### 优点
1. **代码极短**：核心实现通常只需十余行，不容易在比赛或工程中写错。
2. **空间开销小**：只需要 $1N$ 的辅助空间，相较于线段树的 $4N$ 空间，大大节省了内存。
3. **常数极小**：运算全部基于简单的位运算和一维数组循环，执行效率显著快于结构复杂的线段树。

### 缺点与不足
1. **局限性强**：仅适用于满足**可逆性**或具有前缀性质的运算。例如，它非常适合处理区间求和，但直接用于处理任意区间的最大值/最小值（RMQ）时，代码实现会变得较为复杂且效率有所降低。
2. **功能拓展受限**：不支持像线段树那样通过懒标记（Lazy Tag）直接进行通用的“区间修改 + 区间查询”。虽然可以通过差分数组等技巧实现类似功能，但普适性不如线段树。

---

## 5. 基础操作模板（C++14）

```cpp
#include <iostream>
#include <vector>

using namespace std;

class FenwickTree {
private:
    int n;
    vector<long long> tree;

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

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

// 单点修改：在位置 x 加上 val
    void update(int x, long long val) {
        for (; x <= n; x += lowbit(x)) {
            tree[x] += val;
        }
    }

// 查询前缀和：[1, x] 的和
    long long query(int x) {
        long long sum = 0;
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }

// 区间查询：[l, r] 的和
    long long range_query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};
```

---

## 6. 经典应用：求逆序对（Inversions）

### (1) 什么是逆序对
在一个序列 $A$ 中，若存在两个下标 $i < j$，使得 $A[i] > A[j]$，则称 $(A[i], A[j])$ 为一对**逆序对**。
计算逆序对的数量是评估序列乱序程度的常见方法。

### (2) 树状数组解决逆序对的原理
如果我们在遍历数组的同时，将元素逐个插入到树状数组中（即在数值对应的位置 `update(A[j], 1)`）：
1. 树状数组此时相当于一个**桶（频数数组）**。
2. 当我们处理到第 $j$ 个元素 $A[j]$ 时，已经有 $j - 1$ 个元素被插入了树状数组。
3. 此时，值小于或等于 $A[j]$ 的元素个数可以通过树状数组前缀查询得到，即 `query(A[j])`。
4. 那么，在已插入的元素中，**严格大于 $A[j]$** 的元素个数就是：
   $$\text{当前已插入元素总数} - \text{小于等于 } A[j] \text{ 的元素个数} = (j - 1) - \text{query}(A[j])$$
5. 遍历整个序列并累加这个差值，即可得到全局的逆序对总数。

### (3) 关键步骤：离散化（Discretization）
如果数组中的数值范围非常大（例如 $A[i] \le 10^9$），直接用数值作为树状数组的下标会导致内存崩溃。
由于逆序对只关心元素的**相对大小关系**，而不关心其具体绝对数值，因此我们可以采用**离散化**将数值映射到 $[1, N]$ 的区间内。

**离散化示例：**
* 原始数组：`[500, 10, 2000, 10]`
* 排序并去重后：`[10, 500, 2000]`
* 映射关系：`10 -> 1`，`500 -> 2`，`2000 -> 3`
* 离散化后的新数组：`[2, 1, 3, 1]`。其逆序对数量与原数组完全一致。

---

### (4) 逆序对完整代码（C++14）

下面是一个结合了**离散化**与**树状数组**来求逆序对的完整实现：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 树状数组结构体
struct Fenwick {
    int n;
    vector<int> tree;
    
    Fenwick(int size) : n(size), tree(size + 1, 0) {}
    
    inline int lowbit(int x) {
        return x & -x;
    }
    
    void update(int x, int val) {
        for (; x <= n; x += lowbit(x)) {
            tree[x] += val;
        }
    }
    
    int query(int x) {
        int sum = 0;
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }
};

int main() {
    // 提升输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> arr(n);
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        temp[i] = arr[i];
    }
    
    // --- 离散化步骤 ---
    // 1. 排序并去重
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    
    // 2. 将原数组中的数值映射到 [1, temp.size()] 的排名区间
    vector<int> ranks(n);
    for (int i = 0; i < n; ++i) {
        // lower_bound 找到当前值在排好序的 temp 数组中的位置，加 1 转换成 1-based 下标
        ranks[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
    }
    
    // --- 计算逆序对 ---
    long long inversion_count = 0;
    Fenwick bit(temp.size()); // 树状数组的大小为不同数值的个数
    
    for (int i = 0; i < n; ++i) {
        int val = ranks[i];
        
        // 1. 先查询当前树状数组中，大于 val 的元素个数
        // 已插入元素总数是 i，小于等于 val 的个数是 bit.query(val)
        int greater_elements = i - bit.query(val);
        inversion_count += greater_elements;
        
        // 2. 将当前值放入树状数组中（相应频数 +1）
        bit.update(val, 1);
    }
    
    cout << inversion_count << "\n";
    
    return 0;
}
```

这里为您整理了一份关于树状数组（Binary Indexed Tree, 简称 BIT / Fenwick Tree）的算法讲义。讲义中将涵盖树状数组的核心原理、优缺点、复杂度分析、基础模板代码，以及如何通过树状数组配合“离散化”来高效解决“逆序对”等经典问题。

算法讲义：树状数组（Fenwick Tree / Binary Indexed Tree）

1. 什么是树状数组（定义）

树状数组（Binary Indexed Tree）是一种用于高效维护前缀和与单点修改的数据结构。与线段树类似，它常用于处理动态数组的区间查询问题，但在结构上更为轻量。

树状数组的底层是一个普通数组 tree[]，它的下标必须从 1 开始。每一个位置 x 并不像普通前缀和那样存储 $[1, x]$ 的所有元素和，而是维护一段特定长度的区间和。

2. 工作原理与核心概念

(1) 核心原理：二进制分解

任何一个正整数 $x$ 都可以唯一地分解为若干个 $2$ 的幂次之和。树状数组正是利用这一特性来划分区间的。对于节点 x，它所维护的区间长度等于 $x$ 的二进制表示中最低位的 $1$ 对应的数值。我们通常用 lowbit(x) 来表示这个值。

节点 tree[x] 存储的区间是：$(x - \text{lowbit}(x), x]$。
区间长度为 $\text{lowbit}(x)$。

举例说明： * $x = 6$（二进制为 $0110_2$），$\text{lowbit}(6) = 2$（二进制 $0010_2$）。因此 tree[6] 维护的区间是 $(6-2, 6] = (4, 6]$，即 tree[6] = arr[5] + arr[6]。 * $x = 8$（二进制为 $1000_2$），$\text{lowbit}(8) = 8$（二进制 $1000_2$）。因此 tree[8] 维护的区间是 $(8-8, 8] = (0, 8]$，即整个前缀的和。

(2) 核心函数：`lowbit`

利用计算机中整型的补码表示法，我们可以通过位运算在 $O(1)$ 的时间内求得 lowbit(x)：

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

原理：在补码表示下，-x 等于 ~x + 1（按位取反再加 1）。当两者进行按位与（&）操作时，除了最低位的 $1$ 被保留之外，其余高位由于取反而相反，均变为 $0$。

(3) 操作逻辑

前缀和查询（Query）：若要查询前缀和 $S[x]$，我们需要将拆分出来的区间值依次相加。每次累加 tree[x]，然后将 x 减去 lowbit(x)（相当于抹去二进制中的最后一个 $1$），直到 x 变为 $0$。
单点修改（Update）：若要给 arr[x] 增加一个值 val，我们需要更新所有包含位置 x 的树状数组节点。这些受影响的节点可以通过不断加上自身的 lowbit 获得：每次更新 tree[x] 后，让 x 加上 lowbit(x)，直到 x 超过数组的最大边界 $N$。

3. 算法复杂度

操作	时间复杂度	空间复杂度	说明
单点修改	$O(\log N)$	$O(1)$	每次往上跳转，二进制位数减少，最多跳转 $\log N$ 次。
前缀查询	$O(\log N)$	$O(1)$	每次往下减少 `lowbit`，最多跳转 $\log N$ 次。
空间开销	—	$O(N)$	仅需要一个与原数组等大的 `tree` 数组，空间利用率极高。

4. 优缺点与不足之处

优点

代码极短：核心实现通常只需十余行，不容易在比赛或工程中写错。
空间开销小：只需要 $1N$ 的辅助空间，相较于线段树的 $4N$ 空间，大大节省了内存。
常数极小：运算全部基于简单的位运算和一维数组循环，执行效率显著快于结构复杂的线段树。

缺点与不足

局限性强：仅适用于满足可逆性或具有前缀性质的运算。例如，它非常适合处理区间求和，但直接用于处理任意区间的最大值/最小值（RMQ）时，代码实现会变得较为复杂且效率有所降低。
功能拓展受限：不支持像线段树那样通过懒标记（Lazy Tag）直接进行通用的“区间修改 + 区间查询”。虽然可以通过差分数组等技巧实现类似功能，但普适性不如线段树。

5. 基础操作模板（C++14）

#include <iostream>
#include <vector>

using namespace std;

class FenwickTree {
private:
    int n;
    vector<long long> tree;

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

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // 单点修改：在位置 x 加上 val
    void update(int x, long long val) {
        for (; x <= n; x += lowbit(x)) {
            tree[x] += val;
        }
    }

    // 查询前缀和：[1, x] 的和
    long long query(int x) {
        long long sum = 0;
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }

    // 区间查询：[l, r] 的和
    long long range_query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

6. 经典应用：求逆序对（Inversions）

(1) 什么是逆序对

在一个序列 $A$ 中，若存在两个下标 $i < j$，使得 $A[i] > A[j]$，则称 $(A[i], A[j])$ 为一对逆序对。计算逆序对的数量是评估序列乱序程度的常见方法。

(2) 树状数组解决逆序对的原理

如果我们在遍历数组的同时，将元素逐个插入到树状数组中（即在数值对应的位置 update(A[j], 1)）： 1. 树状数组此时相当于一个桶（频数数组）。 2. 当我们处理到第 $j$ 个元素 $A[j]$ 时，已经有 $j - 1$ 个元素被插入了树状数组。 3. 此时，值小于或等于 $A[j]$ 的元素个数可以通过树状数组前缀查询得到，即 query(A[j])。 4. 那么，在已插入的元素中，严格大于 $A[j]$ 的元素个数就是： $$\text{当前已插入元素总数} - \text{小于等于 } A[j] \text{ 的元素个数} = (j - 1) - \text{query}(A[j])$$ 5. 遍历整个序列并累加这个差值，即可得到全局的逆序对总数。

(3) 关键步骤：离散化（Discretization）

如果数组中的数值范围非常大（例如 $A[i] \le 10^9$），直接用数值作为树状数组的下标会导致内存崩溃。由于逆序对只关心元素的相对大小关系，而不关心其具体绝对数值，因此我们可以采用离散化将数值映射到 $[1, N]$ 的区间内。

离散化示例： * 原始数组：[500, 10, 2000, 10] * 排序并去重后：[10, 500, 2000] * 映射关系：10 -> 1，500 -> 2，2000 -> 3 * 离散化后的新数组：[2, 1, 3, 1]。其逆序对数量与原数组完全一致。

(4) 逆序对完整代码（C++14）

下面是一个结合了离散化与树状数组来求逆序对的完整实现：

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

using namespace std;

// 树状数组结构体
struct Fenwick {
    int n;
    vector<int> tree;

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

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

    void update(int x, int val) {
        for (; x <= n; x += lowbit(x)) {
            tree[x] += val;
        }
    }

    int query(int x) {
        int sum = 0;
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }
};

int main() {
    // 提升输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> arr(n);
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        temp[i] = arr[i];
    }

    // --- 离散化步骤 ---
    // 1. 排序并去重
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());

    // 2. 将原数组中的数值映射到 [1, temp.size()] 的排名区间
    vector<int> ranks(n);
    for (int i = 0; i < n; ++i) {
        // lower_bound 找到当前值在排好序的 temp 数组中的位置，加 1 转换成 1-based 下标
        ranks[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
    }

    // --- 计算逆序对 ---
    long long inversion_count = 0;
    Fenwick bit(temp.size()); // 树状数组的大小为不同数值的个数

    for (int i = 0; i < n; ++i) {
        int val = ranks[i];

        // 1. 先查询当前树状数组中，大于 val 的元素个数
        // 已插入元素总数是 i，小于等于 val 的个数是 bit.query(val)
        int greater_elements = i - bit.query(val);
        inversion_count += greater_elements;

        // 2. 将当前值放入树状数组中（相应频数 +1）
        bit.update(val, 1);
    }

    cout << inversion_count << "\n";

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com