题解：AcWing 245 你能回答这些问题吗

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing245. 你能回答这些问题吗 - 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_{il}^{r}A[i]\}x≤l≤r≤ymax​{il∑r​A[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,yk 1 k1k1表示查询此时如果x y xyxy请交换x , y x,yx,yk 2 k2k2表示修改。【输出】对于每个查询指令输出一个整数表示答案。每个答案占一行。【输入样例】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]sumpresufbestA[i]向上合并 pushupO ( 1 ) O(1)O(1)s u m l . s u m r . s u m sum l.sum r.sumsuml.sumr.sump r e max ⁡ ( l . p r e , l . s u m r . p r e ) pre \max(l.pre,\ l.sum r.pre)premax(l.pre,l.sumr.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)sufmax(r.suf,r.suml.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)bestmax(l.best,r.best,l.sufr.pre)单点修改 updateO ( log ⁡ N ) O(\log N)O(logN)定位到叶子节点修改值然后自底向上 pushup 更新区间查询 queryO ( 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(NMlogN)空间复杂度O ( N ) O(N)O(N)线段树开4 N 4N4N空间线段树维护最大子段和的核心思想节点信息设计最大子段和无法直接由左右子树的最大子段和推导必须额外维护最大前缀和与最大后缀和才能处理跨过中点的情况跨区间合并区间[ l , r ] [l,r][l,r]的最大子段和有三种来源——完全在左子树、完全在右子树、跨过中点左后缀和 右前缀和查询返回结构体与普通线段树查询返回数值不同本题查询需要返回完整的 Node 结构以支持上层合并适用于带修改的最大子段和、最大子矩阵和等动态区间问题【算法标签】#线段树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将 int 定义为 long long防止数值溢出constintN500005;// 最大数组长度intn,m,v[N],sa[N];// n: 数组长度, m: 指令数, v: 原数组, sa: 前缀和数组未使用// 线段树节点结构structNode{intl,r;// 区间左右端点intsum;// 区间总和intpre;// 最大前缀和从左端点开始的最大连续子段和intsuf;// 最大后缀和以右端点结束的最大连续子段和intbest;// 区间内的最大连续子段和}tr[N*4];// 线段树数组4倍空间// 向上更新根据左右子节点信息更新父节点voidpushup(intu){autoroottr[u],ltr[u1],rtr[u1|1];root.suml.sumr.sum;// 区间总和 左子树和 右子树和root.premax(l.pre,l.sumr.pre);// 最大前缀和要么在左子树要么跨过中点root.sufmax(r.suf,r.suml.suf);// 最大后缀和要么在右子树要么跨过中点root.bestmax({l.best,r.best,l.sufr.pre});// 最大子段和左子树、右子树、或跨过中点}// 建立线段树voidbuild(intu,intl,intr){if(lr)// 叶子节点tr[u]{l,r,v[l],v[l],v[l],v[l]};// 初始化sumpresufbestv[l]else{tr[u]{l,r};// 初始化当前节点的区间范围intmidlr1;// 取中点等价于 (lr)/2build(u1,l,mid),build(u1|1,mid1,r);// 递归建立左右子树pushup(u);// 向上更新当前节点}}// 单点修改将位置 pos 的值改为 dvoidupdate(intu,intpos,intd){if(tr[u].ltr[u].r)// 叶子节点{tr[u]{pos,pos,d,d,d,d};// 直接替换为新的值return;}intmidtr[u].ltr[u].r1;// 取中点if(posmid)update(u1,pos,d);// 在左子树elseupdate(u1|1,pos,d);// 在右子树pushup(u);// 修改后向上更新}// 区间查询返回区间 [l, r] 的 Node 信息Nodequery(intu,intl,intr){if(tr[u].lltr[u].rr)// 当前节点区间完全包含在查询区间内returntr[u];intmidtr[u].ltr[u].r1;// 取中点if(rmid)returnquery(u1,l,r);// 查询区间完全在左子树if(lmid)returnquery(u1|1,l,r);// 查询区间完全在右子树// 查询区间横跨左右子树需要合并左右结果Node leftquery(u1,l,r);// 查询左子树Node rightquery(u1|1,l,r);// 查询右子树Node res;res.sumleft.sumright.sum;res.premax(left.pre,left.sumright.pre);res.sufmax(right.suf,right.sumleft.suf);res.bestmax({left.best,right.best,left.sufright.pre});returnres;}signedmain()// 使用 signed 替代 int因为 #define int long long{cinnm;// 读入数组长度和指令数for(inti1;in;i){cinv[i];// 读入原数组}build(1,1,n);// 建立线段树根节点为1覆盖区间[1,n]while(m--)// 依次处理每条指令{intk,x,y;cinkxy;// 读入指令类型和参数if(k1)// 查询指令{if(xy)swap(x,y);// 保证 x yNode resquery(1,x,y);// 查询区间最大子段和coutres.bestendl;// 输出最大子段和}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