什么是离散化？
离散化是将连续的数值范围映射到有限的、离散的数值集合的过程。在许多情况下，数据可能会存在多个重复值或范围较大的连续值。为了简化处理，尤其是处理区间查询和增量问题时，我们可以将这些值转换为一组有限的、唯一的值（即离散值），从而更高效地进行操作。
例如，如果我们有一组数值 {1.1, 1.2, 1.15, 2.5}，在离散化后，我们可能会将其映射为 {1, 2, 3} 这样的索引值，便于后续的操作。
为什么要学离散化？
-
降低时间复杂度：处理连续的数据可能导致算法的时间复杂度急剧增加。通过离散化，我们可以将问题转化为处理较小的离散集，从而大大提高算法的效率。
-
节省空间：在许多应用中，尤其是对于大规模数据，存储每个连续值可能占用大量的空间。离散化有助于减少需要存储的数据量，使得内存使用更加高效。
-
简化问题：离散化能够将复杂的问题分解为基础操作，比如通过离散化后的索引数组，可以更容易地实现前缀和、区间查询等常见算法。
-
易于去重和排序：在进行统计分析时，我们常常需要去除重复的数值或对数据进行排序。离散化可以降低重复数据的复杂度，使这些操作更为简单。
-
灵活应对动态数据：在处理增量更新和查询时，离散化提供了一种高效的方法来动态管理数据，从而能够实时响应用户的请求。
问题描述
假设我们有一系列的增量操作和询问操作。增量操作允许我们在某个点上增加一个值，而询问操作则用于查询某个区间内的总和。为了高效处理这些操作，我们需要进行离散化，避免处理大量的数字，转而处理相对较小的离散值。
代码示例
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* 区间和
*/
public class test1 {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt(); //n次操作
int m = sc.nextInt(); //m次询问
int N = 300010; //因为需要将所有x，l，r存在数组中，这样就是n + 2m <= 300000
int[] a = new int[N]; //从1开始，需要通过x找到离散量，然后+1，
int[] s = new int[N]; //前缀和来做，所以需要从1开始记录a
List<Integer> alls = new ArrayList<>(); //将所有的使用到的数存在alls中，比如x，l，r
//但其中会有先后顺序的差别，以及重复，所以需要排序和去重
List<Pairs> add = new ArrayList<>(); //用来存n次操作
List<Pairs> query = new ArrayList<>(); //用来存m次询问
for (int i = 0; i < n; i++) {
int x = sc.nextInt(); // 读取下一个增量数值
int c = sc.nextInt(); // 读取增量值
add.add(new Pairs(x, c)); // 将增量操作存储到add列表
alls.add(x); // 将x值存储到alls，待后续处理
}
for (int i = 0; i < m; i++) {
int l = sc.nextInt(); // 读取查询的左边界
int r = sc.nextInt(); // 读取查询的右边界
query.add(new Pairs(l, r)); // 存储查询操作到query列表
alls.add(l); // 将左边界l加入alls
alls.add(r); // 将右边界r加入alls
}
//到此为止，alls中存好了所有会被用到的数轴上的点，开始进行离散化处理
Collections.sort(alls);//排序
int unique = unique(alls);//去重
alls = alls.subList(0, unique); //去重后的数值只保留有效部分
for (Pairs item : add) {
int index = find(item.first, alls); // 找到x在离散化数组中的位置
a[index] += item.second; // 更新相应位置的增量值
}
//前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
for (Pairs item : query) {
int l = find(item.first, alls); // 找到查询左边界的位置
int r = find(item.second, alls); // 找到查询右边界的位置
System.out.println(s[r] - s[l - 1]); // 输出区间和
}
}
//去重
static int unique(List<Integer> list) {
int res = 0;
for (int i = 0; i < list.size(); i++) {
if (i == 0 || list.get(i) != list.get(i - 1)) {
list.set(res, list.get(i));
res++;
}
}
return res;
}
//二分
static int find(int x, List<Integer> list) {
int l = 0;
int r = list.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (list.get(mid) >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l + 1; //因为要考虑到前缀和
}
}
class Pairs {
int first;
int second;
public Pairs(int first, int second) {
this.first = first;
this.second = second;
}
}
核心逻辑解释
1. 数据输入
我们首先读取增量操作的次数 n 和询问操作的次数 m。然后，我们定义两个数组 a 和 s，其中 a 用于记录每个离散化值的增量，而 s 用于存储前缀和。
int n = sc.nextInt(); // n次操作
int m = sc.nextInt(); // m次询问
int[] a = new int[N]; // 存储离散化数值对应的增量
int[] s = new int[N]; // 存储前缀和
2. 收集所有数值
我们使用 alls 列表来收集所有在增量和询问过程中出现的数字，方便后续的离散化。将增量操作和查询操作中的数字放入 alls 中。
List<Integer> alls = new ArrayList<>();
3. 离散化处理
对 alls 中的数字进行排序和去重，得到每个数字在离散化后对应的唯一索引。去重的实现通过 unique 方法完成，确保我们只保留有效的数字。
Collections.sort(alls); // 排序
int uniqueCount = unique(alls); // 去重
alls = alls.subList(0, uniqueCount); // 只保留有效部分
4. 更新增量
在确定了离散化对应的索引后，我们遍历 add 列表，更新对应的增量值到数组 a 中。
for (Pairs item : add) {
int index = find(item.first, alls); // 找到离散化的索引
a[index] += item.second; // 更新增量
}
5. 前缀和计算
我们接下来计算前缀和数组 s，以便能快速响应后续的查询请求。
for (int i = 1; i <= alls.size(); i++)
s[i] = s[i - 1] + a[i]; // 构建前缀和
6. 响应查询
最后，我们通过 find 方法找到查询区间的左、右边界在离散化数组中的位置，然后利用前缀和快速计算区间和并输出结果。
for (Pairs item : query) {
int l = find(item.first, alls); // 左边界
int r = find(item.second, alls); // 右边界
System.out.println(s[r] - s[l - 1]); // 输出区间和
}
总结
用离散化的方式有效处理增量操作和区间查询问题。这种方法不仅减少了数据规模，还显著提升了查询效率，是解决类似问题时值得参考的思路。
离散化在处理动态数据时，尤其是区间和、区间更新等问题中，具有非常广泛的应用，能够帮助我们更高效地完成各种统计任务。
希望能为你提供一些启发，下面是代码的图片示例，这样看注释会更清楚一些……
