开门见山。这个月我把某个算法训练平台的基础算法课第三部分刷完了，顺手整理了一份笔记。这部分内容集中在双指针、位运算、离散化和区间合并上，四个看起来“小而美”的专题，却是后面进阶算法里高频复用的基本功。

先说结论：这四个专题难度不大，但非常讲究“技巧性”。很多初学者容易卡在“明明思路听懂了，一写代码就错”的状态，十有八九是没吃透这几类题目的固定套路和边界处理。这篇文章我尽量把每个专题的关键思路、典型代码、踩坑点都掰开讲清楚，适合刚刷完排序和二分、正在往进阶走的同学参考。

1. 双指针算法：从暴力枚举到线性扫描的思维跃迁

1.1 双指针到底在优化什么

双指针算法听起来玄乎，本质上就是把两重循环优化成一重循环。最经典的场景是：一个数组里，你需要枚举所有满足某种条件的子区间，暴力写法是固定左端点i，让右端点j从i扫到n，时间复杂度O(n²)。双指针的优化思路是——让i和j都只往一个方向移动，不会回退，这样总移动次数是O(n)。

为什么i和j都能不回退？这才是理解双指针的关键。假设我们用i表示区间左端点，j表示区间右端点，当前区间[i, j]已经满足条件了。当i向右移动一步变成i'，区间变小了，那么原来满足的条件在新区间里仍然可能满足，而j不需要从i'重新开始扫，只需要基于原来的j继续扩展就行。这背后的逻辑是单调性——如果区间合法性和区间长度之间存在单调关系，双指针就能生效。

很多资料用“滑动窗口”来类比双指针，其实这俩不完全是一回事。滑动窗口更强调“窗口”的形态，左右边界都是浮动的；而双指针还包括两个指针同向移动的“快慢指针”场景，比如链表里找环。但在算法基础课这个阶段，双指针基本就是用来处理数组/字符串子区间问题的，按滑动窗口的思路去理解完全够用。

1.2 最经典的模板：最长连续不重复子序列

这个题目是理解双指针的绝佳入口，题目要求是：给定一个长度为n的整数序列，找出最长的不含重复数字的连续子序列长度。

暴力思路很简单：枚举起点i，然后让终点j从i开始一直往右走，用哈希表记录区间内每个数字出现的次数，一旦发现重复数字就停，更新答案。这个做法的复杂度是O(n²)，n到10⁵就完蛋。

双指针的做法长这样：

#include <iostream> using namespace std; const int N = 100010; int a[N], cnt[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; int res = 0; for (int i = 0, j = 0; j < n; j++) { cnt[a[j]]++; while (cnt[a[j]] > 1) { cnt[a[i]]--; i++; } res = max(res, j - i + 1); } cout << res << endl; return 0; }

代码很短，但每一行都有讲究。外层循环枚举的实际上是右端点j，每次把a[j]加入窗口。如果加入后a[j]出现了两次，说明窗口里有重复元素了，那就移动左指针i，把窗口左端的元素一个个从计数里去掉，直到a[j]的计数恢复为1。内层while每执行一次，i就右移一格。由于i在整个算法过程中只会向右移动不会回退，总移动次数不超过n，所以整体复杂度是O(n)。

我最初学这段代码的时候有个疑惑：为什么while里面只判断cnt[a[j]]是否大于1，而不是检查整个窗口有没有重复？答案在于——窗口在每一轮循环结束时一定是合法的，加入新元素后，唯一可能造成重复的只有这个新加进来的a[j]。所以只需要盯着它检查就够了。

实际做题的时候，数组开多大、cnt数组用不用memset清零、输入用scanf还是cin，这些细节都能影响你是否在比赛中白白罚时。序列元素可能范围较大时，更稳妥的做法是直接用unordered_map来计数，但它的常数比普通数组大不少。如果题目没给值的范围，可以考虑先离散化再用数组，这个后面细说。

1.3 双指针的扩展场景

除了最长连续不重复子序列，双指针还能处理很多看起来不太一样的问题。比如“数组元素的目标和”：给定两个升序数组A和B，再给定一个目标值x，要求在A和B中各找一个数，使得它们的和正好等于x。

