【GESP/CSP练习】GESP八级 / CSP-S 题解:luogu-P3374 【模板】树状数组 1
在序列维护与区间统计问题中,单点动态修改与区间和查询是一对经典而基础的矛盾操作:静态前缀和虽然能支持 O(1) 的高速区间查询,但在面对单点修改时需要重构后续所有前缀和,单次更新开销高达 O(n);普通数组虽具备 O(1) 的原地单点写入效率,但任意区间的求和却退化为...
在序列维护与区间统计问题中,单点动态修改与区间和查询是一对经典而基础的矛盾操作:静态前缀和虽然能支持 的高速区间查询,但在面对单点修改时需要重构后续所有前缀和,单次更新开销高达 ;普通数组虽具备 的原地单点写入效率,但任意区间的求和却退化为 的线性遍历。当序列长度 与操作指令总数 双双达到 规模时,前述两种朴素方案均会导致总运算量突破 次而彻底超时(TLE)。洛谷 P3374「【模板】树状数组 1」是 CCF GESP 八级与 CSP-S 组别中最为核心的基础高级数据结构经典题目,它考察如何利用树状数组(Binary Indexed Tree / Fenwick Tree),借助二进制最低有效位(lowbit(x) = x & (-x))的层级管辖机制,将前缀和拆解为至多对数阶不相交子区间的并集,从而在极简常数与仅 线性空间消耗下,同时将单点增量修改与区间求和的时间复杂度平衡至 。题目洛谷官方难度评级为普及/提高-。
luogu-P3374 【模板】树状数组 1
🔗 洛谷原题传送门:luogu-P3374 【模板】树状数组 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
-
将某一个数加上
-
求出某区间每一个数的和
输入格式
第一行包含两个正整数 ,分别表示该数列数字的个数和操作的总个数。
第二行包含 个用空格分隔的整数,其中第 个数字表示数列第 项的初始值。
接下来 行每行包含 个整数,表示一个操作,具体如下:
-
1 x k含义:将第 个数加上 -
2 x y含义:输出区间 内每个数的和
输出格式
输出包含若干行整数,即为所有操作 的结果。
样例 #1
样例输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4样例输出 #1
14
16提示
【数据范围】
对于 的数据,,;
对于 的数据,;
对于 的数据,。
数据保证对于任意时刻, 的任意子区间(包括长度为 和 的子区间)和均在 范围内。
样例说明:

