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

所属专题CSP-S
题号标识P3374
代码 / 阅读C++11 · 16 min
累计阅读实时统计
TL;DR · 核心摘要

在序列维护与区间统计问题中,单点动态修改与区间和查询是一对经典而基础的矛盾操作:静态前缀和虽然能支持 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

Code· 7 行
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

样例输出 #1

Code· 2 行
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. 单点修改与区间查询的树形跃迁机制

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

  1. 前缀和查询:沿树向左下方折跃(减去 lowbit)

    • 目标:求区间 的累加和 。
    • 流程:
      1. 累加当前节点管辖的和:;
      2. 将下标更新为该区间左端点的左侧相邻位置:;
      3. 重复执行,直到 。
    • 复杂度:每步消除二进制中的一个最低位 1, 的二进制表示中至多有 个 1,因而前缀和查询的步数严格不超过 ,耗时 。
  2. 单点增量更新:沿树向右上方蔓延(加上 lowbit)

    • 目标:将原数组中第 个元素增加 。
    • 流程:
      1. 只要当前节点 仍在有效范围内(),其管辖区间必然包含原数组第 项,执行更新:;
      2. 向上传递至其在树状数组中的直接父节点:;
      3. 持续向上跃迁,直至越过数组边界 。
    • 复杂度:向上跳转等价于在最低有效位处执行二进制加法产生连续进位,跃迁次数同样受限于 ,耗时严格为 。
  3. 任意闭区间 的和查询(容斥原理)

    • 原数组连续闭区间 的元素和等于前缀和 与前缀和 的差值:
    • 两次单次耗时 的前缀和查询即可精准得出闭区间和。

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

虽然线段树(Segment Tree)同样能以 时间解决单点修改与区间查询,但相比于线段树,树状数组在处理此类经典问题时具备无可比拟的工程优势:

  • 代码体量与心智负担极小:树状数组的核心逻辑仅需 lowbit、update 和 query 三个函数,核心代码不足 20 行,编写调试零心智负担;
  • 极小常数因子(Ultra-low Constant Factor):线段树需要通过递归树或自底向上位运算操作左儿子与右儿子,常数开销较大;树状数组本质为极短的平直单层循环与位运算,常数仅为线段树的数分之一;
  • 内存极致紧凑:线段树需要开辟 规模的节点空间;树状数组仅需 的静态一维数组,节省了四分之三的内存占用,具备绝佳的 CPU 缓存(L1/L2 Cache)亲和力。

C++11 标准参考程序

C++· 101 行
/**
 * 题目: 【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):每次循环下标增加 ,在 范围内至多迭代 次,单次耗时 ;
    • 单点建树过程:读入 个初始元素,每个元素调用一次 update,建树总耗时为 ;
    • 前缀和与区间和查询 query_range(x, y):单次区间和转化为两次前缀和查询,单次循环消除一个二进制位 1,至多迭代 次,单次查询耗时 ;
    • 整体时间复杂度:处理 次混合操作与 个初始元素,总时间复杂度为 。代入 ,,基本运算总步数约 次,加上平直循环无分支开销的极小常数因子,可在 1.0 秒时限内飞速跑完。
  2. 空间复杂度分析:

    • 状态存储数组:树状数组维护 个位置的累加权值,仅需开辟一个大小为 的一维长整型数组 tree[MAXN];
    • 内存实际占用:;
    • 整体空间复杂度:严格为 ,远低于题目给定的 512.00 MB 空间限制,空间效率极为优异。
OneCoder 信奥远征平台 · oi.coderli.com

看完题解,马上用 240 关实战检验掌握度

覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。

立即闯关
开源代码与考纲字典

配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。

技术交流与考级答疑

欢迎加入 C++ GESP/CSP 群(688906745) 或 Java/Python 群(982860385)。

同专栏相关推荐

OneCoder

OneCoder

始于 2012

持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com

读者讨论与留言

共 0 条讨论
邮箱仅用于接收回复通知,不对外展示
还没有读者留言,欢迎写下你的第一条交流笔记。