坐标压缩是什么？为什么能把大值域数组映射到小下标？
简化版
坐标压缩是把一组很大的、稀疏的值重新映射成连续的小整数下标。它保留大小顺序，方便用数组、树状数组或线段树处理原本值域很大的数据。
详细版
当值域很大但实际出现的值很少时，直接开数组会浪费空间。坐标压缩会收集所有出现的值，排序去重，再用排名作为新下标。
- 原值可能是
10^9级，但实际只有几万个不同值。 - 压缩后下标范围变成
0..m-1。 - 通常保留大小顺序，适合比较、区间统计、排名相关问题。
- 如果要处理区间端点，端点收集要完整，不能漏。
- 坐标压缩改变的是表示方式，不改变原值之间的相对顺序。
完整版教学
一、为什么大值域会让数组失效
数组擅长用下标直接访问，但前提是下标范围可控。如果数据值可能达到 10 亿，而实际只出现 5 个值，直接开长度 10 亿的数组显然不现实。坐标压缩的动机就是：我们不关心值中间那些从未出现的位置，只关心出现过的值之间的顺序关系。把稀疏大坐标变成紧凑小下标后，数组结构又能派上用场。
原值: [1000000000, 7, 500, 7]
出现过的值: [7, 500, 1000000000]
压缩下标: 7->0, 500->1, 1000000000->2记忆钩子：坐标压缩不是改变大小关系，而是给出现过的坐标重新排座位。
二、标准流程是什么
坐标压缩通常三步：收集值、排序去重、建立映射。收集值时要把后续会查询或更新的关键坐标都放进去。排序去重后，第 i 个值映射为下标 i。查询时通过哈希表或二分查找得到压缩下标。这个流程看似简单，但很多 bug 都出在“漏收端点”或“误以为压缩后差值仍然等于原差值”。
const values = [...new Set(nums)].sort((a, b) => a - b);
const rank = new Map();
values.forEach((v, i) => rank.set(v, i));
const compressed = nums.map(v => rank.get(v));三、它保留了什么，又丢失了什么
坐标压缩保留的是相对大小顺序：如果 a < b，那么 rank(a) < rank(b)。但它不保留原始距离：原值 7 和 500 差 493，压缩后可能只差 1。这个区别非常重要。如果题目只关心大小关系、排名、出现位置，压缩很好；如果题目关心真实距离、长度、面积，就不能直接用压缩下标差代替原值差。
| 信息 | 是否保留 |
|---|---|
| 大小顺序 | 保留 |
| 是否相等 | 保留 |
| 原始差值 | 不保留 |
| 原始单位长度 | 不保留 |
四、带数字看空间节省
假设有 10 万个事件坐标，每个坐标最大到 10^9。直接开数组要 10 亿个位置，如果每个位置 4 字节，就是约 4GB 内存；坐标压缩后只需要 10 万个位置，大约 0.4MB。这个数量级差异说明，压缩不是小技巧，而是大值域问题能否使用数组结构的关键。
未压缩：1,000,000,000 × 4B ≈ 4GB
压缩后：100,000 × 4B ≈ 0.4MB五、区间问题为什么要小心端点
如果处理区间 [l, r]，只收集 l 和 r 有时不够，因为区间边界之间的空段也可能有意义。比如计算覆盖长度时，压缩后的相邻下标差不能代表真实长度，必须回到原坐标计算 values[i+1] - values[i]。某些扫描线问题还会收集 r + 1 或右端点的后继位置，用来表达区间结束。端点收集策略要根据题目语义决定。
区间 [10, 1000]
压缩后可能是 [0, 1]
但真实长度不是 1，而是 990 或 991，取决于区间定义六、坐标压缩和哈希映射的区别
哈希映射也能把大 key 映射到小编号，但普通哈希映射不保证顺序。坐标压缩强调排序后的排名，所以适合处理“比某个值小的有多少”“第 k 个坐标在哪”这类问题。可以说，坐标压缩是带顺序语义的离散化映射。只需要判断相等时，哈希表就够；需要比较顺序时，要用排序去重后的压缩。
只查是否出现：HashSet
需要排名/区间/顺序：坐标压缩七、常见误区与追问
- 误区：压缩后下标差等于原始距离。 压缩只保留顺序，不保留真实距离。
- 误区：只收集数组里的值就一定够。 区间问题可能还要收集端点、右端点后继或查询值。
- 误区：坐标压缩会改变比较结果。 它保留相对大小关系，不改变排序顺序。
- 追问：为什么要排序去重？ 排序保证顺序，去重保证相同原值映射到同一下标。
- 追问：查询没出现过的值怎么办？ 根据需求用二分找插入位置、前驱后继，或提前把查询值也加入压缩集合。
八、加强记忆
坐标压缩可以记成“只给出现过的位置编号”。它把大而稀疏的坐标轴折叠成小而连续的下标轴，让数组、树状数组、线段树能工作。答题时一定补上边界：保顺序，不保距离；区间题要谨慎收端点。这样既能讲用途，也能讲清坑点。