这类题的经典做法是：i从A的头部开始，j从B的尾部开始。如果A[i] + B[j] > x，就让j左移；如果小于x，就让i右移；刚好等于就输出答案。两个指针都只朝一个方向移动，复杂度O(n + m)。这里用到的单调性是：A递增、B递减时，两数之和关于i递增、关于j递减，配合目标值就能像夹逼一样收敛到答案。

另外还有一个高频变体是“判断子序列”。给定两个字符串，判断较短的字符串是否是较长字符串的子序列。这本质也是双指针的经典应用——i指针指向短串，j指针指向长串，j不断向后移动，一旦遇到与短串当前字符相同的字符，i就前进一步。长串扫完时如果i走过的长度等于短串长度，说明每个字符都能按顺序找到，答案就是true。

这类题目里有一个很实用的经验：双指针的核心是找到那个“单调性的轴”。做题之前先问问自己：左指针右移会导致什么变化？右指针右移会导致什么变化？两者的变化方向是否一致或者相反？想清楚这个，代码基本就不会写错方向。

1.4 双指针常见错误清单

双指针代码看似简单，我见过身边不少人在这上面卡了很久，总结下来就三类错误：

第一类是while循环条件写错。有些题需要外层枚举i、内层移动j，有些题反过来外层枚举j、内层移动i。如果搞反了，要么答案偏大（漏掉了某些合法区间），要么复杂度退化。我自己的习惯是先固定“扩展的那一端”，再考虑“收缩的那一端”，并不会每次都死记模板。

第二类是忽略计数数组的恢复。比如上面最长不重复子序列的题，当左指针i右移时，必须把原来i位置的元素从cnt中减去。漏掉这一步，窗口里的计数就会失真，后续判断全部乱套。

第三类是边界处理不当。比如子序列问题里，j扫描完整个长串但i还没走完短串，说明匹配失败；再比如区间问题的双指针写法里，内层while结束的条件是“i > j”而不是“i == j”，因为当左指针越过右指针时，区间已经空了。这些边界条件不处理干净，代码很容易在线评测的极端数据上翻车。

2. 位运算：算法题里最不好直观理解的小技巧

2.1 为什么算法题爱考位运算

位运算在算法基础课里的戏份不算多，但出现即高频——它主要用来解决一类关于二进制表示的问题，最常见的就是统计一个数的二进制表示中有多少个1。这类问题的特点是用常规十进制思维很难想通，一旦理解了二进制运算的底层机制，代码又简洁得让人拍案叫绝。

计算机里一切数据说到底都是二进制。位运算包括与（&）、或（|）、异或（^）、取反（~）、左移（<<）、右移（>>）六种操作。算法题里最常用的其实是与运算配合右移操作来逐位提取，以及一个特殊技巧叫lowbit运算——用来提取一个数二进制表示中最右侧的1。

我做这类题最大的感受是：不要试图用十进制数学直觉去推导，要直接在纸上画出二进制位来模拟。有些规律光看代码很难体会，画几遍二进制演变图就通透了。

2.2 统计二进制中1的个数：两种解法对比

先看最常见的题目：输入n个整数，依次输出每个数的二进制表示中1的个数。n可以到10⁵甚至10⁶，每个数在int范围内。

解法一：逐位右移判断

int countOne(int x) { int res = 0; while (x) { if (x & 1) res++; x >>= 1; } return res; }

这个思路非常直白：x & 1能取出x的最低位，是1就计数加一，然后x右移一位，相当于丢掉最低位。循环直到x变成0为止。负数的右移是算术右移，最高位补1，所以这个写法在负数上会死循环——实际题目如果给的都是非负整数，这个写法没问题，但最好提前确认输入范围。

解法二：lowbit运算

lowbit运算的定义是：返回一个数的二进制表示中最低位的1所对应的数值。举个例子：x = 12时，二进制是1100，最低位的1在第2位（从0开始计数），对应数值就是4。lowbit(12) = 4。

