1. 问题引入从一道国赛真题说起去年蓝桥杯国赛研究生组的赛场上有一道题让我印象特别深刻就是这道“最大公约数”。题目本身描述并不复杂给定一个长度为 N 的整数数组 A然后有 M 次操作。操作分两种一是将某个区间 [l, r] 内的所有数都加上一个值 k二是查询某个区间 [l, r] 内所有数的最大公约数GCD。数据范围 N 和 M 都在 10^5 级别k 和数组初始值也都在整数范围内。乍一看这题像是线段树的经典应用——区间修改、区间查询。但如果你真拿普通的线段树模板去套大概率会吃瘪。因为这里查询的是 GCD而区间修改是加法。GCD 运算有一个非常“不友好”的性质它不满足区间可加性。简单来说整个区间的 GCD并不等于左半区间的 GCD 和右半区间的 GCD 的 GCD。更致命的是当你对区间进行加法操作后整个区间的 GCD 可能会发生你无法通过简单合并子区间信息来推算的变化。我当时的第一反应也是线段树但很快就卡在了区间修改如何维护 GCD 这个问题上。赛后和几个朋友交流发现大家普遍在这里栽了跟头。后来经过反复推敲和查阅资料才找到了“线段树差分二分”这套组合拳的解法。这道题的精妙之处在于它巧妙地将一个看似无法直接维护的问题通过数学变换转化为了两个可以高效维护的子问题。今天我就把这套思路的来龙去脉、代码实现细节以及我踩过的几个坑完整地梳理一遍。2. 核心破局点从区间GCD到差分数组GCD的转化直接维护区间加法下的 GCD 是行不通的我们必须换个思路。这里的关键洞察来自于一个经典的数论结论它也是解决本题的基石对于一个序列 a[1], a[2], ..., a[n]设其差分数组为 d其中 d[i] a[i] - a[i-1] (规定 a[0] 0)。那么区间 [l, r] 的 GCD即 gcd(a[l], a[l1], ..., a[r])等于 gcd(a[l], gcd(d[l1], d[l2], ..., d[r]))。我们来证明一下这个结论。根据辗转相除法的原理更相减损术有 gcd(x, y) gcd(x, y - x)。将其推广到多个数 gcd(a[l], a[l1], ..., a[r]) gcd(a[l], a[l1] - a[l], a[l2] - a[l1], ..., a[r] - a[r-1])。 而 a[l1] - a[l] 正是 d[l1]a[l2] - a[l1] 是 d[l2]以此类推。因此原区间的 GCD 就等于第一个元素 a[l] 和差分区间 [l1, r] 的 GCD 的 GCD。这个转化为什么如此重要因为它把问题拆解了查询 a[l]我们需要能快速查询原序列中任意一个位置的值。查询差分数组 d 在区间 [l1, r] 上的 GCD我们需要能快速查询差分数组任意区间的 GCD。现在我们来看区间加法操作对这两个部分的影响对原序列 a 的影响区间 [l, r] 加 k意味着 a[l], a[l1], ..., a[r] 每个数都增加了 k。这是一个典型的区间修改、单点查询问题。我们可以用树状数组或带懒标记的线段树来高效维护。对差分数组 d 的影响根据定义 d[i] a[i] - a[i-1]。当区间 [l, r] 加 k 时d[l] a[l] k - a[l-1] (a[l] - a[l-1]) k d[l] k。d[r1] a[r1] - (a[r] k) (a[r1] - a[r]) - k d[r1] - k。对于 l i rd[i] (a[i] k) - (a[i-1] k) a[i] - a[i-1] d[i]值不变。 看区间加法在差分数组上神奇地变成了两个单点修改d[l] 加 k d[r1] 减 k于是整个问题的维护模型就清晰了维护原数组 a支持区间加修改和单点查查询 a[l]。用树状数组或线段树。维护差分数组 d支持单点修改对应原数组的区间加和区间查询查询 d[l1, r] 的 GCD。用线段树最为合适因为线段树天然支持区间信息的合并这里是 GCD 运算。至此我们成功地将一个“区间加、区间查 GCD”的难题转化为了“区间加/单点查”和“单点改/区间查 GCD”两个经典数据结构的组合问题。复杂度也从不可行变成了每次操作 O(log N)。3. 数据结构选型与实现细节理论通了接下来就是具体的代码实现。这里有几个关键的设计决策和实现细节。3.1 维护原数组树状数组 vs 线段树对于“区间加、单点查”这个需求树状数组和线段树都能实现。我个人的偏好是使用树状数组因为它代码更简洁常数更小。树状数组通常用于“单点修改、区间查询”。如何让它支持“区间修改、单点查询”呢这需要利用差分的思想第二次用到了。我们维护另一个差分数组bit。当我们要对原数组a的区间[l, r]加上k时我们执行add(l, k)add(r1, -k)这里的add(i, val)是树状数组的标准单点加法操作。那么查询原数组a[x]的值就等于初始值a_init[x]加上树状数组bit的前缀和sum(x)。因为bit的add(l, k)操作影响了所有i l的sum(i)相当于给a[l], a[l1], ...都加了 k而add(r1, -k)则从r1开始抵消了这个影响。代码片段树状数组class BIT { private: vectorlong long tree; // 注意用 long long 防溢出 int n; public: BIT(int size) : n(size), tree(size 2, 0) {} void add(int idx, long long delta) { for (; idx n; idx idx -idx) tree[idx] delta; } long long query(int idx) { // 前缀和查询 long long res 0; for (; idx 0; idx - idx -idx) res tree[idx]; return res; } // 区间 [l, r] 加 k void range_add(int l, int r, long long k) { add(l, k); if (r 1 n) add(r 1, -k); } // 查询原数组 a[pos] 的当前值 long long point_query(int pos, const vectorlong long init_a) { return init_a[pos] query(pos); } };注意数组下标通常从1开始方便处理。init_a是原数组的初始值需要预先存储。3.2 维护差分数组线段树求区间GCD对于差分数组d我们需要支持单点修改和区间 GCD 查询。线段树是完美选择。线段树的每个节点维护对应区间的 GCD 值。合并两个子节点信息时直接取gcd(left_gcd, right_gcd)即可。单点修改时从根节点递归到目标叶子节点更新其值然后回溯更新所有祖先节点的 GCD 值。区间查询时也是标准的线段树查询逻辑将查询区间[L, R]划分为线段树上若干个不相交的区间的并集分别获取这些区间的 GCD最后再求一次总 GCD。这里有一个极其重要的细节GCD 运算中gcd(x, 0) |x|。但在实现时我们通常希望区间内所有数都是0时GCD 返回0。然而在查询差分区间[l1, r]时如果l1 r即查询区间长度为0我们应该返回0因为gcd(a[l], 0) a[l]这符合我们的数学定义。因此在线段树的query函数中初始的res应该设为0。代码片段线段树节点与构建struct SegNode { int l, r; long long g; // 该节点对应区间的 gcd 值 }; class SegTree { private: vectorSegNode tree; vectorlong long arr; // 差分数组 d void push_up(int p) { tree[p].g gcd(tree[p*2].g, tree[p*21].g); } void build(int p, int l, int r) { tree[p].l l; tree[p].r r; if (l r) { tree[p].g arr[l]; return; } int mid (l r) / 2; build(p*2, l, mid); build(p*21, mid1, r); push_up(p); } public: SegTree(const vectorlong long diff_arr) : arr(diff_arr) { int n arr.size() - 1; // arr[0] 未使用有效下标 1~n tree.resize(4 * n); build(1, 1, n); } // 单点更新将位置 pos 的值改为 val void update(int p, int pos, long long val) { if (tree[p].l tree[p].r) { tree[p].g val; return; } int mid (tree[p].l tree[p].r) / 2; if (pos mid) update(p*2, pos, val); else update(p*21, pos, val); push_up(p); } // 区间查询 [L, R] 的 gcd long long query(int p, int L, int R) { if (L R) return 0; // 关键空区间 gcd 为 0 if (L tree[p].l tree[p].r R) { return tree[p].g; } int mid (tree[p].l tree[p].r) / 2; long long res 0; if (L mid) res gcd(res, query(p*2, L, R)); if (R mid) res gcd(res, query(p*21, L, R)); return res; } };3.3 整体操作流程与初始化有了这两个数据结构整个程序的框架就出来了初始化读入原数组初始值init_a[1..n]。构建差分数组d[1..n]其中d[1] init_a[1],d[i] init_a[i] - init_a[i-1]for i1。d[n1]可以设为0或忽略但为了处理rn时d[r1]的修改通常将数组开大一点。初始化树状数组bit所有值为0因为修改量初始为0。用差分数组d初始化线段树seg_tree。处理修改操作1 l r kbit.range_add(l, r, k)。seg_tree.update(1, l, seg_tree.arr[l] k)。注意这里需要先获取差分数组当前值然后加上k。更规范的做法是我们额外用一个数组diff维护差分数组的当前值每次更新它并用它去更新线段树。如果r1 n则seg_tree.update(1, r1, seg_tree.arr[r1] - k)。处理查询操作2 l rcurrent_al init_a[l] bit.query(l)。这是原数组a[l]的当前值。gcd_of_diff seg_tree.query(1, l1, r)。这是差分数组区间[l1, r]的 GCD。最终答案ans gcd(current_al, gcd_of_diff)。注意取绝对值因为 GCD 通常定义为正整数。gcd(x, y)函数内部一般会处理负数。4. 二分查找的用武之地与边界处理等等标题里不是还有“二分”吗在上述标准解法中我们似乎只用了线段树和树状数组。确实对于标准的区间查询二分并非必需。但是蓝桥杯这道题可能有一个经典的变种或隐含需求使得二分查找成为关键一步。常见的场景是查询通过多少次操作每次操作是给一个区间加1可以使整个数组的GCD变为1或一个更大的数。这类问题的解法通常是最终我们希望整个数组的 GCD 为 G。根据之前的结论整个数组的 GCD 等于gcd(a[1], gcd(d[2], d[3], ..., d[n]))。区间加操作反映在差分数组上是修改d[l]和d[r1]。特别地如果我们只操作前缀[1, pos]那么只会修改d[1]加k和d[pos1]减k。为了不影响到d[n1]通常我们不考虑我们可以选择操作[1, n]这样只修改d[1]。因此一个核心观察是通过操作我们只能改变d[1]即a[1]和某一个d[x] (x1)的值。而gcd(d[2], d[3], ..., d[n])这个值我们可以通过操作来尝试减小它通过修改某个d[x]。问题转化为至少需要操作多少次每次让某个d[x]减少多少才能使得gcd(a[1], G_diff) G其中G_diff是操作后d[2..n]的 GCD。这时二分查找就派上用场了。我们可以二分答案——操作的次数cnt。对于每个二分的mid我们判断能否在mid次操作内通过调整某个d[x]x从2到n使得新的G_diff与a[1]的 GCD 达到目标值。判断的过程可能又需要枚举或利用一些数学性质。另一种更常见的二分应用场景是题目本身的查询可能不是直接给[l, r]而是问满足某个条件的最左/最右端点。例如“求最大的r使得区间[l, r]的 GCD 大于等于k”。由于区间 GCD 具有单调性固定左端点l向右扩展r区间 GCD 单调不增我们可以对右端点r进行二分。对于每个猜测的mid用线段树O(log N)快速求出[l, mid]的 GCD然后与k比较调整二分边界。边界处理是这类题目调试的重灾区下标从1开始强烈建议可以避免很多1/-1的混乱。输入数据如果从0开始读入后统一转到从1开始存储。差分数组大小差分数组d的长度应为n1使用d[1]到d[n]d[n1]作为哨兵。这样对于rn的修改d[r1]才有位置。空区间查询在线段树查询[l1, r]时如果l r那么查询区间就是[r1, r]这是一个非法区间左右。必须特判这种情况直接返回0。这就是为什么我在query函数开头判断if (L R) return 0;。数据范围与溢出区间加操作可能多次进行a[i]的当前值可能超出int范围。同样在求 GCD 的过程中中间值也可能很大。一律使用long long是最保险的做法。GCD 与负数C 的std::gcdC17或自己实现的欧几里得算法通常对负数返回的也是负数其绝对值是最大公约数。在最后输出时可能需要取abs()。5. 实战编码完整代码框架与调试心得将以上所有部分整合下面给出一个应对标准问题操作1区间加操作2区间查GCD的完整代码框架。假设输入格式为第一行 n, m第二行 n 个整数 init_a[1..n]接下来 m 行每行op l r (k)。#include bits/stdc.h using namespace std; typedef long long ll; // 树状数组区间加单点查 class BIT { vectorll tree; int n; public: BIT(int size) : n(size), tree(size 2, 0) {} void add(int idx, ll delta) { for (; idx n; idx idx -idx) tree[idx] delta; } ll query(int idx) { ll res 0; for (; idx 0; idx - idx -idx) res tree[idx]; return res; } void range_add(int l, int r, ll k) { add(l, k); if (r 1 n) add(r 1, -k); } }; // 线段树单点改区间查GCD class SegTree { struct Node { int l, r; ll g; }; vectorNode tree; vectorll arr; // 引用外部差分数组方便同步更新 void push_up(int p) { tree[p].g __gcd(tree[p*2].g, tree[p*21].g); } void build(int p, int l, int r) { tree[p].l l; tree[p].r r; if (l r) { tree[p].g arr[l]; return; } int mid (l r) 1; build(p*2, l, mid); build(p*21, mid1, r); push_up(p); } public: SegTree(vectorll diff_arr) : arr(diff_arr) { int n arr.size() - 1; tree.resize(4 * n); build(1, 1, n); } void update(int p, int pos, ll val) { if (tree[p].l tree[p].r) { tree[p].g val; arr[pos] val; // 同步更新外部数组 return; } int mid (tree[p].l tree[p].r) 1; if (pos mid) update(p*2, pos, val); else update(p*21, pos, val); push_up(p); } ll query(int p, int L, int R) { if (L R) return 0; if (L tree[p].l tree[p].r R) return tree[p].g; int mid (tree[p].l tree[p].r) 1; ll res 0; if (L mid) res __gcd(res, query(p*2, L, R)); if (R mid) res __gcd(res, query(p*21, L, R)); return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; vectorll init_a(n 1), diff(n 2, 0); // diff[1..n1] for (int i 1; i n; i) { cin init_a[i]; } // 构建差分数组 for (int i 1; i n; i) { diff[i] init_a[i] - init_a[i-1]; // init_a[0] 0 } BIT bit(n); SegTree seg(diff); while (m--) { int op, l, r; ll k; cin op l r; if (op 1) { cin k; // 1. 原数组区间加 bit.range_add(l, r, k); // 2. 差分数组单点改 seg.update(1, l, diff[l] k); if (r 1 n) { seg.update(1, r 1, diff[r 1] - k); } } else { // 查询区间 [l, r] 的 GCD ll al init_a[l] bit.query(l); ll diff_gcd seg.query(1, l 1, r); ll ans __gcd(abs(al), abs(diff_gcd)); // 取绝对值确保非负 cout ans \n; } } return 0; }调试心得与常见坑点差分数组的更新与线段树同步这是最容易出错的地方。在SegTree::update中我不仅更新了线段树节点还同步更新了外部引用的diff数组。这是因为下一次修改时我们需要基于当前最新的diff值进行增减。如果不同步下次更新就会使用旧的diff值导致错误。__gcd的使用我使用了__gcd这是 GNU 扩展在竞赛环境中普遍可用。它支持long long且能处理负数返回带符号的公约数。如果环境不允许需要自己实现一个ll gcd(ll a, ll b) { return b 0 ? a : gcd(b, a % b); }注意a % b对负数的行为可能不符合预期最好先取绝对值。初始化init_a[0]在计算diff[i] init_a[i] - init_a[i-1]时i1需要init_a[0]。我们将其初始化为0这符合逻辑假想原数组前有一个0。二分查找的循环条件如果题目涉及二分务必想清楚是找“第一个满足条件的”还是“最后一个满足条件的”对应lower_bound或upper_bound的变体。循环条件常用while (l r)根据检查函数check(mid)的结果来更新l或r最后l或r就是答案。二分边界l和r的初始值要包含所有可能答案。复杂度分析每次操作修改或查询涉及树状数组和线段树各一次操作时间复杂度均为 O(log N)。整体复杂度 O((NM) log N)对于 10^5 的数据量完全可行。空间复杂度 O(N)。这道题从“看似线段树模板题”到“发现GCD不满足区间可加性”的困惑再到“利用差分转化问题”的豁然开朗最后到“数据结构组合与边界处理”的细致实现完整地考察了选手的问题转化能力、数据结构应用能力和编码调试功底。它提醒我们面对复杂操作时不妨思考其数学本质看能否通过变换将问题映射到我们熟悉的数据结构模型上去。