树状数组（BIT）：快速处理前缀和查询

# 2.1.1 树状数组（BIT）的定义和原理

树状数组（Binary Indexed Tree，简称 BIT），又称二进制索引树，是一种基于二进制树思想设计的空间优化数据结构。它可以高效地处理一维数组上的单点更新和区间查询操作。

BIT 的基本原理是利用二进制数的特性，将一维数组中的每个元素看作一个二进制数，并将其存储在树形结构中。在树形结构中，每个节点存储一个或多个数组元素，且满足以下条件：

- 对于任意一个节点，其左子节点存储的元素索引是其索引的二进制表示中最低位为 0 的所有元素索引；
- 对于任意一个节点，其右子节点存储的元素索引是其索引的二进制表示中最低位为 1 的所有元素索引。

# 2. 树状数组（BIT）的实现与操作

### 2.1 树状数组（BIT）的数据结构

#### 2.1.1 树状数组（BIT）的定义和原理

树状数组（Binary Indexed Tree，简称 BIT），是一种基于二进制树原理构建的数据结构，用于高效地维护一个一维数组中的元素和进行区间和查询。

树状数组的原理是将一维数组中的元素按照二进制位进行存储，从而形成一棵完全二叉树。对于一个长度为 N 的数组，其对应的树状数组大小为 N+1。

#### 2.1.2 树状数组（BIT）的存储和表示

树状数组中的每个节点存储着它所代表的子数组中所有元素的和。对于索引为 i 的节点，它所代表的子数组范围为 [i-lowbit(i)+1, i]，其中 lowbit(i) 表示 i 的二进制表示中最低位的 1 所在的位置。

### 2.2 树状数组（BIT）的更新和查询操作

#### 2.2.1 树状数组（BIT）的单点更新

单点更新操作是指更新树状数组中某个元素的值。对于索引为 i 的元素，其更新过程如下：

void update(int i, int val) {
    while (i <= n) {
        bit[i] += val;
        i += lowbit(i);
    }
}

其中，n 为树状数组的大小。

**逻辑分析：**

该更新操作从 i 开始，逐层向上更新树状数组中每个节点的值。对于每个节点，它将 val 加到其所代表的子数组中所有元素的和上，然后将 i 递增 lowbit(i) 以访问其父节点。

**参数说明：**

* `i`: 要更新的元素索引
* `val`: 更新的值

#### 2.2.2 树状数组（BIT）的前缀和查询

前缀和查询操作是指查询树状数组中某个索引 i 之前的元素和。对于索引为 i 的元素，其前缀和查询过程如下：

int query(int i) {
    int sum = 0;
    while (i > 0) {
        sum += bit[i];
        i -= lowbit(i);
    }
    return sum;
}

**逻辑分析：**

该查询操作从 i 开始，逐层向下查询树状数组中每个节点的值。对于每个节点，它将节点的值加到 sum 中，然后将 i 递减 lowbit(i) 以访问其子节点。

**参数说明：**

* `i`: 要查询的索引

# 3.1 树状数组（BIT）在区间和查询中的应用

#### 3.1.1 区间和查询的定义和需求

区间和查询是一种常见的数据结构问题，其目标是在给定一个数组中，计算指定区间内所有元素的和。例如，给定数组 `[1, 2, 3, 4, 5, 6, 7]`，区间和查询 `[2, 5]` 的结果为 `15`。

区间和查询在许多实际应用中都有着广泛的需求，例如：

- 股票分析：计算特定时间段内的股票价格总和。
- 数据统计：计算特定地区的人口总数。
- 科学研究：计算特定实验条件下的数据总和。

#### 3.1.2 树状数组（BIT）解决区间和查询的思路

树状数组（BIT）通过利用其二进制性质，可以高效地解决区间和查询问题。BIT 的核心思想是将数组元素存储在一棵二叉树中，其中每个节点的值代表其子树中所有元素的和。

具体来说，BIT 的构建过程如下：

1. **初始化：**创建一个大小为 `n` 的数组 `BIT`，其中 `n` 为原始数组的大小。
2. **遍历原始数组：**依次遍历原始数组中的每个元素 `a[i]`。
3. **更新 BIT：**对于每个元素 `a[i]`, 从其索引 `i` 开始，沿其二进制表示中的每个 `1` 位向上更新 `BIT`。具体来说，对于索引 `i` 的二进制表示 `(i)_2`，将 `BIT[i]` 加上 `a[i]`，并将 `i`