本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：245. 你能回答这些问题吗 - AcWing题库
【题目描述】
给定长度为N NN的数列A AA，以及M MM条指令，每条指令可能是以下两种之一：
1 x y，查询区间[ x , y ] [x,y][x,y]中的最大连续子段和，即max x ≤ l ≤ r ≤ y { ∑ i = l r A [ i ] } \max\limits_{x\le l\le r\le y}\{\sum\limits_{i=l}^{r}A[i]\}x≤l≤r≤ymax{i=l∑rA[i]}。2 x y，把A [ x ] A[x]A[x]改成y yy。
对于每个查询指令，输出一个整数表示答案。
【输入】
第一行两个整数N , M N,MN,M。
第二行N NN个整数A [ i ] A[i]A[i]。
接下来M MM行每行3 33个整数k , x , y k,x,yk,x,y，k = 1 k=1k=1表示查询（此时如果x > y x>yx>y，请交换x , y x,yx,y），k = 2 k=2k=2表示修改。
【输出】
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
【输入样例】
5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 3 2【输出样例】
2 -1【核心思想】
问题分析：给定长度为N NN的数列A AA和M MM条指令，指令分为两类：查询区间[ x , y ] [x,y][x,y]中的最大连续子段和，或将A [ x ] A[x]A[x]修改为y yy。这是一个线段树维护最大子段和问题，关键在于设计能支持区间合并的节点信息。
算法选择：
- 线段树（Segment Tree）：支持O ( log N ) O(\log N)O(logN)时间复杂度的单点修改和区间查询
- 节点信息设计：每个节点维护四个值——区间总和s u m sumsum、最大前缀和p r e prepre、最大后缀和s u f sufsuf、最大连续子段和b e s t bestbest
关键步骤：
- 建树（O ( N ) O(N)O(N)）：递归建立线段树，叶子节点初始化s u m = p r e = s u f = b e s t = A [ i ] sum = pre = suf = best = A[i]sum=pre=suf=best=A[i]
- 向上合并 pushup（O ( 1 ) O(1)O(1)）：
- s u m = l . s u m + r . s u m sum = l.sum + r.sumsum=l.sum+r.sum
- p r e = max ( l . p r e , l . s u m + r . p r e ) pre = \max(l.pre,\ l.sum + r.pre)pre=max(l.pre,l.sum+r.pre)
- s u f = max ( r . s u f , r . s u m + l . s u f ) suf = \max(r.suf,\ r.sum + l.suf)suf=max(r.suf,r.sum+l.suf)
- b e s t = max ( l . b e s t , r . b e s t , l . s u f + r . p r e ) best = \max(l.best,\ r.best,\ l.suf + r.pre)best=max(l.best,r.best,l.suf+r.pre)
- 单点修改 update（O ( log N ) O(\log N)O(logN)）：定位到叶子节点修改值，然后自底向上 pushup 更新
- 区间查询 query（O ( log N ) O(\log N)O(logN)）：若查询区间横跨左右子树，需合并左右结果并返回完整 Node 信息
时间/空间复杂度：
- 时间复杂度：建树O ( N ) O(N)O(N)，单次修改O ( log N ) O(\log N)O(logN)，单次查询O ( log N ) O(\log N)O(logN)，总复杂度O ( N + M log N ) O(N + M \log N)O(N+MlogN)
- 空间复杂度：O ( N ) O(N)O(N)，线段树开4 N 4N4N空间
线段树维护最大子段和的核心思想：
- 节点信息设计：最大子段和无法直接由左右子树的最大子段和推导，必须额外维护最大前缀和与最大后缀和，才能处理跨过中点的情况
- 跨区间合并：区间[ l , r ] [l,r][l,r]的最大子段和有三种来源——完全在左子树、完全在右子树、跨过中点（左后缀和 + 右前缀和）
- 查询返回结构体：与普通线段树查询返回数值不同，本题查询需要返回完整的 Node 结构，以支持上层合并
- 适用于带修改的最大子段和、最大子矩阵和等动态区间问题
【算法标签】
#线段树
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将 int 定义为 long long，防止数值溢出constintN=500005;// 最大数组长度intn,m,v[N],sa[N];// n: 数组长度, m: 指令数, v: 原数组, sa: 前缀和数组（未使用）// 线段树节点结构structNode{intl,r;// 区间左右端点intsum;// 区间总和intpre;// 最大前缀和（从左端点开始的最大连续子段和）intsuf;// 最大后缀和（以右端点结束的最大连续子段和）intbest;// 区间内的最大连续子段和}tr[N*4];// 线段树数组（4倍空间）// 向上更新：根据左右子节点信息更新父节点voidpushup(intu){auto&root=tr[u],&l=tr[u<<1],&r=tr[u<<1|1];root.sum=l.sum+r.sum;// 区间总和 = 左子树和 + 右子树和root.pre=max(l.pre,l.sum+r.pre);// 最大前缀和：要么在左子树，要么跨过中点root.suf=max(r.suf,r.sum+l.suf);// 最大后缀和：要么在右子树，要么跨过中点root.best=max({l.best,r.best,l.suf+r.pre});// 最大子段和：左子树、右子树、或跨过中点}// 建立线段树voidbuild(intu,intl,intr){if(l==r)// 叶子节点tr[u]={l,r,v[l],v[l],v[l],v[l]};// 初始化：sum=pre=suf=best=v[l]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);// 向上更新当前节点}}// 单点修改：将位置 pos 的值改为 dvoidupdate(intu,intpos,intd){if(tr[u].l==tr[u].r)// 叶子节点{tr[u]={pos,pos,d,d,d,d};// 直接替换为新的值return;}intmid=tr[u].l+tr[u].r>>1;// 取中点if(pos<=mid)update(u<<1,pos,d);// 在左子树elseupdate(u<<1|1,pos,d);// 在右子树pushup(u);// 修改后向上更新}// 区间查询：返回区间 [l, r] 的 Node 信息Nodequery(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r)// 当前节点区间完全包含在查询区间内returntr[u];intmid=tr[u].l+tr[u].r>>1;// 取中点if(r<=mid)returnquery(u<<1,l,r);// 查询区间完全在左子树if(l>mid)returnquery(u<<1|1,l,r);// 查询区间完全在右子树// 查询区间横跨左右子树，需要合并左右结果Node left=query(u<<1,l,r);// 查询左子树Node right=query(u<<1|1,l,r);// 查询右子树Node res;res.sum=left.sum+right.sum;res.pre=max(left.pre,left.sum+right.pre);res.suf=max(right.suf,right.sum+left.suf);res.best=max({left.best,right.best,left.suf+right.pre});returnres;}signedmain()// 使用 signed 替代 int，因为 #define int long long{cin>>n>>m;// 读入数组长度和指令数for(inti=1;i<=n;i++){cin>>v[i];// 读入原数组}build(1,1,n);// 建立线段树，根节点为1，覆盖区间[1,n]while(m--)// 依次处理每条指令{intk,x,y;cin>>k>>x>>y;// 读入指令类型和参数if(k==1)// 查询指令{if(x>y)swap(x,y);// 保证 x <= yNode res=query(1,x,y);// 查询区间最大子段和cout<<res.best<<endl;// 输出最大子段和}else// 修改指令update(1,x,y);// 将 A[x] 修改为 y}return0;}【运行结果】
5 3 1 2 -3 4 5 1 2 3 2 2 2 -1 1 3 2 -1