计算lowbit有个著名公式：x & -x。为什么这个公式成立？关键在于负数的二进制表示是原数的补码。x和-x进行按位与，只有x最右侧的那个1位会保留下来，其余高位都为0。不理解就去纸上画一下12和-12的二进制，再对齐做与运算，一眼就能看明白。

统计1的个数就变成了：

int countOne(int x) { int res = 0; while (x) { x -= lowbit(x); res++; } return res; }

每次把x的最低位的1减去，循环多少次就说明有多少个1。两种解法复杂度都是O(k)，k二进制中1的个数。实际跑起来lowbit写法通常更快，因为跳过了值为0的高位部分。

2.3 lowbit运算的其他用途

lowbit除了数1的个数，还有一个重要应用场景——树状数组。树状数组里更新和查询都要用到i += lowbit(i)和i -= lowbit(i)这两个操作，用来在逻辑的树形结构上跳跃。所以千万不要觉得位运算算1的个数只是个孤立的小技巧，它其实是很多数据结构的基石。

我在刷题过程中还发现lowbit能用来快速判断一个数是不是2的整数次幂：如果x是正整数，且x & (x - 1) == 0，那x就是2的n次幂。这个等价于x的二进制表示里只有一个1。比循环判断高效得多，而且一行代码就能写完。

2.4 位运算题目的实操经验

位运算的题，代码写错通常不是逻辑错，而是运算优先级出错。C++里位运算的优先级低于比较运算，容易写出if (x & 1 == 0)这种实际上解析成x & (1 == 0)的代码。处理办法很简单——尽量把位运算用括号包起来，别嫌麻烦。

另一个经验是：涉及负数的位运算要格外小心。左移负数、右移负数、对负数取反，行为在不同编译器/平台上可能符合预期也可能不符合。竞赛环境里如果输入范围限定在非负整数，就放心用；如果可能为负，建议先确认题意。

我自己的习惯是在纸上先演练两个用例：一个值比较大的数（比如2³¹ - 1），一个边界数（比如0或者1）。0的特殊之处在于它的任何位运算结果都是0，循环根本不会执行；1则对应最低位为1的情况，很多边界错误都藏在这样的两种用例里。

3. 离散化：让稀疏的大范围数据变得可处理

3.1 什么时候需要离散化

离散化这个词听起来高端，实际上思路朴素得不能再朴素——把值域很大但个数很少的数据，映射成从1开始的连续整数，然后用数组代替哈希表来计数。

很多题目里数据范围会这样设计：n个操作，每次操作涉及一个位置x，x的范围可以达到10⁹，但n本身只有10⁵。这时候你没法开一个长度10⁹的数组（内存直接爆炸），但如果你把所有出现过的x收集起来，排序去重，一共也就n个不同的值，映射到1~m（m≤n）这m个连续下标上，就能用普通数组来存储每个位置的值了。

我最初学离散化时最大的困惑是：为什么不直接用一个map或者unordered_map存？原因在于两点。第一，数组的随机访问比哈希表快得多，常数小；第二，很多后续操作（比如求前缀和、二分查找）要求数据具有顺序性，而离散化后的数组天然是保序的，哈希表做不到。

3.2 离散化的标准实现流程

完整流程分三步：收集-排序-去重，然后是二分查找映射。

第一步，把所有可能出现的位置x存到一个vector里。第二步，sort()排序，然后用unique()和erase()去重。这两步配合使用是C++的标准写法：

vector<int> alls; // 把所有相关位置加入alls sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());

unique()会把重复元素移动到容器末尾，返回新逻辑结尾的迭代器，然后erase删掉后面的重复元素。这行代码应该背下来，刷题常用。

第三步，实现一个映射函数，把原始位置x映射到下标：

int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return l + 1; // 从1开始方便前缀和 }

这里返回l+1，而不是l，是为了让映射后的下标从1开始。这样后面做前缀和的时候，sum[i] = sum[i-1] + a[i]不需要单独处理0号下标，能省很多边界判断的麻烦。这是一个很小的经验，但能让你写代码时少踩不少坑。

3.3 典型例题：区间和

