离散化（Coordinate Compression）将大范围的值域映射到连续的小范围整数，使得原本无法开数组的数据可以用线段树、树状数组等结构处理。
一、为什么需要离散化？
Mermaid · 渲染中（下方为源码）
graph LR A[大值域坐标] --> B[排序去重] B --> C[映射到 1..n] C --> D[线段树/BIT 可用]
- 值域很大（如坐标 10⁹），但实际出现的值只有 n 个
- 线段树/BIT 需要连续下标
- 只关心相对大小关系，不关心绝对值
二、基本方法
排序 + 二分
// 离散化：将 arr 中的值映射到 [0, m-1]
int[] compress(int[] arr) {
int n = arr.length;
int[] sorted = arr.clone();
Arrays.sort(sorted);
// 去重
int m = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || sorted[i] != sorted[i-1]) {
sorted[m++] = sorted[i];
}
}
// 映射
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = lowerBound(sorted, m, arr[i]);
}
return result; // 值域 [0, m-1]
}
int lowerBound(int[] arr, int n, int target) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}