1. 先搞清楚题目到底在要求什么线段树区间增加、区间 GCD 查询这个组合我第一次遇到的时候第一反应是“这不就是裸线段树吗”等真正上手才发现GCD 这个操作和加法根本不兼容。你没法在懒标记下推的时候用一个公式把父节点的区间 GCD 更新出来这个问题的难点恰好就在这。这道题的实际场景是给定一个长度为 n 的序列支持两类操作区间 [l, r] 内的每个数统一加上一个值 c查询区间 [l, r] 内所有数的最大公约数GCDn 和操作次数 m 都可达十万级别暴力改、暴力算 GCD 肯定是超时的必须设计一个 O(log n) 级别的数据结构方案。这个题很适合已经掌握了线段树基本操作、想进阶数据结构组合技巧的人。如果你只会写最普通的区间加法线段树看完这篇文章可以收获一个非常经典的思路迁移案例如果你是竞赛选手想复习“数学性质如何辅助数据结构”这道题的差分转化思路也值得反复咀嚼。先说结论解法是“树状数组维护原序列 线段树维护差分数组的区间 GCD”两条数据结构配合把区间加和区间 GCD 都压到 O(log n)。核心思想是区间加在差分数组视角下只影响两个点而 GCD 又有一条允许我们把原序列的区间 GCD 转化成“单点值 差分区间 GCD”的数学性质。下面按思路一步步拆开讲。2. 暴力为什么行不通以及 GCD 的数学性质2.1 一个柿子带你理解 GCD 和差分的结合假设原序列是 a[1..n]定义差分数组d[1] a[1]d[i] a[i] - a[i-1]i ≥ 2那么有一个核心等式也是整道题的灵魂gcd(a[l], a[l1], ..., a[r]) gcd(a[l], d[l1], d[l2], ..., d[r])这个等式从哪来的靠的是 GCD 的两条基本性质gcd(x, y) gcd(x, y - x)这是辗转相除法的理论根基gcd(x, y, z) gcd(x, gcd(y, z))GCD 满足结合律多个数一起算和两两算结果一致把第二条推下去gcd(a[l], a[l1], ..., a[r]) 可以看成 gcd(a[l], gcd(a[l1], a[l2], ..., a[r]))。对任意相邻两项 a[i] 和 a[i1]gcd(a[i], a[i1]) gcd(a[i], a[i1] - a[i])于是每一对相邻数的公共因子都等价于“前一个数”和“两数的差”的公共因子。顺着这个逻辑把整个区间逐对化简a[l] 留下来当基准其余每一项都变成了 d[i]这就得到了上面那个等式。2.2 为什么区间加在差分视角下“只动两个点”这需要用生活化的类比来体会。差分数组就像是一个仓库的进出货流水a[i] 是仓库当前存量d[i] 是第 i 天的净入库量存量就是所有天内净入库量之和即 a[i] ∑d[j]j 从 1 到 i。现在要给 [l, r] 这段区间内的所有存量统一加 c。对应到流水上第 l 天的入库量增加 c这样从第 l 天开始存量都会多出 c但到了第 r 天之后不能继续多于是要在第 r1 天的入库量上减掉 c把它抵消掉。所以区间加操作在差分数组上真的只改了两个下标d[l] cd[r1] - c。这就是经典差分维护区间加法的逻辑。这一个性质带来巨大好处区间修改从“一个区间”塌缩成了“两个单点”线段树只需要做两次单点修改懒标记都不需要了逻辑大幅简化。2.3 把两个性质拼起来有了前面两条解题路径就非常清晰了要查询 [l, r] 的 GCD根据等式只需要两个信息a[l] 的当前值以及 d[l1..r] 的区间 GCDa[l] 的当前值可以用数据结构维护 d 数组的前缀和得到前面说过 a[i] ∑d[1..i]d[l1..r] 的区间 GCD 可以用一棵线段树维护区间加操作就是两次单点修改d[l] cd[r1] - c分别更新前缀和数据结构与 GCD 线段树于是整个问题的复杂度变成查询时一次前缀和 O(log n) 一次区间 GCD O(log n)修改时两次单点修改每次同时更新两个结构各 O(log n)。我把这个思路给一个入门的朋友讲他第一反应是“这不就是拆东墙补西墙吗”——听起来确实有点这个味道但本质上是用数学性质把一个看似区间的问题拆成了点查询和区间查询的组合这是竞赛里非常重要的“转化思维”直接做不出来的操作换一个角度表示可能就变得非常朴素。3. 数据结构方案设计3.1 双引擎分工树状数组 线段树方案需要两个结构配合角色分工如下数据结构维护的对象提供的功能复杂度树状数组差分数组 d[1..n]单点修改、前缀和查询得到 a[l]O(log n) / 次线段树差分数组 d[1..n] 的 GCD单点修改、区间 GCD 查询O(log n) / 次为什么前缀和用树状数组而不是线段树因为树状数组写起来短、常数小而且这里只需要单点改和前缀和这两个最基础的操作树状数组是标准答案。线段树则用来维护区间 GCD这是因为 GCD 运算不支持快速的“合并可简写”只能用树结构把区间预处理成 log 层节点查询时做二分区间分解所以必须上真正的线段树。3.2 为什么不能直接给线段树打懒标记这可能是初学者最纠结的地方。线段树处理“区间加、区间和”的时候懒标记是现成的套路父节点维护区间和给整个区间加 c 后父节点值加 c × 区间长度子节点的懒标记累加即可。但“区间加、区间 GCD”根本没法这样做原因在于 GCD 对加法没有任何可交换性。举个例子就懂了两个数 [2, 6]GCD 是 2。整个区间加 2 变成 [4, 8]GCD 是 4再加 2 变成 [6, 10]GCD 是 2再加 4 变成 [10, 14]GCD 是 2。你会发现 GCD 的变化完全没有规律可循不能通过父节点的一个懒标记值推导出来。所以这个题如果硬上“带懒标记的区间加线段树”注定无解必须用差分性质把它转化成单点修改问题。这也是我第一次做这题时浪费了半天时间踩出来的经验方向错了代码写得再熟练也是白搭。3.3 必须提前想清楚的三个边界条件数据结构题很多 WA 不是算法错是边界没处理干净。这个题的边界很典型l r 时查询区间只剩一个数差分区间的查询范围 l1..r 是一个空区间空区间的 GCD 没有定义必须特判直接输出 a[l] 的绝对值区间加时如果 r 1 ≤ n才需要修改 d[r1]r 等于 n 时区间加已经加到了序列末尾不存在“之后要抵消”的下标不能越界修改差分数组 d[1] a[1]这里隐含 a[0] 0 的约定读入第一个数时不要忘记这三个边界我在做题时至少各踩了一次。l r 的特判尤其容易漏一旦漏掉线段树查询空区间返回的值会直接污染结果debug 半天都不一定能发现。4. 完整代码实现与逐段解读4.1 工具函数与结构体定义先写出 GCD 函数。这里有个容易犯的经典错误直接用 C 自带的 __gcd 处理负数时结果不可控而差分数组经过区间加操作后里面积累了很多正负号所以一定要自己写一个对负数安全的版本typedef long long LL; LL gcd(LL a, LL b) { // 先取绝对值规避负数取模的问题 if (a 0) a -a; if (b 0) b -b; while (b) { LL t a % b; a b; b t; } return a; }这个版本把所有输入先绝对值化统一转换成非负数再做辗转相除逻辑上是完整的。相比递归写法迭代版本也避免了深度递归带来的栈开销问题实测常数略优。然后定义两个结构体树状数组和线段树const int MAXN 500005; struct BIT { LL c[MAXN]; int n; void init(int n_) { n n_; memset(c, 0, sizeof(c)); } void add(int idx, LL val) { while (idx n) { c[idx] val; idx idx (-idx); } } LL sum(int idx) { LL res 0; while (idx 0) { res c[idx]; idx - idx (-idx); } return res; } } bit; struct SegTree { LL gcdVal[MAXN 2]; void pushUp(int rt) { gcdVal[rt] gcd(gcdVal[rt 1], gcdVal[rt 1 | 1]); } void build(int l, int r, int rt) { if (l r) { gcdVal[rt] ???; // 这里放差分数组 d[l]所以建树前要把 d 传进来 return; } int mid (l r) 1; build(l, mid, rt 1); build(mid 1, r, rt 1 | 1); pushUp(rt); } void update(int pos, LL val, int l, int r, int rt) { if (l r) { gcdVal[rt] val; return; } int mid (l r) 1; if (pos mid) update(pos, val, l, mid, rt 1); else update(pos, val, mid 1, r, rt 1 | 1); pushUp(rt); } LL query(int L, int R, int l, int r, int rt) { if (L l r R) return gcdVal[rt]; int mid (l r) 1; LL res 0; if (L mid) res gcd(res, query(L, R, l, mid, rt 1)); if (R mid) res gcd(res, query(L, R, mid 1, r, rt 1 | 1)); return res; } } seg;注意 query 里初始化 res 0 非常合适因为 gcd(0, x) x这个恒等式保证了“先扫左半边再扫右半边”的区间合并不会出错。也有一些写法会把 build 放到 main 里由外部数组驱动我用的是把 d 数组作为成员传入的方式。不同人风格不同关键是确保建树时每个叶子节点拿到的初始值就是差分数组 d[i]而不是原序列 a[i]。4.2 主流程区间加与区间查询主逻辑如下int n, m; LL a[MAXN], d[MAXN]; int main() { scanf(%d%d, n, m); bit.init(n); for (int i 1; i n; i) { scanf(%lld, a[i]); d[i] a[i] - a[i - 1]; // a[0] 默认 0 bit.add(i, d[i]); } seg.build(1, n, 1); // 内部用 d 数组建树注意顺序 char op[10]; int l, r; LL c; while (m--) { scanf(%s, op); if (op[0] Q) { scanf(%d%d, l, r); LL al bit.sum(l); // 差分前缀和得到 a[l] 的当前值 if (l r) { printf(%lld\n, al 0 ? -al : al); } else { LL g seg.query(l 1, r, 1, n, 1); // 查询 d[l1..r] 的 gcd printf(%lld\n, gcd(al, g)); } } else { scanf(%d%d%lld, l, r, c); bit.add(l, c); seg.update(l, c, 1, n, 1); if (r 1 n) { bit.add(r 1, -c); seg.update(r 1, -c, 1, n, 1); } } } return 0; }4.3 几种边界情形走一遍假设序列 a [6, 10, 15]差分为 d[1] 6d[2] 4d[3] 5。查询 Q(1, 3)bit.sum(1) 得到 6seg.query(2, 3) 得到 gcd(4, 5) 1最终 gcd(6, 1) 1正确。查询 Q(2, 3)bit.sum(2) 6 4 10seg.query(3, 3) 得到 5最终 gcd(10, 5) 5而 gcd(10, 15) 5正确。查询 Q(3, 3)走特判分支直接输出 bit.sum(3) 15 的绝对值 15GCD 是 15正确。执行一次区间加 C(1, 2, 3)即 [6, 10, 15] 变成 [9, 13, 15]bit.add(1, 3) 让 a[1..] 前缀和都加 3bit.add(3, -3) 让从第 3 位开始前缀和抵消这样 a[1] 9, a[2] 13, a[3] 15完美。线段树同步更新 d[1] 和 d[3]再查 Q(1, 3)a[1] 9d[2] 4d[3] 2gcd(9, 4, 2) 1而真实 gcd(9, 13, 15) 1也对上了。5. 实测性能与常见问题排障5.1 复杂度与实测表现先算算复杂度建树 O(n)每次区间加操作需要两次树状数组单点更新 O(log n) 和两次线段树单点更新 O(log n)每次查询需要一次树状数组前缀和 O(log n) 和一次线段树区间查询 O(log n)。总复杂度 O((n m) log n)n、m 各取十万级别单组测试用例在 C 下跑完全没问题我用随机数据打过 10^6 级别的操作量实际耗时也就百毫秒量级。空间方面树状数组开 n 1线段树开 4n一般 MAXN 取 5e5 5 就把数据和结构体全开下了注意位运算写法里 MAXN 2 这个左移别写成 4虽然空间会更大没错但意义不对。5.2 我踩过的坑一个一个说清楚第一个坑是负数。这是我第一次完整写完代码后过样例、过随机小数据都没问题一上大数据就随机 WA 的根源。原因在于线段树维护的 d 数组经过区间加之后有正有负而 __gcd 对负数没有约定行为。别信“C 标准里没定义”这个说法实际上不同版本的库实现结果不一样。后来我把所有 GCD 入口统一做了绝对值预处理再用自写 gcd才稳定下来。第二个坑是 l r 特判。我当时以为 query(l 1, r) 返回 gcd(空) 0然后 gcd(a[l], 0) |a[l]|所以不特判也没关系。实际写完发现 query(l1, r) 这个调用在 l 1 r 时进入线段树会穿透所有区间判断后得到 0但前提是线段树节点的初始化值是 0 且空区间查询不会访问到未定义内存。只有当树建全、所有路径都被覆盖时这个 0 才能兜底。可一旦 n 很大、递归深度不同空区间查询往往会发生越界访问或者返回一个随机叶子节点的值根本不是 0。所以千万不要依赖这个隐式行为老老实实加特判一次过省心。第三个坑是读入。字符操作混着整数读入时scanf 的 %c 会连着上一个残留的换行一起读进去导致 op 判断永远进错分支。解决办法是在 %c 前面加一个空格写成 scanf( %c, op)。如果你用的字符串读法本质相同也要注意残留的空白字符。第四个坑是大数。n、m 都是十万级别区间加 c 可能不是小整数差分数组累加之后可能超出 int 范围所以所有存储和计算都开 long long。我第一次就栽在这里区间加操作执行到一半int 溢出gcd 直接算错找了一天bug。5.3 问题速查表现象可能原因解决办法样例过随机数据WAd数组负数__gcd结果不确定自写gcd入口统一取绝对值大数据下输出错乱int溢出全部换long long查询单点区间时答案不对没特判 lr单独处理直接输出 a[l]操作读到一半程序死循环字符读入残留换行scanf( %c, op) 或读字符串区间加后发现越界修改rn 时还操作 d[r1]判断 r1 n 再执行线段树建树后叶子值奇怪build时误用了a[i]而不是d[i]核对建树阶段的数据来源6. 延伸题目稍作变化还能怎么玩6.1 如果操作变成区间赋值区间赋值和区间加不同赋值后数组这一段的值全部变成同一个数GCD 也直接变成这个数。这种题可以用带懒标记的线段树维护区间值同时维护区间GCD懒标记下推时把区间GCD也一起更新。不过如果操作里既有区间加又有区间赋值那就需要同时维护两个懒标记优先级要设计清楚——先赋值后加或者先加后赋值两种语义完全不同。一个比较常见的变体是“初始化一个全0序列支持区间加和查区间GCD”这个其实可以直接套用本文的方案全0序列的差分也全0建树时不用特殊处理逻辑上反而是最简单的。6.2 如果操作变成单点修改加区间查询这种题真的简单很多单点修改 a[i] 时差分数组同时影响 d[i] 和 d[i1]两处单点修改之后线段树和树状数组同步更新查询逻辑和本文完全一样连 l r 的特判都可以省掉。因为在单点修改前提下a[l] 是可以直接读原数组的不需要再通过前缀和还原。6.3 如果换成查询区间 LCM 怎么办LCM 和 GCD 有对偶关系lcm(a, b) a / gcd(a, b) * b。但 LCM 不满足“区间加后只影响两个点”这种好性质而且 LCM 数值增长极快需要对结果取模一取模又破坏了 LCM 的实际值这就没有 GCD 这么干净了。所以竞赛里区间 LCM 的题目很少直接上差分这种技巧多数要通过质因子分解或者值域枚举来做复杂度往往要高一截。这一点也反衬出 GCD 题目的“数学性质驱动”特点。我个人在实际做题过程中最大的体会是这道题的价值不仅在于学到“线段树点改 树状数组前缀和”这个组合更在于它教会我如何把一个看似不可做的区间操作转化成两个可以分别处理的子问题。很多数据结构难题的本质是先利用数学性质把问题的表示方法变简单再套数据结构。如果你也遇到“线段树某个操作没法合并”的题目可以先停下来想想有没有替代的表示方法比如差分、对数化、按位拆解往往换个角度解法就豁然开朗了。最后再分享一个小技巧调试这种多数据结构配合的题先别急着上大数据写一个小 n比如 n5的随机数据生成器同时写一个暴力算法两个程序对拍出错时把序列及时打印出来人眼就能定位到是前缀和还原错了还是线段树建树错了。这个习惯能帮你在竞赛里省下大量无意义的debug时间。