本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：246. 区间最大公约数 - AcWing题库

【题目描述】

给定一个长度为N NN的数列A AA，以及M MM条指令，每条指令可能是以下两种之一：

1. C l r d，表示把A [ l ] , A [ l + 1 ] , … , A [ r ] A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r]都加上d dd。
2. Q l r，表示询问A [ l ] , A [ l + 1 ] , … , A [ r ] A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r]的最大公约数（G C D GCDGCD)。

对于每个询问，输出一个整数表示答案。

【输入】

第一行两个整数N , M N,MN,M。

第二行N NN个整数A [ i ] A[i]A[i]。

接下来M MM行表示M MM条指令，每条指令的格式如题目描述所示。

【输出】

对于每个询问，输出一个整数表示答案。

每个答案占一行。

【输入样例】

5 5 1 3 5 7 9 Q 1 5 C 1 5 1 Q 1 5 C 3 3 6 Q 2 4

【输出样例】

1 2 4

【核心思想】

1. 问题分析：给定长度为N NN的数列A AA，以及M MM条指令，支持区间[ l , r ] [l, r][l,r]加d dd和查询区间[ l , r ] [l, r][l,r]的最大公约数。关键在于如何在区间修改的同时高效维护区间 GCD。

2. 算法选择：

   • 差分数组（Difference Array）：将区间加法转化为差分数组的单点修改，实现O ( 1 ) O(1)O(1)区间标记
   • 线段树（Segment Tree）：维护差分数组的区间 GCD，支持单点修改和区间 GCD 查询
   • 树状数组（Fenwick Tree）：维护差分数组的前缀和，用于快速查询A [ l ] A[l]A[l]的值
   • 数学性质：利用gcd ⁡ ( a 1 , a 2 , . . . , a n ) = gcd ⁡ ( a 1 , a 2 − a 1 , a 3 − a 2 , . . . , a n − a n − 1 ) \gcd(a_1, a_2, ..., a_n) = \gcd(a_1, a_2-a_1, a_3-a_2, ..., a_n-a_{n-1})gcd(a1​,a2​,...,an​)=gcd(a1​,a2​−a1​,a3​−a2​,...,an​−an−1​)的性质，将区间 GCD 转化为差分数组的 GCD

3. 关键步骤：

   • 初始化：读取N NN（数组长度）、M MM（指令数）、A [ 1.. N ] A[1..N]A[1..N]（初始数组）
   • 构建差分数组：b [ i ] = A [ i ] − A [ i − 1 ] b[i] = A[i] - A[i-1]b[i]=A[i]−A[i−1]，其中b [ 1 ] = A [ 1 ] b[1] = A[1]b[1]=A[1]
   • 树状数组初始化：将差分数组b [ i ] b[i]b[i]加入树状数组，支持前缀和查询得到A [ i ] A[i]A[i]
   • 线段树建立：维护差分数组b bb的区间 GCD
   • 处理查询指令Q l r：
     • 通过树状数组前缀和查询A [ l ] = ∑ i = 1 l b [ i ] A[l] = \sum_{i=1}^{l} b[i]A[l]=∑i=1l​b[i]
     • 通过线段树查询gcd ⁡ ( b [ l + 1 ] , b [ l + 2 ] , . . . , b [ r ] ) \gcd(b[l+1], b[l+2], ..., b[r])gcd(b[l+1],b[l+2],...,b[r])
     • 答案为gcd ⁡ ( A [ l ] , gcd ⁡ ( b [ l + 1.. r ] ) ) \gcd(A[l], \gcd(b[l+1..r]))gcd(A[l],gcd(b[l+1..r]))，即gcd ⁡ ( A [ l . . r ] ) \gcd(A[l..r])gcd(A[l..r])
     • 若l = r l = rl=r，直接输出∣ A [ l ] ∣ |A[l]|∣A[l]∣
   • 处理修改指令C l r d：
     • 树状数组单点修改：add(l, d)和add(r+1, -d)
     • 线段树单点更新：update(l, d)和update(r+1, -d)（若r + 1 ≤ n r+1 \leq nr+1≤n）

4. 时间/空间复杂度：

   • 时间复杂度：O ( ( N + M ) log ⁡ N ) O((N + M) \log N)O((N+M)logN)，线段树和树状数组操作均为O ( log ⁡ N ) O(\log N)O(logN)
   • 空间复杂度：O ( N ) O(N)O(N)，线段树（4 N 4N4N）+ 树状数组（N NN）+ 原数组

