区间加法与GCD查询：线段树+树状数组+差分数组的巧妙解法

1. 先搞清楚题目到底在要求什么

线段树区间增加、区间 GCD 查询，这个组合我第一次遇到的时候，第一反应是“这不就是裸线段树吗”，等真正上手才发现，GCD 这个操作和加法根本不兼容。你没法在懒标记下推的时候用一个公式把父节点的区间 GCD 更新出来，这个问题的难点恰好就在这。

这道题的实际场景是：给定一个长度为 n 的序列，支持两类操作：

1. 区间 [l, r] 内的每个数统一加上一个值 c
2. 查询区间 [l, r] 内所有数的最大公约数（GCD）

n 和操作次数 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[l+1], ..., a[r]) = gcd(a[l], d[l+1], d[l+2], ..., d[r])

这个等式从哪来的？靠的是 GCD 的两条基本性质：

• gcd(x, y) = gcd(x, y - x)，这是辗转相除法的理论根基
• gcd(x, y, z) = gcd(x, gcd(y, z))，GCD 满足结合律，多个数一起算和两两算结果一致

把第二条推下去：gcd(a[l], a[l+1], ..., a[r]) 可以看成 gcd(a[l], gcd(a[l+1], a[l+2], ..., a[r]))。对任意相邻两项 a[i] 和 a[i+1]，gcd(a[i], a[i+1]) = gcd(a[i], a[i+1] - 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 天之后不能继续多，于是要在第 r+1 天的入库量上减掉 c，把它抵消掉。所以区间加操作在差分数组上真的只改了两个下标：d[l] += c，d[r+1] -= c。这就是经典差分维护区间加法的逻辑。

这一个性质带来巨大好处：区间修改从“一个区间”塌缩成了“两个单点”，线段树只需要做两次单点修改，懒标记都不需要了，逻辑大幅简化。

2.3 把两个性质拼起来

有了前面两条，解题路径就非常清晰了：

• 要查询 [l, r] 的 GCD，根据等式只需要两个信息：a[l] 的当前值，以及 d[l+1..r] 的区间 GCD
• a[l] 的当前值可以用数据结构维护 d 数组的前缀和得到，前面说过 a[i] = ∑d[1..i]
• d[l+1..r] 的区间 GCD 可以用一棵线段树维护
• 区间加操作就是两次单点修改：d[l] += c，d[r+1] -= c，分别更新前缀和数据结构与 GCD 线段树

于是整个问题的复杂度变成：查询时，一次前缀和 O(log n) + 一次区间 GCD O(log n)；修改时，两次单点修改，每次同时更新两个结构，各 O(log n)。

我把这个思路给一个入门的朋友讲，他第一反应是“这不就是拆东墙补西墙吗”——听起来确实有点这个味道，但本质上是用数学性质把一个看似区间的问题拆成了点查询和区间查询的组合，这是竞赛里非常重要的“转化思维”：直接做不出来的操作，换一个角度表示，可能就变得非常朴素。

3. 数据结构方案设计

3.1 双引擎分工：树状数组 + 线段树

方案需要两个结构配合，角色分工如下：

为什么前缀和用树状数组而不是线段树？因为树状数组写起来短、常数小，而且这里只需要单点改和前缀和这两个最基础的操作，树状数组是标准答案。线段树则用来维护区间 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 时，查询区间只剩一个数，差分区间的查询范围 l+1..r 是一个空区间，空区间的 GCD 没有定义，必须特判：直接输出 a[l] 的绝对值
• 区间加时，如果 r + 1 ≤ n，才需要修改 d[r+1]；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[l+1..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] = 6，d[2] = 4，d[3] = 5。

查询 Q(1, 3)：bit.sum(1) 得到 6，seg.query(2, 3) 得到 gcd(4, 5) = 1，最终 gcd(6, 1) = 1，正确。

查询 Q(2, 3)：bit.sum(2) = 6 + 4 = 10，seg.query(3, 3) 得到 5，最终 gcd(10, 5) = 5，而 gcd(10, 15) = 5，正确。

查询 Q(3, 3)：走特判分支直接输出 bit.sum(3) = 15 的绝对值 15，GCD 是 15，正确。

执行一次区间加 C(1, 2, 3)，即 [6, 10, 15] 变成 [9, 13, 15]：bit.add(1, 3) 让 a[1..] 前缀和都加 3；bit.add(3, -3) 让从第 3 位开始前缀和抵消，这样 a[1] = 9, a[2] = 13, a[3] = 15，完美。线段树同步更新 d[1] 和 d[3]，再查 Q(1, 3)：a[1] = 9，d[2] = 4，d[3] = 2，gcd(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(l+1, 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 问题速查表

6. 延伸：题目稍作变化还能怎么玩

6.1 如果操作变成区间赋值

区间赋值和区间加不同，赋值后数组这一段的值全部变成同一个数，GCD 也直接变成这个数。这种题可以用带懒标记的线段树维护区间值，同时维护区间GCD，懒标记下推时把区间GCD也一起更新。不过如果操作里既有区间加又有区间赋值，那就需要同时维护两个懒标记，优先级要设计清楚——先赋值后加，或者先加后赋值，两种语义完全不同。

一个比较常见的变体是“初始化一个全0序列，支持区间加和查区间GCD”，这个其实可以直接套用本文的方案，全0序列的差分也全0，建树时不用特殊处理，逻辑上反而是最简单的。

6.2 如果操作变成单点修改加区间查询

这种题真的简单很多：单点修改 a[i] 时，差分数组同时影响 d[i] 和 d[i+1]，两处单点修改之后，线段树和树状数组同步更新，查询逻辑和本文完全一样，连 l == r 的特判都可以省掉。因为在单点修改前提下，a[l] 是可以直接读原数组的，不需要再通过前缀和还原。

6.3 如果换成查询区间 LCM 怎么办

LCM 和 GCD 有对偶关系：lcm(a, b) = a / gcd(a, b) * b。但 LCM 不满足“区间加后只影响两个点”这种好性质，而且 LCM 数值增长极快，需要对结果取模，一取模又破坏了 LCM 的实际值，这就没有 GCD 这么干净了。所以竞赛里区间 LCM 的题目很少直接上差分这种技巧，多数要通过质因子分解或者值域枚举来做，复杂度往往要高一截。这一点也反衬出 GCD 题目的“数学性质驱动”特点。

我个人在实际做题过程中最大的体会是：这道题的价值不仅在于学到“线段树点改 + 树状数组前缀和”这个组合，更在于它教会我如何把一个看似不可做的区间操作转化成两个可以分别处理的子问题。很多数据结构难题的本质，是先利用数学性质把问题的表示方法变简单，再套数据结构。如果你也遇到“线段树某个操作没法合并”的题目，可以先停下来想想有没有替代的表示方法，比如差分、对数化、按位拆解，往往换个角度，解法就豁然开朗了。

最后再分享一个小技巧：调试这种多数据结构配合的题，先别急着上大数据，写一个小 n（比如 n=5）的随机数据生成器，同时写一个暴力算法，两个程序对拍，出错时把序列及时打印出来，人眼就能定位到是前缀和还原错了还是线段树建树错了。这个习惯能帮你在竞赛里省下大量无意义的debug时间。