有一道经典题叫区间和，描述是这样的：坐标轴上有一个数轴，n次操作在某个位置x加上一个数c，然后m次询问，每次问[l, r]区间内所有数的和。x、l、r的范围可以到10⁹，但n和m之和不超过10⁵。

做法就是在读入所有操作时把x、l、r都收集到alls里，排序去重后，用离散化后的下标存储每个位置的值，然后求前缀和数组，再对每次询问在alls里二分定位到离散化后的下标，用前缀和相减得出区间和。

完整代码如下：

#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; int a[N], s[N]; vector<int> alls; vector<PII> add, query; int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return l + 1; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 0; i < m; i++) { int l, r; cin >> l >> r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); for (auto item : add) { int idx = find(item.first); a[idx] += item.second; } for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i]; for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }

这个例子信息量很大：它同时用到了离散化、二分查找和前缀和，是一个综合性的应用场景。如果把这段代码吃透，不仅离散化会了，二分的边界处理和前缀和的思想也能得到巩固。

3.4 离散化避坑要点

第一，alls数组里必须把查询的l和r也加入。很多人一开始只加入修改操作的位置x，结果查询时在alls里找不到l和r对应的下标，代码直接越界。别问我是怎么知道的。

第二，find函数的前提是x一定存在于alls中。因为所有可能出现的坐标在收集阶段都加入了alls，所以查找一定能找到。如果你自定义的数据没有提前收集就调用find，二分结果就不确定。

第三，unique和erase的搭配。有些C++版本里unique返回的迭代器指向去重后的最后一个元素的下一个位置，如果忘记erase，后续用alls.size()取长度时会把重复元素也算进去，导致a数组分配空间不够或者find出现逻辑错误。

第四，下标从1开始的收益。前面提到了，从1开始做前缀和可以避免对下标0的特殊处理。如果你第一次写的时候下标从0开始，你会发现后面处理前缀和时要额外判断l > 0的情况，烦得很。从我个人的体验来说，这个从1开始的小习惯值得刻意养成。

4. 区间合并：贪心思想的第一次真正落地

4.1 问题定义与解题思路

区间合并是基础算法课里一个承上启下的内容。题目描述很简单：给定n个区间，把有重叠（包括端点相接）的区间合并成一个区间，最后输出合并后的区间个数和每个区间的起止位置。

暴力做法是先对每个区间遍历其他区间判断是否重叠，时间复杂度O(n²)；更麻烦的是区间合并的结果还可能级联（合并后的新区间又和其他区间重叠）。所以这类题的标准解法是贪心：先把所有区间按照左端点从小到大排序，然后依次扫描，维护一个当前合并区间的右端点。

贪心的正确性在于：排序后，左端点小的区间一定先被处理。当前扫描到的区间是否要和维护中的区间合并，完全取决于它的左端点是否不超过当前区间的右端点——如果不超过，则重叠，需要把右端点更新为两者中较大的值；如果超过，则维护中的区间已经无法与后续任何区间合并，可以输出并重新开始维护新的区间。

4.2 代码实现与细节

#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; void merge(vector<PII> &segs) { vector<PII> res; sort(segs.begin(), segs.end()); int st = -2e9, ed = -2e9; for (auto seg : segs) { if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else { ed = max(ed, seg.second); } } if (st != -2e9) res.push_back({st, ed}); segs = res; } int main() { int n; cin >> n; vector<PII> segs; for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; segs.push_back({l, r}); } merge(segs); cout << segs.size() << endl; return 0; }

这里的st和ed初始值设置成-2e9，是因为区间坐标可能为负，用极小值初始化使得第一次扫描时不会误判为“不重叠”。最后扫描结束后还要把最后一个未输出的合并区间push进结果数组，这地方漏掉的话，答案会少一个区间。

4.3 端点重合的处理策略

判断两个区间是否重叠，标准写法是判断当前区间的左端点是否大于维护区间的右端点。也就是ed < seg.first时不重叠，否则重叠。注意这里用的是严格小于，说明当ed == seg.first时（前一个区间的右端点和后一个区间的左端点重合），我们仍然认为它们重叠并合并。

这个细节在不同题目里有不同要求。有些题目明确说区间端点相接触不算合并，那判断条件就要变成ed <= seg.first。我建议每次做题先读清楚题目里对“重叠”的定义，不要想当然地套模板。

