★ FEATURED ARTICLE 排序、二分、高精度、前缀和差分、双指针、位运算、离散化、区间合并坦白说我当年第一次把《算法基础课》第一章的目录翻完时第一反应是“就这”八个看上去跟“基础”两个字毫无关系的名词每一章单独拎出来都是能让新手劝退的存在。但等我认真刷完、把每道模板题亲手敲到能默写的程度后才明白为什么它叫“算法基础”——这八块内容不是知识的并列而是一整套后续所有算法的底层骨架。你后面学的图论、树状数组、线段树、动态规划几乎没有哪个能绕开这里面的某一块。这篇就把我梳理过的第一章完整拆一遍把每个算法模板背后的设计逻辑、边界处理和实战中容易踩的坑一起讲透。1. 章节整体思路为什么算法基础要学会“背模板”1.1 第一章到底在解决什么问题任何一个程序员刷题或者做项目遇到性能瓶颈本质上跑不掉的都是那几类计算排序、查找、区间聚合、数值运算。第一章把这几类问题里最高频、最底层的解法单独拎了出来目的不是让你会背代码而是让你在遇到新题时能快速对照场景选对方案。比如看到“求区间和”“区间加同一个数”能条件反射想到前缀和与差分看到“求所有逆序对”能想到归并排序的合并过程这种本能不是靠看出来的是靠反复过模板练出来的。同时这些模板本身也是后续章节的工具。像离散化和区间合并你学扫描线、学线段树维护坐标时一定会再次撞见二分更是贯穿整个算法体系从整数二分到实数二分再到二分答案思维一脉相承。第一章学得扎实后面的各种高级数据结构才不至于摸不着头脑。1.2 模板化的意义与适用边界很多人一提“背模板”就嗤之以鼻觉得算法学习应该靠理解。我的看法是初期必须有适度的模板化。你可以不理解为什么快排最坏情况退化到O(n²)但你必须先能稳定写出一个不越界、不死循环的快排你可以暂时没吃透二分的数学本质但必须能把两个整数二分模板背得滚瓜烂熟。为什么因为比赛和面试现场没时间让你从头推边界。模板就是保底方案是那个“哪怕我不理解也保证不写错”的防线。等熟练之后再去深挖原理把模板消化成自己的思路这时候才算真正掌握了。当然模板不是银弹。你不能见到任何区间查询都无脑前缀和见到任何最小值问题都套二分。后面我会反复强调“适用场景”这才是模板能不能用得对的关键。2. 排序算法快排与归并的边界处理是分水岭2.1 快速排序模板的细节快速排序可能是很多人接触的第一个“会写但写不对”的算法。最经典的写法是选一个分界点然后左右递归排序整体结构很简洁但边界问题极其容易翻车。给一份标准模板void quick_sort(int q[], int l, int r) { if (l r) return; int i l - 1, j r 1, x q[(l r) 1]; while (i j) { do i; while (q[i] x); do j--; while (q[j] x); if (i j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j 1, r); }三个关键细节值得展开说说。第一分界点取q[(l r) 1]而不是q[l]。如果取左端点当数组已经有序时每次划分都极端不平衡递归深度会退化到O(n)数据规模一大直接栈溢出。取中间值是一种工程默认的防退化策略虽然不能完全消除最坏情况但能在绝大多数输入下保持稳定。第二循环用的是do...while不是常规的while (q[i] x) i。这里有个隐蔽的坑如果q[i] x后一种写法里i会停住不动循环卡死。do...while保证指针至少移动一格从根本上避免死循环。我第一次教学弟时他照着别的资料写数据里一出现重复值就超时原因正在这里。第三递归区间是[l, j]和[j 1, r]不是[l, i-1]和[i, r]。如果你改成以i为划分点配合不同的分界点取值边界组合就可能出差错。最简单的避免方法就是固定记住这一个搭配基准取中间值递归用j划分。想用i划分也可以但x要取q[(l r 1) 1]代码就得写成递归[l, i-1]和[i, r]。每一套搭配都自洽但你不能混乱着混用。2.2 归并排序与逆序对统计归并排序的思路比快排直观先递归拆到单个元素再两两合并有序数组。模板同样标准void merge_sort(int q[], int l, int r) { if (l r) return; int mid l r 1; merge_sort(q, l, mid); merge_sort(q, mid 1, r); int k 0, i l, j mid 1; while (i mid j r) { if (q[i] q[j]) tmp[k] q[i]; else tmp[k] q[j]; } while (i mid) tmp[k] q[i]; while (j r) tmp[k] q[j]; for (i l, k 0; i r; i, k) q[i] tmp[k]; }归并排序的合并过程隐藏了一个高频考点逆序对计数。如果q[i] q[j]说明左半边从i到mid的所有元素都比q[j]大可以一次性加上mid - i 1个逆序对。很多人在主函数里加一行count mid - i 1就去交题结果发现数据大时数量超过int范围——逆序对数量最坏是n*(n-1)/2十万数据量就已经到亿级别了必须开long long。这个细节我在章节的常见问题里还会再强调。2.3 排序相关的常见坑快排和归并的坑主要集中在这些地方递归爆栈数据有序时快排易退化处理方法是取中间元素做基准或改用随机基准。递归结束条件写错l r而不是l r否则空区间会再次递归导致死循环。合并时临时数组的复制范围经常有人忘记把tmp复制回原数组或者for循环里下标写混。数据范围判断int不够时要毫不犹豫用long long。3. 二分算法边界问题的本质3.1 整数二分的两个模板二分的难点不在“二分”本身而在边界更新。整数二分有两个高度对称的模板分别用于查找区间的左端点和右端点。模板一int l 0, r n - 1; while (l r) { int mid l r 1; if (check(mid)) r mid; else l mid 1; }模板二int l 0, r n - 1; while (l r) { int mid l r 1 1; if (check(mid)) l mid; else r mid - 1; }两个模板最核心的区别在于mid的计算模板二必须1。原理不复杂当l r - 1时模板二的mid如果不加1会等于l。如果此时check(mid)为真l mid等于没更新死循环就产生了。加1之后mid r就算不满足条件也能正常收缩。这属于典型的“差一点就崩盘”的边界问题必须靠着模板固定记忆临场很容易漏。3.2 浮点数二分浮点数二分比整数二分简单得多因为不需要处理1的边界。典型场景是求平方根或解方程模板如下double l 0, r 100000; while (r - l 1e-7) { double mid (l r) / 2; if (mid * mid x) r mid; else l mid; }这里的精度1e-7是经验值。如果题目要求输出小数点后6位循环条件设到1e-7起要求更高就再缩一位。另一种方式是直接循环100次相当于二分从不知道多少位精度的区间一直压下去最终精度一定够。浮点数二分整体上没有死循环问题初学者可以优先从这里建立信心。3.3 二分常见问题排查二分题写不对90%是边界更新错。我的排查顺序是先确认题意是找左边界还是右边界两个模板别混用。再看mid有没有加1这决定了最终会不会死循环。最后用只有两个元素的数组手动模拟一遍能覆盖掉绝大多数边界bug。另外不要把二分理解成只能在有序数组上用。二分的本质是“把一个区间分成性质相反的两段找到分界点”单调性只是充分条件而不是必要条件。只要你定义的check函数满足“左边全为false右边全为true”或反过来就能二分。4. 前缀和与差分区间操作的基石4.1 一维前缀和如何推导前缀和解决的问题是“频繁查询区间和”。每次暴力遍历区间复杂度是O(n)查询 m 次就是O(nm)前缀和通过一次预处理把单次查询降到O(1)。公式很朴素s[i] s[i - 1] a[i];查询[l, r]区间和时ans s[r] - s[l - 1];这里有一个值得注意的约定数组下标从1开始s[0]置0。为什么要这样因为如果从0开始查询[0, r]时s[-1]直接越界必须特判。从1开始书写最干净这也是模板类代码默认下标从1起的根本原因。4.2 二维前缀和的容斥思想二维前缀和是考试和刷题中更常出现的变种核心是容斥原理s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j];查询左上角(x1, y1)右下角(x2, y2)的子矩阵和sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1];理解容斥最快的方法是画一个2x2的四宫格把重叠区域标出来数两遍减一遍。很多初学者死记公式写错符号然后对着样例反复调。我建议直接在纸上推一遍先加整个大矩形再减掉左上角区域和右上角区域会发现上角区域被减了两次所以再加回来一次。符号永远不可能记错。4.3 差分数组的应用差分是前缀和的逆运算b[i] a[i] - a[i-1];对原始数组区间[l, r]整体加上c只需要b[l] c; b[r 1] - c; // 然后对 b 做前缀和还原为什么这么巧因为对差分数组求前缀和得到的就是原数组。区间加操作反映到差分数组上只在两个端点发生变化。这个思想在后面的差分矩阵、树上差分、扫描线里都会反复出现是“用端点操作替代区间操作”的典型。实战中差分容易踩的坑有两个一是忘记在下标r 1处减回去导致后续所有元素都被多加二是在数据量大的时候int溢出区间加 c 可能让每个元素累加超过int上限干脆定义成long long数组求和。5. 其他经典基础高精度、双指针、位运算、离散化与区间合并5.1 高精度逆序存储与进位处理高精度解决的是“数字位数超过语言内置类型上限”的计算问题。核心思想是用数组模拟竖式运算。标准存储方案是逆序存放即个位放在数组下标0的位置。为什么逆序因为运算时会产生进位逆序存储可以让进位自然地向数组末尾扩展不需要反复整体搬迁数据。高精度加法模板vectorint add(vectorint A, vectorint B) { vectorint C; int t 0; for (int i 0; i A.size() || i B.size(); i) { if (i A.size()) t A[i]; if (i B.size()) t B[i]; C.push_back(t % 10); t / 10; } if (t) C.push_back(t); return C; }高精度乘法和减法还要额外处理前导零。乘法的前导零出现你乘的数是0的时候减法则是在C.size() 1时不断pop_back去掉高位多余的0。这个去零步骤非常容易漏我当时就在一个高精度减法模板块卡了半小时最后发现答案输出的是000123这种带零的字符串。5.2 双指针算法单调性带来的复杂度优化双指针的精髓一句话解释利用指针的“单调移动”把双重循环降到O(n)。最经典的应用是“最长连续不重复子序列”for (int i 0, j 0; i n; i) { count[a[i]]; while (count[a[i]] 1) { count[a[j]]--; j; } ans max(ans, i - j 1); }这里的i和j都只会向右跑所以总复杂度O(n)。很多人写双指针时会在内层循环里反复重置j但双指针的前提就是j不会回退。想明白这个单调性才能写出干净的代码。双指针的另一类应用是与排序结合。比如两个有序数组找和等于某个值的数对一左一右往中间靠本质也是利用单调性。5.3 位运算lowbit与二进制中1的个数位运算这一节在第一章里相对轻量核心是lowbit操作int lowbit(int x) { return x -x; }lowbit返回的是x二进制表示中最低位的1及其后面所有0组成的数。比如lowbit(12)中12是1100结果是100即4。这个操作最常见的应用是统计二进制中1的个数while (x) { x - lowbit(x); count; }每次减去一个lowbit相当于消掉一个1。也可以用x (x - 1)达到同样效果。这两个位运算技巧写起来很简洁也容易记混。实际用手算一遍就清楚x - 1会把最低位的1变成0把后面所有0变成1再和x做与运算正好把最低位的1抹掉。5.4 离散化保序映射的通用做法离散化处理的问题是“值域很大但数据量小”。比如有1e9范围内的若干点坐标要在上面做区间操作直接开数组是不现实的。离散化的做法是把所有出现过的坐标收集起来排序去重然后用二分找到每个坐标对应的压缩下标。模板如下vectorint alls; // 收集所有需要离散化的值 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 二分映射 int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; }这里1是为了让映射后的下标从1开始方便配合前缀和。unique会返回去重后新的末尾位置erase把重复部分删干净。注意unique只对排序后的数组有效所以顺序不能颠倒。离散化的关键在于“保序”也就是压缩后的相对大小关系和原来一致这样二分和前缀和才能在压缩坐标系里正常工作。我当时犯过的错是只用哈希表做映射结果丢了顺序后面的区间操作全乱套。在需要“保序”的场景中必须先排序再去重。5.5 区间合并排序后一次性合并区间合并是第一章里最“工程化”的算法情景是给你一堆左闭右开或闭区间要求合并所有重叠区间。核心做法按左端点排序。遍历区间维护当前合并区间[L, R]。如果新区间左端点a[i].l R则重叠更新R max(R, a[i].r)。否则把当前区间输出重置为新区间。模板sort(a.begin(), a.end()); int ans 0, L -2e9, R -2e9; for (auto p : a) { if (p.first R) { if (L ! -2e9) ans; L p.first, R p.second; } else { R max(R, p.second); } } if (L ! -2e9) ans;这里条件用的是p.first R判定不重叠而不是p.first R因为题目区间通常是闭区间左端点等于右端点也算重叠。不同题目的区间开闭性会影响这个比较符号写代码前要先看清楚题面。6. 学习路径与实战记录从看懂到 AC 的完整过程6.1 个人学习顺序建议第一章八块内容我建议的学习顺序不完全是书上的目录顺序而是按依赖关系排先学离散化因为后面高精度、前缀和、区间合并都会用到二分查找和排序热完手直接学排序和二分。排序掌握足够好之后逆序对和区间合并都可以顺手做。接下来学二分这需要一个单独的时段因为边界问题需要专门记忆。然后是前缀和与差分注意区分“静态区间求和”前缀和和“动态区间修改”差分。高精度单独安排因为代码偏长是大整数计算的一个分支。最后是双指针和位运算这两块相对独立但内容核心花费时间不必太多。6.2 刷题时必踩的坑与调试技巧在这个阶段我遇到过的很典型的问题是模板能背但题目一变形就完全不会。后来我发现一个有效的做法不急着刷题先把每道模板题默写三遍要求每遍都能一遍过编译且零错误。把模板存进肌肉记忆后再开始变形题这时候的思考负担从“怎么写”转移到了“为什么这么写”进步会特别快。调试时也有几个心得二分答案不过时先把自己的边界写在一张纸上手动模拟一个三元素数组看每一轮 l、r、mid 怎么变。高精度加法结果不对就自己构造两个小数字在纸上列竖式对拍。前缀和数组算错检查s[i]的递推式和s[r]-s[l-1]的下标是否写反。区间合并卡壳就造几个边界区间[1,3]、[3,4]、[5,6]检查是大于还是大于等于。另外尽量避免通过特殊调试手段定位错误比如删代码打日志。先静态走查“下标能不能对齐、边界条件能不能自洽”大部分错误都能在脑子跑完一遍后自己暴露。6.3 调试与验证经常被忽略的细节很多人在本地跑测试用例时只测样例交上去就超时或越界。针对这类问题我从第一章就开始养成一个习惯每次写完模板题循环跑三组数据——最大值边界、最小值边界、全相同值。最大值边界测试数据范围最小值边界测试初始化全相同值测试分治或二分的等于分支。想让模板真正可靠这些“非典型”输入必须全过。还有一个关于数组长度的问题。比如区间合并读到很多区间时结果数组要先预留一倍空间高精度计算的结果数组则可能比两个输入都长开vector时别怕多开宁可开大也不要开小导致越界。7. 章节之外模板背后的思维如何迁移到后续算法7.1 二分与二分答案的关联第一章的二分模板解决“在有序数组里查找某个值”后续的二分答案解决的则是“在答案的可行域上找最优值”。思维上的关键转变是把check(mid)从“比较大小”改成“判断某个方案是否可行”。能提前想通这一点后面学最短路、最小生成树这类要把mid放进求解过程的问题会轻松很多。7.2 差分的“端点操作”思想差分数组的端点加减操作本质上提供了一种“把区间整体修改转化成两个点修改”的视角。这个视角在树状数组、线段树的区间更新解法里随处可见。很多人学LCA最近公共祖先时觉得树上差分难懂其实就是没把一维差分的这个视角吃透。一维简化成两个端点树上则简化成四个端点——本质是同一个思想在换场景。7.3 前缀和的预处理思维前缀和把“查询”的复杂度转移到了“预处理”上是典型的空间换时间。后续的滑动窗口、莫队、二维树状数组里都会用到类似的预处理加速查询技巧。如果你能把前缀和为什么要下标从1开始都理解透那么后面学树状数组的低效写法时会少走很多弯路。7.4 双指针与滑动窗口的扩展双指针的核心“单调移动”在后续滑动窗口题里被广泛应用变化形式是维护窗口状态、窗口右移和左移。章节里的最长不重复子序列就是滑动窗口的原型理解它之后能应对大多数窗口类题目遇到特殊的窗口收缩条件也能推理出来。7.5 位运算与状态压缩的衔接位运算在基础章里显得小但它还是状态压缩DP的基本工具。lowbit是树状数组的核心操作x (x-1)这种技巧更是枚举子集时的常客。如果在第一章把这些位运算全练熟后面遇到位运算类型的题目就不再需要现场硬啃。我个人在实际刷完这一章之后的体会是第一步的“背模板”不可跳过跳过了后面很多代码会陷入今天改边界明天改符号的死循环但一直停在背模板也不行必须尽快主动去理解每个模板“为什么要这样写边界”否则你连它适用的范围都判断不出来。最后再分享一个笨办法把每个模板的代码原文打印出来贴在屏幕边边写边看等哪一天你发现自己写出的代码和模板有一点不同但能解释为什么不同时这一章就算真正毕业了。后面即使暂时不碰算法题这些思维和模板也会在日常写代码时潜移默化地帮你写出更稳健的循环和边界判断。
阅读完成 · 觉得有帮助？
