# 树状数组及应用

## 1. 什么是树状数组

树状数组（Binary Indexed Tree, BIT）是一种数据结构，主要用于数组的单点修改和区间求和，支持在 $O(\log n)$ 时间内完成查询和更新操作。  
传统的前缀和方法可以在 $O(1)$ 时间内查询区间和，但如果修改一个点的值，需要重新计算整个前缀和数组，这需要 $O(n)$ 时间复杂度。树状数组通过树形结构优化了单点修改和区间求和操作。

---

### 树状数组的拆分原理

树状数组的基本思想是将一个区间的和拆分成多个子区间的和。通过观察二进制表示，发现一个整数可以表示为一系列 2 的幂之和，从而可以将区间拆分为多个子区间。具体来说，可以通过二进制表示来划分一个区间。

例如，对于一个长度为 $21$ 的数组，其二进制表示为 `10101`，即：
$$ 21 = 2^4 + 2^2 + 2^1 $$

因此，长度为 $21$ 的数组可以拆分为 3 个子区间，分别表示为：
- $[2^4 + 2^2 + 1]$
- $[2^4 + 2^2 + 20]$

在树状数组中，`lowbit(x)` 是指 $x$ 对应二进制中最后一个 1 所代表的值。通过 `lowbit(x)` 可以实现对区间的拆分和查询。

---

### `lowbit(x)` 的计算方法

`lowbit(x)` 表示 $x$ 对应二进制的最后一个 1 向后的值。其计算方式为：
$$ \text{lowbit}(x) = x \& (-x) $$

#### 示例：
- 对于 $x = 10$（二进制为 `1010`），`lowbit(10)` 返回 `2`（二进制为 `0010`）。
- 对于 $x = 40$（二进制为 `101000`），`lowbit(40)` 返回 `8`（二进制为 `01000`）。

这个操作是通过取 $x$ 和其补码 $-x$ 的按位与运算得到的。

---

### 树状数组的划分方法

在树状数组中，考虑以 `a[x]` 结尾的区间，其区间长度为 `x` 的最后一个 1 所对应的 2 的次幂，具体可通过 `lowbit(x)` 来划分。

例如：
- 对于某个结点 $x$，它管理的区间大小为 `lowbit(x)`。

树状数组有以下特点：
- 除根结点外，结点 $x$ 的父结点为：$x + \text{lowbit}(x)$。
- 对于一个长度为 $n$ 的数组，树状数组的深度为 $\log(n)$。

通常，树状数组的下标是从 1 开始的，因为如果从 0 开始，`lowbit(0) = 0`，这可能导致死循环。

---

## 2. 树状数组的操作

### 树状数组修改元素

树状数组的单点修改是通过将 `c[x]` 加上某个值 $k$ 来实现的。具体步骤如下：
1. 修改结点 $x$ 对应的值：$c[x] += k$。
2. 将修改向上传播，直到 $x$ 超过数组长度。

```cpp
void update(int x, int k, int n) {
    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += k;
    }
}

树状数组及应用

1. 什么是树状数组

树状数组（Binary Indexed Tree, BIT）是一种数据结构，主要用于数组的单点修改和区间求和，支持在 $O(\log n)$ 时间内完成查询和更新操作。
传统的前缀和方法可以在 $O(1)$ 时间内查询区间和，但如果修改一个点的值，需要重新计算整个前缀和数组，这需要 $O(n)$ 时间复杂度。树状数组通过树形结构优化了单点修改和区间求和操作。

树状数组的拆分原理

例如，对于一个长度为 $21$ 的数组，其二进制表示为 10101，即： $$ 21 = 2^4 + 2^2 + 2^1 $$

因此，长度为 $21$ 的数组可以拆分为 3 个子区间，分别表示为： - $[2^4 + 2^2 + 1]$ - $[2^4 + 2^2 + 20]$

在树状数组中，lowbit(x) 是指 $x$ 对应二进制中最后一个 1 所代表的值。通过 lowbit(x) 可以实现对区间的拆分和查询。

`lowbit(x)` 的计算方法

lowbit(x) 表示 $x$ 对应二进制的最后一个 1 向后的值。其计算方式为： $$ \text{lowbit}(x) = x \& (-x) $$

示例：

对于 $x = 10$（二进制为 1010），lowbit(10) 返回 2（二进制为 0010）。
对于 $x = 40$（二进制为 101000），lowbit(40) 返回 8（二进制为 01000）。

这个操作是通过取 $x$ 和其补码 $-x$ 的按位与运算得到的。

树状数组的划分方法

在树状数组中，考虑以 a[x] 结尾的区间，其区间长度为 x 的最后一个 1 所对应的 2 的次幂，具体可通过 lowbit(x) 来划分。

例如： - 对于某个结点 $x$，它管理的区间大小为 lowbit(x)。

树状数组有以下特点： - 除根结点外，结点 $x$ 的父结点为：$x + \text{lowbit}(x)$。 - 对于一个长度为 $n$ 的数组，树状数组的深度为 $\log(n)$。

通常，树状数组的下标是从 1 开始的，因为如果从 0 开始，lowbit(0) = 0，这可能导致死循环。

2. 树状数组的操作

树状数组修改元素

树状数组的单点修改是通过将 c[x] 加上某个值 $k$ 来实现的。具体步骤如下： 1. 修改结点 $x$ 对应的值：$c[x] += k$。 2. 将修改向上传播，直到 $x$ 超过数组长度。

```cpp void update(int x, int k, int n) { for (int i = x; i <= n; i += lowbit(i)) { c[i] += k; } }

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