尧图网页设计 
如果你在刷算法题时遇到过这样的场景题目给出的数据范围是1 ≤ n ≤ 10^5但每个数据的值却可能高达-10^9 ≤ a[i] ≤ 10^9甚至更大。你想用数组下标直接映射这些值却发现a[i]可能为负数或者数值跨度极大直接开一个10^9大小的数组根本不现实。这时一个看似简单却极其关键的技巧就派上用场了——离散化。它不是什么高深的算法而是一种将“无限”或“超大”空间中的有限个数据映射到“紧凑”的连续整数空间的思想。很多初学者在遇到需要离散化的题目时要么暴力开大数组导致内存超限要么因为处理边界和去重问题而频频出错。本文将彻底讲透 C 中的离散化。我们不只告诉你“离散化是什么”更会深入剖析“为什么需要它”、“它解决了哪些具体问题”并通过多个实战代码模板让你真正掌握这一在算法竞赛、面试和数据处理中必备的“空间压缩”利器。读完本文你将能清晰判断何时该用离散化并拥有可直接复用的、经过边界测试的 C 代码模板。1. 离散化到底解决了什么问题在开始写代码之前我们必须先理解离散化的核心价值。它本质上是一种数据预处理技术目标是将原本稀疏、离散、范围巨大的数值映射为从 0 或 1 开始的连续整数索引。它解决的典型痛点包括数组下标越界与内存浪费这是最直接的动机。例如你有 1000 个点坐标范围在[-1e9, 1e9]。如果你想用vis[坐标]来标记某个点是否访问过直接开2e9大小的数组是不可能的。离散化后你只需要一个大小为 1000 的数组。为高级数据结构铺路许多数据结构如树状数组 (Fenwick Tree)、线段树 (Segment Tree)其底层实现通常依赖于连续的整数下标。当原始数据值域很大但数据量不多时离散化是使用这些数据结构的前提。简化比较与排序将复杂对象如结构体的某个关键属性如分数、ID映射为简单整数后排序、去重、二分查找等操作会变得非常高效和直观。统一数据尺度在数据分析和机器学习特征工程中离散化可以将连续数值转换为分类标签便于后续处理。一个经典类比想象你有一个班级学生的学号这些学号是学校统一分配的可能从 20230001 到 20231000中间还有空号。现在你要按学号顺序建立一个花名册数组。你当然不能开一个大小为 20231000 的数组只为了存放这 1000 个学生。更聪明的做法是收集所有实际存在的学号排序然后给第 1 个学号标为 1 号同学第 2 个学号标为 2 号同学……这样你的花名册数组大小就只需要 1000。这里的“学号”就是原始数据“1,2,3…”就是离散化后的索引。在算法题中离散化最常见的应用场景是“数值范围大但实际出现的数值个数少”。接下来我们就从原理到实现一步步拆解。2. 离散化的核心原理与步骤离散化的过程可以抽象为以下三个核心步骤理解了这个流程代码就是顺理成章的事情。2.1 第一步收集与排序将所有需要被离散化的原始数据我们称之为原始值放入一个数组通常叫alls。这个数组可能来自题目输入也可能是根据查询动态生成的。 然后对这个数组进行排序。排序的目的是为后续的二分查找做准备因为我们需要快速找到某个原始值对应的新索引。2.2 第二步去重关键排序之后紧接着必须进行去重。这是离散化最容易出错的一步。为什么必须去重 因为离散化要求建立的是“原始值”到“唯一索引”的一一映射。如果alls数组中有重复的原始值那么同一个值就会对应多个不同的索引这将导致后续逻辑完全混乱。例如你想查询值5出现了几次如果5在alls中出现了两次你该返回哪个索引对应的计数呢在 C 中排序后去重的“标准动作”是使用erase和unique函数sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());unique函数会将相邻的重复元素“移动”到容器末尾并返回指向第一个重复元素的迭代器erase则负责删除这些重复项。2.3 第三步映射查询经过排序和去重alls数组中的每个元素都有了唯一的、按升序排列的位置下标0, 1, 2...。这个位置就是它的新索引。 当我们需要查询某个原始值x对应的离散化索引时只需要在alls数组中二分查找x的位置。int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; // 通常映射到1-based索引 }这里使用lower_bound返回第一个大于等于x的元素位置。因为alls中已经包含x所以一定能找到确切位置。- alls.begin()得到从 0 开始的偏移量1是为了将其转换为从 1 开始的索引很多时候更方便比如配合前缀和或树状数组。整个过程的核心思想用索引的“连续性”和“紧凑性”换取值域的“无限性”。我们不再关心原始值的绝对大小只关心它们的相对顺序。3. 环境准备与代码框架在实现具体的离散化模板前我们需要一个清晰的 C 编程环境。本文假设你使用C11或更高标准并且熟悉 STL 中的vector,sort,unique,lower_bound等组件。一个典型的离散化问题会涉及以下元素原始数据数组a存放待处理的原始数值。离散化数组alls存放所有需要被映射的唯一原始值。映射后的操作数组b以离散化索引为下标进行加、减、求和等操作。查询数组query存放需要查询的区间或点。下面我们从一个最简单的“求区间和”问题出发构建完整的离散化解决方案。4. 实战案例区间加法与求和离散化 前缀和这是离散化最经典的入门题也是理解其价值的绝佳例子。问题描述 在一个无限长的数轴上坐标范围-10^9到10^9进行n次操作每次操作在某个坐标x上加一个值c。然后进行m次询问每次询问某个区间[l, r]内所有位置值的总和。n, m ≤ 10^5。传统思路的困境如果直接开数组arr[-1e9...1e9]来存储每个坐标的值内存直接爆炸。离散化思路我们只关心那些被操作过加点或被查询到区间端点的坐标。将这些坐标全部收集起来。对这些坐标进行离散化映射到1...k(k ≤ 2n2m因为每个操作和查询会引入至多2个点)。在一个大小为k5的数组b上进行加法和前缀和操作b[i]对应的是离散化后索引i所代表的原始坐标上的值。查询时将原始的l, r通过同样的映射找到离散化后的索引L, R然后在b的前缀和数组上计算sum[R] - sum[L-1]。4.1 完整代码实现与逐行解析#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; // 用于存储操作和查询 const int N 300010; // n, m ≤ 1e5, 最多有 n 2m 个点开3e5足够 int n, m; int a[N], s[N]; // a是离散化后的数组s是前缀和 vectorint alls; // 存储所有待离散化的坐标 vectorPII add, query; // add存储加操作query存储询问 // 二分查找函数找到x在alls中离散化后的位置1-based index 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 r 1; // 映射到1, 2, ... n // 也可以使用STLreturn lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; } int main() { // 1. 读入数据 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); // 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); } // 2. 离散化核心步骤排序 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 3. 处理加操作将加法施加到离散化后的数组a上 for (auto item : add) { int x find(item.first); // 找到原始坐标x离散化后的索引 int c item.second; a[x] c; // 在离散化后的位置进行加法 } // 4. 预处理前缀和 for (int i 1; i alls.size(); i) { s[i] s[i - 1] a[i]; } // 5. 处理查询 for (auto item : query) { int l find(item.first); int r find(item.second); cout s[r] - s[l - 1] endl; // 利用前缀和快速计算区间和 } return 0; }关键点解析alls数组的内容它包含了所有“有意义”的坐标即所有操作点和查询边界点。这是离散化能压缩空间的前提。find函数这是离散化的灵魂。它通过二分查找将任意一个原始坐标x快速转换为它在alls中的紧凑索引从1开始。lower_bound是更简洁的 STL 实现方式。数组a的大小a的下标范围是1 ~ alls.size()大小仅为实际出现的不同坐标数远小于原始值域。前缀和s在离散化后的紧凑数组上计算前缀和使得区间查询复杂度降至 O(1)。4.2 输入输出示例假设输入如下3 3 1 2 3 6 7 5 1 3 4 6 7 8程序内部过程alls收集的坐标[1, 3, 7, 1, 3, 4, 6, 7, 8](来自操作点1,3,7和查询区间[1,3],[4,6],[7,8])排序去重后[1, 3, 4, 6, 7, 8]离散化映射1-1, 3-2, 4-3, 6-4, 7-5, 8-6执行加法a[1]2, a[2]6, a[5]5前缀和数组s:[0, 2, 8, 8, 8, 13, 13](下标从0开始s[0]0)处理查询[1,3]-[1,2]-s[2]-s[0]8[4,6]-[3,4]-s[4]-s[2]0[7,8]-[5,6]-s[6]-s[4]5输出8 0 55. 离散化的通用模板与变体上面的例子展示了离散化与前缀和的结合。实际上离散化模板本身是独立的。我们可以将其抽象出来方便在不同场景下调用。5.1 模板一基于vector和lower_bound(推荐)这是最通用、最清晰的写法适用于绝大多数情况。#include vector #include algorithm using namespace std; // 离散化类或结构体 class Discretizer { private: vectorint alls; // 存储所有待离散化的值 public: // 添加一个待离散化的值 void add(int x) { alls.push_back(x); } // 预处理排序并去重。在所有值添加完毕后调用。 void prepare() { sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); } // 查询 x 离散化后的结果 (1-based index) int get(int x) { // 使用 lower_bound 进行二分查找 return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; } // 查询离散化后索引对应的原始值 (1-based index) int original(int idx) { return alls[idx - 1]; // 因为 get 返回的是 1-based } // 获取离散化后值域的大小 int size() { return alls.size(); } }; // 使用示例 int main() { Discretizer d; // 假设有一些数据 vectorint data {1000000000, 1, -1000000000, 1, 500, 500}; // 1. 添加所有值 for (int x : data) { d.add(x); } // 2. 预处理 d.prepare(); // 此时 alls 为 [-1000000000, 1, 500, 1000000000] // 3. 查询离散化索引 cout d.get(-1000000000) endl; // 输出 1 cout d.get(1) endl; // 输出 2 cout d.get(500) endl; // 输出 3 cout d.get(1000000000) endl; // 输出 4 // 4. 根据索引查原始值 cout d.original(1) endl; // 输出 -1000000000 return 0; }5.2 模板二手写二分查找在一些对性能极其敏感或不允许使用 STL 的场合如某些特殊竞赛环境可以手写二分。int find(int x, vectorint alls) { 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-based index } // 注意使用此函数前必须确保 alls 已排序且包含 x。5.3 模板三离散化结合map进行双向查找如果你需要频繁地根据索引查找原始值除了用alls数组也可以使用unordered_map或map来记录映射关系实现 O(1) 或 O(log n) 的查询。#include vector #include algorithm #include unordered_map using namespace std; class DiscretizerWithMap { private: vectorint alls; unordered_mapint, int val2idx; // 值-索引 unordered_mapint, int idx2val; // 索引-值 (如果需要) public: void add(int x) { alls.push_back(x); } void prepare() { sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 构建映射表 for (int i 0; i alls.size(); i) { val2idx[alls[i]] i 1; // 1-based // idx2val[i 1] alls[i]; } } int get(int x) { // 直接查表比二分更快但需要额外空间 return val2idx[x]; } int original(int idx) { return alls[idx - 1]; // 或者 return idx2val[idx]; } };选择建议在算法竞赛中模板一vectorlower_bound因其简洁、高效、内存友好是绝对的主流选择。map版本在需要极高频双向查找且内存不敏感时可以考虑。6. 进阶应用离散化与树状数组结合离散化真正发挥威力的地方是与树状数组、线段树等高级数据结构结合解决“动态区间问题”。一个经典问题是逆序对统计但这里我们看一个更通用的“区间更新、单点查询”或“单点更新、区间查询”问题。问题数轴上有若干线段每条线段覆盖一个区间[l, r]。有多次查询每次问某个点x被多少条线段覆盖。如果坐标范围很大就需要离散化。思路将所有的l,r,x加入alls进行离散化。离散化后每条线段覆盖的区间[L, R]对应到紧凑的整数区间。问题转化为在一个较小的数组上进行多次区间加1线段覆盖然后进行多次单点查询问某个点被覆盖几次。这正好是树状数组或差分数组的经典应用场景。代码示例差分数组法离散化后#include iostream #include vector #include algorithm using namespace std; const int N 200010; // 最多 n 条线段m 次查询最多 2nm 个点 int diff[N]; // 差分数组 vectorint alls; int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; } int main() { int n, m; cin n m; vectorpairint, int segs(n); vectorint queries(m); // 读入线段和查询点 for (int i 0; i n; i) { cin segs[i].first segs[i].second; alls.push_back(segs[i].first); alls.push_back(segs[i].second); } for (int i 0; i m; i) { cin queries[i]; alls.push_back(queries[i]); } // 离散化 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 在离散化后的坐标上使用差分数组处理区间加 for (auto seg : segs) { int L find(seg.first); int R find(seg.second); diff[L] 1; diff[R 1] - 1; // 注意这里是离散化后的R线段覆盖是闭区间[l, r] } // 计算前缀和得到每个点的覆盖次数 vectorint cover(alls.size() 2, 0); for (int i 1; i alls.size(); i) { cover[i] cover[i - 1] diff[i]; } // 回答查询 for (int x : queries) { int idx find(x); cout cover[idx] endl; } return 0; }这个例子清晰地展示了离散化如何将一个大值域的几何问题转化为一个小数组上的差分/前缀和问题。7. 常见问题、陷阱与排查指南离散化思路清晰但实现时细节决定成败。下表总结了最常见的“坑”问题现象可能原因排查方式解决方案运行时错误如数组越界find函数返回的索引超出了alls数组的范围。检查find函数逻辑特别是二分查找的边界条件。确认查询的值x一定在alls中。1. 确保alls包含了所有需要查询的值。2. 二分查找使用lower_bound时确保容器已排序。3. 如果查询值可能不在alls中需要特别处理返回-1或插入。答案错误逻辑混乱忘记对alls进行去重。在sort后打印alls的大小和内容检查是否有重复元素。务必在排序后调用alls.erase(unique(alls.begin(), alls.end()), alls.end());答案错误映射不一致离散化前后使用了不同的映射关系。例如加法用了一套alls查询用了另一套。确保整个程序只维护一个alls向量所有数据的映射都基于它。将所有需要离散化的点操作点、查询点一次性加入同一个alls然后统一预处理。性能不佳在循环中多次调用sort和unique。检查代码确保prepare()或排序去重操作只执行了一次在所有数据添加完毕之后。将添加数据和预处理分成两个清晰的阶段。处理区间时出错离散化后区间的性质可能改变。例如原区间[l, r]离散化后[L, R]可能不再是连续覆盖。思考离散化是否适用于当前问题。对于“区间覆盖点数”类问题离散化是安全的。对于“区间长度”类问题可能需要将点转化为段。理解问题本质。对于涉及“连续区间内点的个数”的问题离散化直接可用。对于涉及“连续区间长度”的问题可能需要将每个点视为一个单位长度段的左端点。查询值不在alls中题目可能询问一个从未出现过的坐标的值。仔细读题。如果查询值可能不存在lower_bound会返回第一个大于等于它的位置这可能不是你想要的行为。根据题意处理1. 若查询值不存在则忽略或输出0需判断alls[pos] x。2. 若需要动态插入则考虑使用map或平衡树而非一次性离散化。一个重要的边界情况当处理区间操作时如果题目中的区间是闭区间[l, r]且操作是影响区间内的点那么离散化l和r通常就足够了。但如果操作是影响以点为边界的段可能需要将r1也加入离散化集合。这需要根据具体问题逻辑分析。8. 最佳实践与工程建议将离散化从竞赛技巧转化为可靠的工程代码需要注意以下几点封装与复用如模板所示将离散化逻辑封装成一个类 (Discretizer)。这提高了代码的清晰度和复用性避免了全局变量alls的滥用。索引基准选择通常使用1-based索引。这有两个好处一是与许多数据结构如树状数组、前缀和数组的惯例保持一致s[0] 0作为哨兵二是避免“下标-1”的思维转换减少错误。在find函数中返回index 1即可。lower_boundvsupper_bound绝大多数情况下使用lower_bound找到第一个大于等于x的位置。因为我们的alls包含x所以找到的就是x的确切位置。只有在处理一些特殊边界如找最后一个小于等于x的位置时才考虑upper_bound并减一。空间预估在竞赛中根据题目给出的n和m上限预估alls的最大大小并提前分配空间如vector::reserve可以避免不必要的动态扩容开销。例如n次操作和m次查询最多可能有n 2*m个点。与 STL 的协同C STL 的sort,unique,lower_bound在随机访问迭代器上效率很高足以应对10^5级别的数据。放心使用无需手写除非有特殊限制。调试输出在复杂问题中离散化后打印出alls数组和关键的映射关系如x - idx是验证逻辑是否正确的最快方法。9. 总结与扩展方向离散化不是一个算法而是一种思想一种在“无限”中处理“有限”的桥梁思想。它通过建立映射让那些依赖连续、紧凑下标的数据结构和算法数组、前缀和、树状数组、线段树得以在稀疏、大值域的数据上大展拳脚。掌握本文的模板和思路你就能解决 LeetCode、AcWing、Codeforces 等平台上绝大多数需要离散化的问题。例如LeetCode 315. 计算右侧小于当前元素的个数需要离散化数组值然后使用树状数组从右向左统计。LeetCode 699. 掉落的方块方块在 x 轴上的位置范围可能很大但方块数量有限离散化 x 坐标后可以用线段树维护每个区间的高度。区间染色、区间最大覆盖次数等问题。下一步深入学习的方向离散化 扫描线解决二维平面上的矩形面积、矩形周长等问题。将 y 坐标离散化用线段树维护 x 轴扫描过程中的状态。动态离散化如果数据流式输入无法预先知道所有值可以考虑使用std::map或std::unordered_map来维护动态的映射关系但会牺牲一些性能和简洁性。离散化与哈希的权衡当值域极大但数据量不大时离散化是首选。如果数据量也很小或者需要保留原始值的映射关系用于输出使用map也是不错的选择。但在追求极致性能的竞赛中离散化数组二分查找通常优于map。最后记住离散化的核心口诀“值域大个数少先收集再排序务必去重二分映射”。把本文的模板收藏下来下次遇到需要“压缩空间”的题目时它就是你的标准解决方案。 C++离散化详解：原理、模板与实战应用
如果你在刷算法题时遇到过这样的场景题目给出的数据范围是1 ≤ n ≤ 10^5但每个数据的值却可能高达-10^9 ≤ a[i] ≤ 10^9甚至更大。你想用数组下标直接映射这些值却发现a[i]可能为负数或者数值跨度极大直接开一个10^9大小的数组根本不现实。这时一个看似简单却极其关键的技巧就派上用场了——离散化。它不是什么高深的算法而是一种将“无限”或“超大”空间中的有限个数据映射到“紧凑”的连续整数空间的思想。很多初学者在遇到需要离散化的题目时要么暴力开大数组导致内存超限要么因为处理边界和去重问题而频频出错。本文将彻底讲透 C 中的离散化。我们不只告诉你“离散化是什么”更会深入剖析“为什么需要它”、“它解决了哪些具体问题”并通过多个实战代码模板让你真正掌握这一在算法竞赛、面试和数据处理中必备的“空间压缩”利器。读完本文你将能清晰判断何时该用离散化并拥有可直接复用的、经过边界测试的 C 代码模板。1. 离散化到底解决了什么问题在开始写代码之前我们必须先理解离散化的核心价值。它本质上是一种数据预处理技术目标是将原本稀疏、离散、范围巨大的数值映射为从 0 或 1 开始的连续整数索引。它解决的典型痛点包括数组下标越界与内存浪费这是最直接的动机。例如你有 1000 个点坐标范围在[-1e9, 1e9]。如果你想用vis[坐标]来标记某个点是否访问过直接开2e9大小的数组是不可能的。离散化后你只需要一个大小为 1000 的数组。为高级数据结构铺路许多数据结构如树状数组 (Fenwick Tree)、线段树 (Segment Tree)其底层实现通常依赖于连续的整数下标。当原始数据值域很大但数据量不多时离散化是使用这些数据结构的前提。简化比较与排序将复杂对象如结构体的某个关键属性如分数、ID映射为简单整数后排序、去重、二分查找等操作会变得非常高效和直观。统一数据尺度在数据分析和机器学习特征工程中离散化可以将连续数值转换为分类标签便于后续处理。一个经典类比想象你有一个班级学生的学号这些学号是学校统一分配的可能从 20230001 到 20231000中间还有空号。现在你要按学号顺序建立一个花名册数组。你当然不能开一个大小为 20231000 的数组只为了存放这 1000 个学生。更聪明的做法是收集所有实际存在的学号排序然后给第 1 个学号标为 1 号同学第 2 个学号标为 2 号同学……这样你的花名册数组大小就只需要 1000。这里的“学号”就是原始数据“1,2,3…”就是离散化后的索引。在算法题中离散化最常见的应用场景是“数值范围大但实际出现的数值个数少”。接下来我们就从原理到实现一步步拆解。2. 离散化的核心原理与步骤离散化的过程可以抽象为以下三个核心步骤理解了这个流程代码就是顺理成章的事情。2.1 第一步收集与排序将所有需要被离散化的原始数据我们称之为原始值放入一个数组通常叫alls。这个数组可能来自题目输入也可能是根据查询动态生成的。 然后对这个数组进行排序。排序的目的是为后续的二分查找做准备因为我们需要快速找到某个原始值对应的新索引。2.2 第二步去重关键排序之后紧接着必须进行去重。这是离散化最容易出错的一步。为什么必须去重 因为离散化要求建立的是“原始值”到“唯一索引”的一一映射。如果alls数组中有重复的原始值那么同一个值就会对应多个不同的索引这将导致后续逻辑完全混乱。例如你想查询值5出现了几次如果5在alls中出现了两次你该返回哪个索引对应的计数呢在 C 中排序后去重的“标准动作”是使用erase和unique函数sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());unique函数会将相邻的重复元素“移动”到容器末尾并返回指向第一个重复元素的迭代器erase则负责删除这些重复项。2.3 第三步映射查询经过排序和去重alls数组中的每个元素都有了唯一的、按升序排列的位置下标0, 1, 2...。这个位置就是它的新索引。 当我们需要查询某个原始值x对应的离散化索引时只需要在alls数组中二分查找x的位置。int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; // 通常映射到1-based索引 }这里使用lower_bound返回第一个大于等于x的元素位置。因为alls中已经包含x所以一定能找到确切位置。- alls.begin()得到从 0 开始的偏移量1是为了将其转换为从 1 开始的索引很多时候更方便比如配合前缀和或树状数组。整个过程的核心思想用索引的“连续性”和“紧凑性”换取值域的“无限性”。我们不再关心原始值的绝对大小只关心它们的相对顺序。3. 环境准备与代码框架在实现具体的离散化模板前我们需要一个清晰的 C 编程环境。本文假设你使用C11或更高标准并且熟悉 STL 中的vector,sort,unique,lower_bound等组件。一个典型的离散化问题会涉及以下元素原始数据数组a存放待处理的原始数值。离散化数组alls存放所有需要被映射的唯一原始值。映射后的操作数组b以离散化索引为下标进行加、减、求和等操作。查询数组query存放需要查询的区间或点。下面我们从一个最简单的“求区间和”问题出发构建完整的离散化解决方案。4. 实战案例区间加法与求和离散化 前缀和这是离散化最经典的入门题也是理解其价值的绝佳例子。问题描述 在一个无限长的数轴上坐标范围-10^9到10^9进行n次操作每次操作在某个坐标x上加一个值c。然后进行m次询问每次询问某个区间[l, r]内所有位置值的总和。n, m ≤ 10^5。传统思路的困境如果直接开数组arr[-1e9...1e9]来存储每个坐标的值内存直接爆炸。离散化思路我们只关心那些被操作过加点或被查询到区间端点的坐标。将这些坐标全部收集起来。对这些坐标进行离散化映射到1...k(k ≤ 2n2m因为每个操作和查询会引入至多2个点)。在一个大小为k5的数组b上进行加法和前缀和操作b[i]对应的是离散化后索引i所代表的原始坐标上的值。查询时将原始的l, r通过同样的映射找到离散化后的索引L, R然后在b的前缀和数组上计算sum[R] - sum[L-1]。4.1 完整代码实现与逐行解析#include iostream #include vector #include algorithm using namespace std; typedef pairint, int PII; // 用于存储操作和查询 const int N 300010; // n, m ≤ 1e5, 最多有 n 2m 个点开3e5足够 int n, m; int a[N], s[N]; // a是离散化后的数组s是前缀和 vectorint alls; // 存储所有待离散化的坐标 vectorPII add, query; // add存储加操作query存储询问 // 二分查找函数找到x在alls中离散化后的位置1-based index 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 r 1; // 映射到1, 2, ... n // 也可以使用STLreturn lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; } int main() { // 1. 读入数据 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); // 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); } // 2. 离散化核心步骤排序 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 3. 处理加操作将加法施加到离散化后的数组a上 for (auto item : add) { int x find(item.first); // 找到原始坐标x离散化后的索引 int c item.second; a[x] c; // 在离散化后的位置进行加法 } // 4. 预处理前缀和 for (int i 1; i alls.size(); i) { s[i] s[i - 1] a[i]; } // 5. 处理查询 for (auto item : query) { int l find(item.first); int r find(item.second); cout s[r] - s[l - 1] endl; // 利用前缀和快速计算区间和 } return 0; }关键点解析alls数组的内容它包含了所有“有意义”的坐标即所有操作点和查询边界点。这是离散化能压缩空间的前提。find函数这是离散化的灵魂。它通过二分查找将任意一个原始坐标x快速转换为它在alls中的紧凑索引从1开始。lower_bound是更简洁的 STL 实现方式。数组a的大小a的下标范围是1 ~ alls.size()大小仅为实际出现的不同坐标数远小于原始值域。前缀和s在离散化后的紧凑数组上计算前缀和使得区间查询复杂度降至 O(1)。4.2 输入输出示例假设输入如下3 3 1 2 3 6 7 5 1 3 4 6 7 8程序内部过程alls收集的坐标[1, 3, 7, 1, 3, 4, 6, 7, 8](来自操作点1,3,7和查询区间[1,3],[4,6],[7,8])排序去重后[1, 3, 4, 6, 7, 8]离散化映射1-1, 3-2, 4-3, 6-4, 7-5, 8-6执行加法a[1]2, a[2]6, a[5]5前缀和数组s:[0, 2, 8, 8, 8, 13, 13](下标从0开始s[0]0)处理查询[1,3]-[1,2]-s[2]-s[0]8[4,6]-[3,4]-s[4]-s[2]0[7,8]-[5,6]-s[6]-s[4]5输出8 0 55. 离散化的通用模板与变体上面的例子展示了离散化与前缀和的结合。实际上离散化模板本身是独立的。我们可以将其抽象出来方便在不同场景下调用。5.1 模板一基于vector和lower_bound(推荐)这是最通用、最清晰的写法适用于绝大多数情况。#include vector #include algorithm using namespace std; // 离散化类或结构体 class Discretizer { private: vectorint alls; // 存储所有待离散化的值 public: // 添加一个待离散化的值 void add(int x) { alls.push_back(x); } // 预处理排序并去重。在所有值添加完毕后调用。 void prepare() { sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); } // 查询 x 离散化后的结果 (1-based index) int get(int x) { // 使用 lower_bound 进行二分查找 return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; } // 查询离散化后索引对应的原始值 (1-based index) int original(int idx) { return alls[idx - 1]; // 因为 get 返回的是 1-based } // 获取离散化后值域的大小 int size() { return alls.size(); } }; // 使用示例 int main() { Discretizer d; // 假设有一些数据 vectorint data {1000000000, 1, -1000000000, 1, 500, 500}; // 1. 添加所有值 for (int x : data) { d.add(x); } // 2. 预处理 d.prepare(); // 此时 alls 为 [-1000000000, 1, 500, 1000000000] // 3. 查询离散化索引 cout d.get(-1000000000) endl; // 输出 1 cout d.get(1) endl; // 输出 2 cout d.get(500) endl; // 输出 3 cout d.get(1000000000) endl; // 输出 4 // 4. 根据索引查原始值 cout d.original(1) endl; // 输出 -1000000000 return 0; }5.2 模板二手写二分查找在一些对性能极其敏感或不允许使用 STL 的场合如某些特殊竞赛环境可以手写二分。int find(int x, vectorint alls) { 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-based index } // 注意使用此函数前必须确保 alls 已排序且包含 x。5.3 模板三离散化结合map进行双向查找如果你需要频繁地根据索引查找原始值除了用alls数组也可以使用unordered_map或map来记录映射关系实现 O(1) 或 O(log n) 的查询。#include vector #include algorithm #include unordered_map using namespace std; class DiscretizerWithMap { private: vectorint alls; unordered_mapint, int val2idx; // 值-索引 unordered_mapint, int idx2val; // 索引-值 (如果需要) public: void add(int x) { alls.push_back(x); } void prepare() { sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 构建映射表 for (int i 0; i alls.size(); i) { val2idx[alls[i]] i 1; // 1-based // idx2val[i 1] alls[i]; } } int get(int x) { // 直接查表比二分更快但需要额外空间 return val2idx[x]; } int original(int idx) { return alls[idx - 1]; // 或者 return idx2val[idx]; } };选择建议在算法竞赛中模板一vectorlower_bound因其简洁、高效、内存友好是绝对的主流选择。map版本在需要极高频双向查找且内存不敏感时可以考虑。6. 进阶应用离散化与树状数组结合离散化真正发挥威力的地方是与树状数组、线段树等高级数据结构结合解决“动态区间问题”。一个经典问题是逆序对统计但这里我们看一个更通用的“区间更新、单点查询”或“单点更新、区间查询”问题。问题数轴上有若干线段每条线段覆盖一个区间[l, r]。有多次查询每次问某个点x被多少条线段覆盖。如果坐标范围很大就需要离散化。思路将所有的l,r,x加入alls进行离散化。离散化后每条线段覆盖的区间[L, R]对应到紧凑的整数区间。问题转化为在一个较小的数组上进行多次区间加1线段覆盖然后进行多次单点查询问某个点被覆盖几次。这正好是树状数组或差分数组的经典应用场景。代码示例差分数组法离散化后#include iostream #include vector #include algorithm using namespace std; const int N 200010; // 最多 n 条线段m 次查询最多 2nm 个点 int diff[N]; // 差分数组 vectorint alls; int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() 1; } int main() { int n, m; cin n m; vectorpairint, int segs(n); vectorint queries(m); // 读入线段和查询点 for (int i 0; i n; i) { cin segs[i].first segs[i].second; alls.push_back(segs[i].first); alls.push_back(segs[i].second); } for (int i 0; i m; i) { cin queries[i]; alls.push_back(queries[i]); } // 离散化 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 在离散化后的坐标上使用差分数组处理区间加 for (auto seg : segs) { int L find(seg.first); int R find(seg.second); diff[L] 1; diff[R 1] - 1; // 注意这里是离散化后的R线段覆盖是闭区间[l, r] } // 计算前缀和得到每个点的覆盖次数 vectorint cover(alls.size() 2, 0); for (int i 1; i alls.size(); i) { cover[i] cover[i - 1] diff[i]; } // 回答查询 for (int x : queries) { int idx find(x); cout cover[idx] endl; } return 0; }这个例子清晰地展示了离散化如何将一个大值域的几何问题转化为一个小数组上的差分/前缀和问题。7. 常见问题、陷阱与排查指南离散化思路清晰但实现时细节决定成败。下表总结了最常见的“坑”问题现象可能原因排查方式解决方案运行时错误如数组越界find函数返回的索引超出了alls数组的范围。检查find函数逻辑特别是二分查找的边界条件。确认查询的值x一定在alls中。1. 确保alls包含了所有需要查询的值。2. 二分查找使用lower_bound时确保容器已排序。3. 如果查询值可能不在alls中需要特别处理返回-1或插入。答案错误逻辑混乱忘记对alls进行去重。在sort后打印alls的大小和内容检查是否有重复元素。务必在排序后调用alls.erase(unique(alls.begin(), alls.end()), alls.end());答案错误映射不一致离散化前后使用了不同的映射关系。例如加法用了一套alls查询用了另一套。确保整个程序只维护一个alls向量所有数据的映射都基于它。将所有需要离散化的点操作点、查询点一次性加入同一个alls然后统一预处理。性能不佳在循环中多次调用sort和unique。检查代码确保prepare()或排序去重操作只执行了一次在所有数据添加完毕之后。将添加数据和预处理分成两个清晰的阶段。处理区间时出错离散化后区间的性质可能改变。例如原区间[l, r]离散化后[L, R]可能不再是连续覆盖。思考离散化是否适用于当前问题。对于“区间覆盖点数”类问题离散化是安全的。对于“区间长度”类问题可能需要将点转化为段。理解问题本质。对于涉及“连续区间内点的个数”的问题离散化直接可用。对于涉及“连续区间长度”的问题可能需要将每个点视为一个单位长度段的左端点。查询值不在alls中题目可能询问一个从未出现过的坐标的值。仔细读题。如果查询值可能不存在lower_bound会返回第一个大于等于它的位置这可能不是你想要的行为。根据题意处理1. 若查询值不存在则忽略或输出0需判断alls[pos] x。2. 若需要动态插入则考虑使用map或平衡树而非一次性离散化。一个重要的边界情况当处理区间操作时如果题目中的区间是闭区间[l, r]且操作是影响区间内的点那么离散化l和r通常就足够了。但如果操作是影响以点为边界的段可能需要将r1也加入离散化集合。这需要根据具体问题逻辑分析。8. 最佳实践与工程建议将离散化从竞赛技巧转化为可靠的工程代码需要注意以下几点封装与复用如模板所示将离散化逻辑封装成一个类 (Discretizer)。这提高了代码的清晰度和复用性避免了全局变量alls的滥用。索引基准选择通常使用1-based索引。这有两个好处一是与许多数据结构如树状数组、前缀和数组的惯例保持一致s[0] 0作为哨兵二是避免“下标-1”的思维转换减少错误。在find函数中返回index 1即可。lower_boundvsupper_bound绝大多数情况下使用lower_bound找到第一个大于等于x的位置。因为我们的alls包含x所以找到的就是x的确切位置。只有在处理一些特殊边界如找最后一个小于等于x的位置时才考虑upper_bound并减一。空间预估在竞赛中根据题目给出的n和m上限预估alls的最大大小并提前分配空间如vector::reserve可以避免不必要的动态扩容开销。例如n次操作和m次查询最多可能有n 2*m个点。与 STL 的协同C STL 的sort,unique,lower_bound在随机访问迭代器上效率很高足以应对10^5级别的数据。放心使用无需手写除非有特殊限制。调试输出在复杂问题中离散化后打印出alls数组和关键的映射关系如x - idx是验证逻辑是否正确的最快方法。9. 总结与扩展方向离散化不是一个算法而是一种思想一种在“无限”中处理“有限”的桥梁思想。它通过建立映射让那些依赖连续、紧凑下标的数据结构和算法数组、前缀和、树状数组、线段树得以在稀疏、大值域的数据上大展拳脚。掌握本文的模板和思路你就能解决 LeetCode、AcWing、Codeforces 等平台上绝大多数需要离散化的问题。例如LeetCode 315. 计算右侧小于当前元素的个数需要离散化数组值然后使用树状数组从右向左统计。LeetCode 699. 掉落的方块方块在 x 轴上的位置范围可能很大但方块数量有限离散化 x 坐标后可以用线段树维护每个区间的高度。区间染色、区间最大覆盖次数等问题。下一步深入学习的方向离散化 扫描线解决二维平面上的矩形面积、矩形周长等问题。将 y 坐标离散化用线段树维护 x 轴扫描过程中的状态。动态离散化如果数据流式输入无法预先知道所有值可以考虑使用std::map或std::unordered_map来维护动态的映射关系但会牺牲一些性能和简洁性。离散化与哈希的权衡当值域极大但数据量不大时离散化是首选。如果数据量也很小或者需要保留原始值的映射关系用于输出使用map也是不错的选择。但在追求极致性能的竞赛中离散化数组二分查找通常优于map。最后记住离散化的核心口诀“值域大个数少先收集再排序务必去重二分映射”。把本文的模板收藏下来下次遇到需要“压缩空间”的题目时它就是你的标准解决方案。