# 【GESP/CSP练习】GESP八级 / CSP-S 题解：luogu-P3374 【模板】树状数组 1

> Author: OneCoder (李宏哲) | Canonical: https://www.coderli.com/gesp-8-luogu-p3374/
> Published: 2026-10-08 | Topic: CSP / NOIP 信奥竞赛 / CSP-S
> Tags: 洛谷, C++, 数据结构, 树状数组, 二进制, 前缀和, GESP八级, CSP-S

在序列维护与区间统计问题中，单点动态修改与区间和查询是一对经典而基础的矛盾操作：静态前缀和虽然能支持 $O(1)$ 的高速区间查询，但在面对单点修改时需要重构后续所有前缀和，单次更新开销高达 $O(n)$；普通数组虽具备 $O(1)$ 的原地单点写入效率，但任意区间的求和却退化为 $O(n)$ 的线性遍历。当序列长度 $n$ 与操作指令总数 $m$ 双双达到 $5 \times 10^5$ 规模时，前述两种朴素方案均会导致总运算量突破 $2.5 \times 10^{11}$ 次而彻底超时（TLE）。洛谷 P3374「【模板】树状数组 1」是 CCF GESP 八级与 CSP-S 组别中最为核心的基础高级数据结构经典题目，它考察如何利用**树状数组（Binary Indexed Tree / Fenwick Tree）**，借助二进制最低有效位（`lowbit(x) = x & (-x)`）的层级管辖机制，将前缀和拆解为至多对数阶不相交子区间的并集，从而在极简常数与仅 $O(n)$ 线性空间消耗下，同时将单点增量修改与区间求和的时间复杂度平衡至 $O(\log n)$。题目洛谷官方难度评级为`普及/提高-`。

## luogu-P3374 【模板】树状数组 1

