树状数组的本质

1. 引言

树状数组（Fenwick Tree）是一种用于高效处理动态数组前缀和的数据结构。它可以在 $O(\log n)$ 时间内完成单点更新和前缀和查询，适用于需要频繁修改和查询的场景，比如处理区间和、求逆序对数量等问题。

---

2. 基本问题与朴素解法

假设有一个长度为 $n$ 的数组 A，支持以下两种操作：

1. 单点更新：将某个位置的元素增加一个值，即 $A[i] \gets A[i] + \Delta$。
2. 前缀和查询：计算数组前 $k$ 个元素的和，即：
   $$
   \text{prefix_sum}(k) = A[1] + A[2] + \dots + A[k]
   $$

朴素方法的缺点

• 单点更新：时间复杂度为 $O(1)$。
• 前缀和查询：时间复杂度为 $O(n)$，因为需要逐一累加前 $k$ 个元素。

这种方法在频繁查询和更新时效率低下，所以我们需要一种更高效的数据结构，即树状数组。

---

3. 树状数组的设计思想

树状数组通过维护一个辅助数组 C[] 来加速查询和更新。每个节点 C[i] 在逻辑上负责管理一段连续区间的前缀和，并且这些区间是由二进制位的最低位 1 来划分的。

lowbit 函数

在树状数组中，我们用 lowbit(i) 函数来表示位置 $i$ 的二进制最低位 1 所代表的值：

$$
\text{lowbit}(i) = i \, \& \, (-i)
$$

示例：

• $i = 6 = (110)_2$，则 $\text{lowbit}(6) = 2 = (10)_2$。
• $i = 12 = (1100)_2$，则 $\text{lowbit}(12) = 4 = (100)_2$。

---

4. 树状数组的区间划分

每个节点 $C[i]$ 负责一个区间，这个区间的长度正是 $\text{lowbit}(i)$，即二进制表示中最低位 1 所代表的值。

• 区间的终点：总是位置 $i$。
• 区间的起点：为 $i - \text{lowbit}(i) + 1$。

因此，节点 $C[i]$ 负责的区间是：

$$
[i - \text{lowbit}(i) + 1, \, i]
$$

为什么用 lowbit 来划分区间？

• 递归划分区间：通过 lowbit 的规则，可以将数组的不同区间按逻辑划分，并保证每个节点管理的区间不重不漏。
• 高效的更新与查询：通过巧妙的区间划分，可以快速跳转到相关节点，实现 $O(\log n)$ 时间内的查询和更新。

---

5. 树状数组的操作

5.1 单点更新

将数组 A[] 的第 $k$ 个元素增加 $\Delta$，即 $A[k] \gets A[k] + \Delta$。

更新过程

1. 从位置 $k$ 开始，依次更新所有包含该位置的节点 C[i]。
2. 每次将 $k$ 更新为 $k + \text{lowbit}(k)$，跳转到父节点，直到超出数组范围。

伪代码

void update(int k, int delta) {
    while (k <= n) {
        C[k] += delta;
        k += lowbit(k);  // 跳转到父节点
    }
}

---

5.2 前缀和查询

计算数组 A 中前 $k$ 个元素的和，即：

$$
\text{prefix_sum}(k) = A[1] + A[2] + \dots + A[k]
$$

查询过程

1. 从位置 $k$ 开始，依次累加所有相关节点的值到 sum。
2. 每次将 $k$ 更新为 $k - \text{lowbit}(k)$，跳转到子节点，直到 $k = 0$。

伪代码

int query(int k) {
    int sum = 0;
    while (k > 0) {
        sum += C[k];
        k -= lowbit(k);  // 跳转到子节点
    }
    return sum;
}

---

6. 树状数组示例

假设我们有一个长度为 8 的数组 A[]，初始值全为 0：

Index:  1  2  3  4  5  6  7  8
A[]:    0  0  0  0  0  0  0  0
C[]:    0  0  0  0  0  0  0  0

我们进行以下操作：

操作1：update(1, 5)

• 更新 A[1] += 5。
• 更新节点 C[1]：C[1] += 5。
• 跳转到 $1 + \text{lowbit}(1) = 2$，更新 C[2] += 5。
• 跳转到 $2 + \text{lowbit}(2) = 4$，更新 C[4] += 5。
• 跳转到 $4 + \text{lowbit}(4) = 8$，更新 C[8] += 5。

结果：

C[]:  5  5  0  5  0  0  0  5

---

操作2：update(4, 3)

• 更新 A[4] += 3。
• 更新节点 C[4]：C[4] += 3。
• 跳转到 $4 + \text{lowbit}(4) = 8$，更新 C[8] += 3。

结果：

C[]:  5  5  0  8  0  0  0  8

---

操作3：query(4)

• 计算前缀和 A[1] + A[2] + A[3] + A[4]。
• 从 C[4] 开始，sum = 8。
• 跳转到 $4 - \text{lowbit}(4) = 0$。

结果：sum = 8。

---

7. 时间复杂度分析

• 单点更新：$O(\log n)$。
• 前缀和查询：$O(\log n)$。

树状数组的高效性来源于其低位掩码（lowbit）的使用，使得每次操作都能跳跃式地访问相关节点。

---

8. 总结

树状数组是一种高效的数据结构，适用于需要频繁进行单点更新和前缀和查询的场景。它通过lowbit 函数将数组划分为不同的区间，使得更新和查询的时间复杂度都为 $O(\log n)$。

关键点回顾：

• lowbit：用于确定节点负责的区间大小。
• 单点更新：从目标位置开始，逐层更新相关节点。
• 前缀和查询：从目标位置向下累加，快速计算前缀和。

树状数组结构简单，但功能强大，常用于求逆序对、区间和等问题。