5. 线段树维护 GCD 的核心思想：

   • 差分降维：利用gcd ⁡ ( A [ l . . r ] ) = gcd ⁡ ( A [ l ] , gcd ⁡ ( b [ l + 1.. r ] ) ) \gcd(A[l..r]) = \gcd(A[l], \gcd(b[l+1..r]))gcd(A[l..r])=gcd(A[l],gcd(b[l+1..r]))的数学性质，将区间修改下的区间 GCD 查询转化为差分数组的区间 GCD 查询
   • 区间修改转单点修改：对原数组区间[ l , r ] [l, r][l,r]加d dd，等价于对差分数组b [ l ] + = d b[l] += db[l]+=d、b [ r + 1 ] − = d b[r+1] -= db[r+1]−=d，仅影响两个端点
   • 线段树维护 GCD：父节点的 GCD 等于左右子节点 GCD 的 GCD，即gcd ⁡ ( l . v , r . v ) \gcd(l.v, r.v)gcd(l.v,r.v)
   • 树状数组维护前缀和：通过前缀和还原原数组的值A [ l ] A[l]A[l]，用于与差分 GCD 合并得到最终答案
   • 适用于区间加减与区间 GCD 查询类问题

【算法标签】

#线段树

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将 int 定义为 long long，防止数值溢出constintN=500005;// 最大数组长度intn,m;// n: 数组长度, m: 指令数intw[N];// 原数组inttr1[N];// 树状数组（维护差分数组的前缀和）structNode{intl,r,v;// 区间左右端点、区间差分数组的GCD值}tr[N*4];// 线段树数组（4倍空间）// 树状数组：lowbit运算，提取x的最低位1对应的2次幂数intlowbit(intx){returnx&-x;}// 树状数组：单点修改（向后修），在位置x加上cvoidadd(intx,intc){for(inti=x;i<=n;i+=lowbit(i))tr1[i]+=c;}// 树状数组：前缀查询（向前查），查询[1,x]的和intsum(intx){intres=0;for(inti=x;i;i-=lowbit(i))res+=tr1[i];returnres;}// 辗转相除法求GCDintgcd(inta,intb){returnb?gcd(b,a%b):a;}// 线段树：向上更新，父节点的v = 左右子节点v的GCDvoidpushup(intu){auto&root=tr[u],&l=tr[u<<1],&r=tr[u<<1|1];tr[u].v=gcd(l.v,r.v);}// 线段树：建立，维护差分数组b[i] = w[i] - w[i-1]的GCDvoidbuild(intu,intl,intr){if(l==r)// 叶子节点tr[u]={l,r,w[r]-w[r-1]};// 差分数组的值else{tr[u]={l,r};// 初始化当前节点的区间范围intmid=l+r>>1;// 取中点（等价于 (l+r)/2）build(u<<1,l,mid),build(u<<1|1,mid+1,r);// 递归建立左右子树pushup(u);// 向上更新当前节点}}// 线段树：区间查询GCDintquery(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r)// 当前节点区间完全包含在查询区间内returntr[u].v;intmid=tr[u].l+tr[u].r>>1;// 取中点intv=0;if(l<=mid)v=query(u<<1,l,r);// 左子树有贡献if(r>mid)v=gcd(v,query(u<<1|1,l,r));// 右子树有贡献，与左子树结果取GCDreturnv;}// 线段树：单点修改，在差分数组位置pos加上dvoidupdate(intu,intpos,intd){if(tr[u].l==tr[u].r)// 叶子节点{tr[u].v+=d;// 差分数组的值增加dreturn;}intmid=tr[u].l+tr[u].r>>1;// 取中点if(pos<=mid)update(u<<1,pos,d);// 在左子树elseupdate(u<<1|1,pos,d);// 在右子树pushup(u);// 修改后向上更新}signedmain()// 使用 signed 替代 int，因为 #define int long long{cin>>n>>m;// 读入数组长度和指令数for(inti=1;i<=n;i++)cin>>w[i];// 读入原数组// 初始化树状数组：将差分数组 b[i] = w[i] - w[i-1] 加入树状数组for(inti=1;i<=n;i++)add(i,w[i]-w[i-1]);build(1,1,n);// 建立线段树，维护差分数组，区间为[1, n]charop;intl,r,d;while(m--)// 依次处理每条指令{cin>>op;if(op=='Q')// 查询指令{cin>>l>>r;intleft=sum(l);// 树状数组查询A[l]的值（差分数组前缀和）intright=query(1,l+1,r);// 线段树查询差分数组[l+1, r]的GCDif(l==r)// 区间长度为1cout<<abs(left)<<endl;// 直接输出A[l]的绝对值else// GCD(A[l..r]) = GCD(A[l], GCD(b[l+1], b[l+2], ..., b[r]))// 其中 b[i] = A[i] - A[i-1] 为差分数组cout<<abs(gcd(left,right))<<endl;}else// 修改指令{cin>>l>>r>>d;// 树状数组：区间加d，转化为差分数组的两个单点修改add(l,d);add(r+1,-d);// 线段树：同步更新差分数组的两个端点update(1,l,d);if(r+1<=n)// 注意线段树建到了nupdate(1,r+1,-d);}}return0;}

【运行结果】

5 5 1 3 5 7 9 Q 1 5 1 C 1 5 1 Q 1 5 2 C 3 3 6 Q 2 4 4