故输出结果14、16
题目深度剖析
1. 经典权衡困境:静态前缀和 vs 动态单点更新
在序列的统计与维护中,常见以下两种极端方案:
- 方案 A(朴素数组):
- 单点修改:直接定位数组下标赋值或自增,时间复杂度为 ;
- 区间求和:遍历区间 ,单次求和需要累加 个元素,最坏时间复杂度为 。
- 方案 B(静态前缀和):
- 区间求和:利用 ,仅需一次减法运算,时间复杂度为 ;
- 单点修改:修改第 个元素后,所有包含该位置的前缀和 都必须同步更新,最坏时间复杂度为 。
当 时,混合操作次数达到 阶,无论是方案 A 还是方案 B,在最坏输入下总运算步数均达 次,必须寻求一种将两种操作均降至对数阶 的平衡数据结构。
2. 树状数组(BIT)的数学骨架:二进制分解与 lowbit 运算
任何正整数 在计算机底层均可唯一表示为若干个互不相同的 2 的非负整数幂次之和:
树状数组(Binary Indexed Tree,简称 BIT)的核心洞见在于:利用这种二进制分解,将序列的前缀区间 划分为至多 个长度为 2 的幂次的互不重叠的小区间。
-
lowbit定义与位运算技巧: 定义 为非负整数 在二进制表示下最低位的 1 及其后所有 0 所构成的权值(即 的二进制表示中最低位的 )。 在计算机原码、反码与补码表示法中,负数 的补码等于 的按位取反加一,即: 由于 中最低位 1 右侧全部为 0,取反后变为 1,再加 1 则向左进位,恰好使得最低位 1 保留,而该位左侧所有二进制位均取反。因此,按位与运算能以极高的常数提取出该权值: -
树状数组节点的管辖区间: 设树状数组的存储数组为
tree,其中节点 负责管辖原数组中一段长度为 且以 为右端点的连续区间: 例如:- :,管辖区间 ;
- :,管辖区间 ;
- :,管辖区间 ;
- :,管辖区间 。
3. 单点修改与区间查询的树形跃迁机制
树状数组巧妙地构筑了一棵隐式的树形拓扑结构,其树形跃迁方向由二进制进位与借位天然界定:
-
前缀和查询:沿树向左下方折跃(减去 lowbit)
- 目标:求区间 的累加和 。
- 流程:
- 累加当前节点管辖的和:;
- 将下标更新为该区间左端点的左侧相邻位置:;
- 重复执行,直到 。
- 复杂度:每步消除二进制中的一个最低位 1, 的二进制表示中至多有 个 1,因而前缀和查询的步数严格不超过 ,耗时 。
-
单点增量更新:沿树向右上方蔓延(加上 lowbit)
- 目标:将原数组中第 个元素增加 。
- 流程:
- 只要当前节点 仍在有效范围内(),其管辖区间必然包含原数组第 项,执行更新:;
- 向上传递至其在树状数组中的直接父节点:;
- 持续向上跃迁,直至越过数组边界 。
- 复杂度:向上跳转等价于在最低有效位处执行二进制加法产生连续进位,跃迁次数同样受限于 ,耗时严格为 。
-
任意闭区间 的和查询(容斥原理)
- 原数组连续闭区间 的元素和等于前缀和 与前缀和 的差值:
- 两次单次耗时 的前缀和查询即可精准得出闭区间和。
4. 树状数组 vs 线段树的架构对比与工程优势
虽然线段树(Segment Tree)同样能以 时间解决单点修改与区间查询,但相比于线段树,树状数组在处理此类经典问题时具备无可比拟的工程优势:
- 代码体量与心智负担极小:树状数组的核心逻辑仅需
lowbit、update和query三个函数,核心代码不足 20 行,编写调试零心智负担; - 极小常数因子(Ultra-low Constant Factor):线段树需要通过递归树或自底向上位运算操作左儿子与右儿子,常数开销较大;树状数组本质为极短的平直单层循环与位运算,常数仅为线段树的数分之一;
- 内存极致紧凑:线段树需要开辟 规模的节点空间;树状数组仅需 的静态一维数组,节省了四分之三的内存占用,具备绝佳的 CPU 缓存(L1/L2 Cache)亲和力。
C++11 标准参考程序
/**
* 题目: 【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;
}算法复杂度全面分析
-
时间复杂度分析:
- 单点增量更新
update(x, val):每次循环下标增加 ,在 范围内至多迭代 次,单次耗时 ; - 单点建树过程:读入 个初始元素,每个元素调用一次
update,建树总耗时为 ; - 前缀和与区间和查询
query_range(x, y):单次区间和转化为两次前缀和查询,单次循环消除一个二进制位 1,至多迭代 次,单次查询耗时 ; - 整体时间复杂度:处理 次混合操作与 个初始元素,总时间复杂度为 。代入 ,,基本运算总步数约 次,加上平直循环无分支开销的极小常数因子,可在 1.0 秒时限内飞速跑完。
- 单点增量更新
-
空间复杂度分析:
- 状态存储数组:树状数组维护 个位置的累加权值,仅需开辟一个大小为 的一维长整型数组
tree[MAXN]; - 内存实际占用:;
- 整体空间复杂度:严格为 ,远低于题目给定的 512.00 MB 空间限制,空间效率极为优异。
- 状态存储数组:树状数组维护 个位置的累加权值,仅需开辟一个大小为 的一维长整型数组
看完题解,马上用 240 关实战检验掌握度
覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。
配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。
同专栏相关推荐
【GESP/CSP练习】GESP八级 / CSP-S 题解:luogu-P3368 【模板】树状数组 2
在序列维护与动态统计问题中,区间修改与单点查询是一对经典的操作矛盾:朴素数组方案虽然能够以 O(1) 的高速常数读取任意单个位置的数值,但在面对区间 [x, y] 的批量累加修改时,必须逐个遍历修改区间内的每个元素,单次操作开销高达 O(n);若直接套用标准树状数组(B...
【GESP/CSP练习】GESP八级 / CSP-S 题解:luogu-P3372 【模板】线段树 1
在序列维护与动态区间统计问题中,同时支持「区间批量增量修改」与「区间任意求和查询」是高阶算法竞赛的核心分水岭:朴素静态数组在进行区间 [x, y] 逐项累加时单次开销高达 O(n),多次操作会导致严重超时;静态前缀和数组虽能以 O(1) 实现区间求和,但在区间修改后需重...
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务
生活与工业生产中的工序流水线调度,天然蕴含着严苛的时序依赖:地基未筑不可起高楼,原料未至不可开炉灶。洛谷 P1113「[USACO02FEB] 杂务」以牧场日常作业为背景,生动抽象出工程管理与图论中的核心模型——有向无环图(DAG)的关键路径与最早完成时间计算(Crit...
OneCoder
始于 2012持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com