> 🔗 **洛谷原题传送门**：[luogu-P3374 【模板】树状数组 1](https://www.luogu.com.cn/problem/P3374)

### 题目描述

如题，已知一个数列，你需要进行下面两种操作：

- 将某一个数加上 $x$

- 求出某区间每一个数的和

## 输入格式

第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。   
 
第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

- `1 x k`  含义：将第 $x$ 个数加上 $k$

- `2 x y`  含义：输出区间 $[x,y]$ 内每个数的和

## 输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

## 样例 #1

### 样例输入 #1
```text
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
```

### 样例输出 #1

```text
14
16
```

## 提示

【数据范围】

对于 $30\%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；   
对于 $70\%$ 的数据，$1\le n,m \le 10^4$；   
对于 $100\%$ 的数据，$1\le n,m \le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

样例说明：

 ![](https://cdn.luogu.com.cn/upload/pic/2256.png) 

故输出结果14、16

---

### 题目深度剖析

#### 1. 经典权衡困境：静态前缀和 vs 动态单点更新

在序列的统计与维护中，常见以下两种极端方案：
- **方案 A（朴素数组）**：
  - 单点修改：直接定位数组下标赋值或自增，时间复杂度为 $O(1)$；
  - 区间求和：遍历区间 $[x, y]$，单次求和需要累加 $y - x + 1$ 个元素，最坏时间复杂度为 $O(n)$。
- **方案 B（静态前缀和）**：
  - 区间求和：利用 $S(y) - S(x - 1)$，仅需一次减法运算，时间复杂度为 $O(1)$；
  - 单点修改：修改第 $x$ 个元素后，所有包含该位置的前缀和 $S(x), S(x+1), \dots, S(n)$ 都必须同步更新，最坏时间复杂度为 $O(n)$。

当 $n, m \le 5 \times 10^5$ 时，混合操作次数达到 $5 \times 10^5$ 阶，无论是方案 A 还是方案 B，在最坏输入下总运算步数均达 $O(m \cdot n) \approx 2.5 \times 10^{11}$ 次，必须寻求一种将两种操作均降至对数阶 $O(\log n)$ 的平衡数据结构。

#### 2. 树状数组（BIT）的数学骨架：二进制分解与 lowbit 运算

任何正整数 $x$ 在计算机底层均可唯一表示为若干个互不相同的 2 的非负整数幂次之和：
$$x = 2^{k_1} + 2^{k_2} + \dots + 2^{k_p} \quad (k_1 > k_2 > \dots > k_p \ge 0)$$

树状数组（Binary Indexed Tree，简称 BIT）的核心洞见在于：**利用这种二进制分解，将序列的前缀区间 $[1, x]$ 划分为至多 $\lfloor \log_2 x \rfloor + 1$ 个长度为 2 的幂次的互不重叠的小区间**。

- **`lowbit` 定义与位运算技巧**：
  定义 $\text{lowbit}(x)$ 为非负整数 $x$ 在二进制表示下最低位的 1 及其后所有 0 所构成的权值（即 $x$ 的二进制表示中最低位的 $2^k$）。
  在计算机原码、反码与补码表示法中，负数 $-x$ 的补码等于 $x$ 的按位取反加一，即：
  $$-x = (\sim x) + 1$$
  由于 $x$ 中最低位 1 右侧全部为 0，取反后变为 1，再加 1 则向左进位，恰好使得最低位 1 保留，而该位左侧所有二进制位均取反。因此，按位与运算能以极高的常数提取出该权值：
  $$\text{lowbit}(x) = x \ \& \ (-x)$$

- **树状数组节点的管辖区间**：
  设树状数组的存储数组为 `tree`，其中节点 $x$ 负责管辖原数组中一段长度为 $\text{lowbit}(x)$ 且以 $x$ 为右端点的连续区间：
  $$\text{tree}[x] = \sum_{i = x - \text{lowbit}(x) + 1}^{x} a[i]$$
  例如：
  - $x = 1 = (001)_2$：$\text{lowbit}(1) = 1$，管辖区间 $(0, 1] = [1, 1]$；
  - $x = 2 = (010)_2$：$\text{lowbit}(2) = 2$，管辖区间 $(0, 2] = [1, 2]$；
  - $x = 4 = (100)_2$：$\text{lowbit}(4) = 4$，管辖区间 $(0, 4] = [1, 4]$；
  - $x = 6 = (110)_2$：$\text{lowbit}(6) = 2$，管辖区间 $(4, 6] = [5, 6]$。

#### 3. 单点修改与区间查询的树形跃迁机制

树状数组巧妙地构筑了一棵隐式的树形拓扑结构，其树形跃迁方向由二进制进位与借位天然界定：

1. **前缀和查询：沿树向左下方折跃（减去 lowbit）**
   - 目标：求区间 $[1, x]$ 的累加和 $\text{sum}(x)$。
   - 流程：
     1. 累加当前节点管辖的和：$\text{sum} \leftarrow \text{sum} + \text{tree}[x]$；
     2. 将下标更新为该区间左端点的左侧相邻位置：$x \leftarrow x - \text{lowbit}(x)$；
     3. 重复执行，直到 $x = 0$。
   - 复杂度：每步消除二进制中的一个最低位 1，$x$ 的二进制表示中至多有 $\lfloor \log_2 x \rfloor + 1$ 个 1，因而前缀和查询的步数严格不超过 $\log_2 n$，耗时 $O(\log n)$。

2. **单点增量更新：沿树向右上方蔓延（加上 lowbit）**
   - 目标：将原数组中第 $x$ 个元素增加 $\text{val}$。
   - 流程：
     1. 只要当前节点 $x$ 仍在有效范围内（$x \le n$），其管辖区间必然包含原数组第 $x$ 项，执行更新：$\text{tree}[x] \leftarrow \text{tree}[x] + \text{val}$；
     2. 向上传递至其在树状数组中的直接父节点：$x \leftarrow x + \text{lowbit}(x)$；
     3. 持续向上跃迁，直至越过数组边界 $n$。
   - 复杂度：向上跳转等价于在最低有效位处执行二进制加法产生连续进位，跃迁次数同样受限于 $\lfloor \log_2 n \rfloor + 1$，耗时严格为 $O(\log n)$。

3. **任意闭区间 $[x, y]$ 的和查询（容斥原理）**
   - 原数组连续闭区间 $[x, y]$ 的元素和等于前缀和 $S(y)$ 与前缀和 $S(x - 1)$ 的差值：
     $$\sum_{i=x}^y a[i] = \text{query}(y) - \text{query}(x - 1)$$
   - 两次单次耗时 $O(\log n)$ 的前缀和查询即可精准得出闭区间和。

#### 4. 树状数组 vs 线段树的架构对比与工程优势

虽然线段树（Segment Tree）同样能以 $O(\log n)$ 时间解决单点修改与区间查询，但相比于线段树，树状数组在处理此类经典问题时具备无可比拟的工程优势：
- **代码体量与心智负担极小**：树状数组的核心逻辑仅需 `lowbit`、`update` 和 `query` 三个函数，核心代码不足 20 行，编写调试零心智负担；
- **极小常数因子（Ultra-low Constant Factor）**：线段树需要通过递归树或自底向上位运算操作左儿子与右儿子，常数开销较大；树状数组本质为极短的平直单层循环与位运算，常数仅为线段树的数分之一；
- **内存极致紧凑**：线段树需要开辟 $4n$ 规模的节点空间；树状数组仅需 $1n$ 的静态一维数组，节省了四分之三的内存占用，具备绝佳的 CPU 缓存（L1/L2 Cache）亲和力。

---

### C++11 标准参考程序

```cpp
/**
 * 题目: 【GESP/CSP练习】GESP八级 / CSP-S 题解：luogu-P3374 【模板】树状数组 1
 * 题号: P3374
 * 归属: GESP八级 / CSP-S / 高级数据结构·树状数组模板题
 * 博客: https://www.coderli.com/gesp-8-luogu-p3374/
 * 标准: C++11 (严格遵循 CCF GESP 官方规范)
 */

#include <iostream>
#include <vector>

using namespace std;

// 最大元素个数
const int MAXN = 500005;

// 数列长度 n 与操作次数 m
int n, m;

// 树状数组存储数组，采用 long long 防止累加和溢出
long long tree[MAXN];

/**
 * 计算低位二进制位 lowbit(x)
 * 返回 x 在二进制表示下最低位的 1 及其后所有 0 构成的数值
 * 利用补码性质：-x = ~x + 1，因此 x & (-x) 即为最低位的二进制权值
 * @param x 正整数索引
 * @return 最低位二进制权值
 */
int lowbit(int x) {
    return x & (-x);
}

/**
 * 树状数组单点增加操作
 * 将序列中第 x 个元素的值增加 val
 * 沿树状数组向根部跃迁，逐层更新包含该位置的所有树状数组区间节点
 * @param x 目标位置下标（1-indexed）
 * @param val 增加的增量值
 */
void update(int x, long long val) {
    for (; x <= n; x += lowbit(x)) {
        tree[x] += val;
    }
}

/**
 * 树状数组前缀和查询操作
 * 计算原数组区间 [1, x] 内所有元素的累加和
 * 沿树状数组向左折跃，累加每个由 lowbit 覆盖的不相交子区间权值
 * @param x 前缀终止下标（1-indexed）
 * @return 前缀区间 [1, x] 的元素和
 */
long long query_prefix(int x) {
    long long sum = 0;
    for (; x > 0; x -= lowbit(x)) {
        sum += tree[x];
    }
    return sum;
}

/**
 * 树状数组区间和查询操作
 * 利用前缀和容斥原理求闭区间 [x, y] 内所有元素的和
 * 区间和等于前缀和 S(y) 减去前缀和 S(x - 1)
 * @param x 区间起始下标（1-indexed）
 * @param y 区间终止下标（1-indexed）
 * @return 区间 [x, y] 的元素和
 */
long long query_range(int x, int y) {
    return query_prefix(y) - query_prefix(x - 1);
}

int main() {
    cin >> n >> m;

    // 读入初始序列元素并构建树状数组
    for (int i = 1; i <= n; ++i) {
        long long val;
        cin >> val;
        update(i, val);
    }

    // 处理 m 次操作
    for (int i = 0; i < m; ++i) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int x;
            long long k;
            cin >> x >> k;
            update(x, k);
        } else if (opt == 2) {
            int x, y;
            cin >> x >> y;
            cout << query_range(x, y) << "\n";
        }
    }

    return 0;
}
```

---

### 算法复杂度全面分析

1. **时间复杂度分析**：
   - **单点增量更新 `update(x, val)`**：每次循环下标增加 $\text{lowbit}(x)$，在 $[1, n]$ 范围内至多迭代 $\lceil \log_2 n \rceil$ 次，单次耗时 $O(\log n)$；
   - **单点建树过程**：读入 $n$ 个初始元素，每个元素调用一次 `update`，建树总耗时为 $O(n \log n)$；
   - **前缀和与区间和查询 `query_range(x, y)`**：单次区间和转化为两次前缀和查询，单次循环消除一个二进制位 1，至多迭代 $\lceil \log_2 n \rceil$ 次，单次查询耗时 $O(\log n)$；
   - **整体时间复杂度**：处理 $m$ 次混合操作与 $n$ 个初始元素，总时间复杂度为 $O((n + m) \log n)$。代入 $n, m = 5 \times 10^5$，$\log_2(5 \times 10^5) \approx 19$，基本运算总步数约 $1.9 \times 10^7$ 次，加上平直循环无分支开销的极小常数因子，可在 1.0 秒时限内飞速跑完。

2. **空间复杂度分析**：
   - **状态存储数组**：树状数组维护 $n$ 个位置的累加权值，仅需开辟一个大小为 $n + 1$ 的一维长整型数组 `tree[MAXN]`；
   - **内存实际占用**：$500005 \times 8 \text{ 字节} \approx 4.0 \text{ MB}$；
   - **整体空间复杂度**：严格为 $O(n)$，远低于题目给定的 512.00 MB 空间限制，空间效率极为优异。

---
Source: OneCoder (https://www.coderli.com/gesp-8-luogu-p3374/) | GESP Wiki: https://wiki.coderli.com/ | OI-Game: https://oi.coderli.com/