4.4 区间合并的变体与应用

区间合并看起来教学意义大于实用意义，但它实际上是很多复杂区间算法的基石。比如扫描线算法求矩形面积并，初始步骤就是把所有矩形的竖边按x坐标排序，然后用类似区间合并的方式维护当前覆盖区间的y方向长度。再比如求最多能保留多少个互不重叠的区间（区间选点问题），也是先排序区间再用贪心策略。

所以在这个阶段花一点时间把区间合并彻底吃透是值得的。我自己的感受是，算法学习到后面会发现很多高级内容都能拆解成基础算法的组合：区间合并 + 线段树、区间合并 + 差分、区间合并 + 扫描线等，都是很常见的组合拳。

经验提示：排序pair默认先按第一关键字升序，再按第二关键字升序。区间合并只依赖左端点单调递增，右端点顺序无所谓，所以直接对vector<PII>排序即可。但如果你写的是自定义结构体，记得在sort时传入cmp函数。

4.5 写区间合并时的三个易错点

我先说我自己踩过的一个坑：只更新右端点不取最大值。如果不取max，当新区间完全被当前合并区间包含时，合并后的右端点反而变小了，后续判断全部错乱。所以合并时的右端点更新一定是ed = max(ed, seg.second)，不是ed = seg.second。

第二个坑是忘记最后一段的入库。循环结束时维护的区间已经无法与后续区间合并，但还没有push进res，需要在循环外单独处理一次。写代码理流程的时候，拿两个用例模拟一遍就能发现。

第三个坑是初始值设置不当。如果区间坐标全为正数，初始值设成-1可能没问题；但坐标可以为负时就必须设成一个足够小的数。还有一个细节是初始值要能保证“第一次扫描时不产生误判”，一般用-2e9或INT_MIN都能达到目的，但有些同学习惯用0就会出问题——题目给的最小坐标是-10时，第一次扫描就全乱套了。

5. 从笔记到能力的两个关键习惯

5.1 用自己的语言整理模板，而不是抄模板

这一部分内容我写笔记的时候最大的体会是：模板要自己推导一遍，再写进笔记。直接抄老师或者题解里的模板，当时看懂了，过两天就忘记了。但如果能自己把双指针的移动过程、位运算lowbit的推导、离散化为什么下标从1开始等问题重新表述一遍，就会真正内化成自己的东西。

我在笔记里给每个算法都配了一个“为什么这样写”的段落，用大白话解释每一步的逻辑。比如双指针模板里为什么要cnt[a[j]]++在先、while判断在后，再比如离散化的find函数为什么用二分而不是直接用lower_bound。就是这些“为什么”，在考试和比赛中帮助我快速还原代码，而不是死记硬背。

5.2 刷题时主动给题目归类

基础算法这个阶段，题目类型非常鲜明，做题时不用追求题量，但每道题要想清楚它考的是哪个专题的哪个变体。我在刷题时会记录一个表格，写上题目编号、核心算法、特殊之处、犯了什么错、怎么改对的。这样到后面的图论、动态规划阶段，遇到新的题目能迅速联想到“这题可以拆成区间合并+贪心”“这题就是双指针+排序”等组合，解题速度快很多。

6. 写在最后：基础不牢，地动山摇

这一篇笔记覆盖的双指针、位运算、离散化和区间合并，单个拿出来看难度都不高，组合起来能覆盖的题目范围却非常惊人。我个人最深的体会是：刷题快慢不取决于你背了多少模板，而取决于你对每个基础专题的理解有没有到位。双指针的单调性、位运算的二进制直觉、离散化的保序映射、区间合并的贪心证明，每一个都值得多花半小时慢慢消化。

如果你现在刷这些题感觉有点吃力，不用慌，这是非常正常的阶段。我当初也是把最长连续不重复子序列那道题写了三遍才彻底搞懂。多写几遍，多模拟几个极端用例，很快就能找到感觉。下一篇笔记我会继续整理基础算法里剩余的内容，包括高精度运算和前缀和差分。到时候见。