本篇博客详细讲解一下离散化知识点，通过讲解和详细列题带大家掌握离散化。
题目：
原题链接：https://www.acwing.com/problem/content/description/804/
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
− 1 0 9 ≤ x ≤ 1 0 9 -10^9≤x≤10^9 −109≤x≤109,
1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105,
− 1 0 9 ≤ l ≤ r ≤ 1 0 9 −10^9≤l≤r≤10^9 −109≤l≤r≤109,
− 10000 ≤ c ≤ 10000 −10000≤c≤10000 −10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
什么是离散化？
本题猛的一看似乎就是一道前缀和的模板题，但需要注意到这里所谓的“坐标”的范围较大，范围在 − 1 0 9 ≤ x ≤ 1 0 9 -10^9≤x≤10^9 −109≤x≤109,为了存下被修改的点的数据，如果将它们的坐标作为数组的下标就需要开一个 2 ∗ 1 0 9 2*10^9 2∗109大小的数组，肯定会爆内存，况且这里的坐标还有负值，不方便进行存储。
所以要提出一个新的能方便快捷存数据的算法——离散化。
离散化的内存优化思路是只存储那些被用到的点（在这里指的是“被加了值的点”以及“要查询区间的两个端点”），然后利用一些较小的值来代替它们的坐标进行索引，并最终保持它们的相对位置。
举个例子：对于“被用到的点”只有四个：1、11、886、320001，如果用传统的存储方式要开1～320001个连续的存储空间，但其实没必要，因为会浪费掉了很多没有用到的空间。其实它们的相对位置可以分别用1（1）、2（11）、3（886）、4（320001）来替代，进而只需要开1～4个连续的存储空间并且全部用上；反观此题的数据量，操作次数决定要存点的个数，n、m均小于等于 1 0 5 10^5 105，所以“被用到的点”最多为 n + 2 m = 3 ∗ 1 0 5 n + 2m =3 *10^5 n+2m=3∗105个 ，也即内存从 2 ∗ 1 0 9 2 * 10^9 2∗109优化到了 3 ∗ 1 0 5 3 * 10^5 3∗105，整整少了4个数量级！
因此，点的存储位置变为连续，但其表示的值却为离散，故而称其被离散化。
如何离散化？（题解）
为了能够将较大的坐标点及其该坐标点上的数值存储下来，就需要使用两个映射：
- total_num（数组）：用来存放题目中用到的坐标点，也就是题中的x, l, r，初始值为空数组。total_num数组表示坐标到相对位置的映射：先将题目中输入样例给出的坐标点全都放入（append）total_num数组后，进行一遍排序和去重，这样就必能保证小的坐标位置在前，大坐标在后，此时下标就是它们新的“相对位置”。
- a（数组）：用来存放离散化后的坐标的值的变化，初始范围为 3 ∗ 1 0 5 + 10 3 * 10^5 + 10 3∗105+10 (n + 2m 最大为 3 ∗ 1 0 5 3 * 10^5 3∗105)。表示相对位置到坐标点上的数值的映射：拿到坐标点的相对位置new_x后，a[new_x] += c就存下了坐标点的数据了。
这里还需要定义add_num数组用来存放整数(x, c)，定义query_num数组，用来存放询问的区间(l, r)
再定义a的前缀和数组s，预处理完后利用s[r] - s[l - 1]就能得到 [l,r] 区间和了。
下面来详细讲解一下各数组的作用和具体实现方法：
首先初始化各个数组，其中a数组和s数组的长度为 3 ∗ 1 0 5 + 10 3 * 10^5 + 10 3∗105+10，值为0，其余数组初始为空。
total_num数组为何除了要存被改动点的坐标x还要存储查询区间的两端点l和r呢？
主要是因为后续要通过s[r] - s[l - 1]来获取到区间和，而必须将它们在坐标轴上的情况也存下来才能知道这个区间的情况，因而它也算作“被用到的点”。
那么被改动点（x, c）和查询端点（l, r）分别还要再放到add_num和query_num里方便处理。
具体的存储情况还可以下图为例：
这里还有一个难点就是如何进行离散化？也就是如何把total_num数组映射到a数组上？这里需要借用二分来进行插入操作，二分的初始左端点 l 为0，右端点 r 为total_num数组的长度减一，mid = (l+r) // 2，传入参数是x(这里的x是toal_num里的数值，需要对total_num进行遍历并挨个把total_num中的值映射到a数组中)，只要total_num[mid] <= x，那么r = mid 否则 l = mid + 1，最后返回值是 l + 1。
为什么返回的是 l + 1 呢？因为a数组和s数组的下标是从1开始的（下标从1开始是方便处理前缀和），所以这里需要进行+1操作。
下面给出详细代码和注释：
# 读取输入的n和m，分别表示添加操作的数量和查询操作的数量
n, m = map(int, input().split())
N = 300010
a = [0] * N
s = [0] * N
# 用于存储添加操作的列表，每个元素是一个元组，包含要添加的数值x和对应的增量c
add_num = []
# 用于存储查询操作的列表，每个元素是一个元组，包含查询的区间左端点l和右端点r
query_num = []
# 用于存储所有出现过的坐标
total_num = [] # 读取n个添加操作
for i in range(n): x, c = map(int, input().split()) add_num.append((x, c)) total_num.append(x) # 将x添加到total_num中 # 读取m个查询操作
for i in range(m): l, r = map(int, input().split()) query_num.append((l, r)) total_num.append(l) # 将l添加到total_num中 total_num.append(r) # 将r添加到total_num中 # 对total_num进行排序并去重，得到所有唯一出现过的数值
total_num = list(set(sorted(total_num))) # 定义一个查找函数，用于在total_num中找到数值x映射到a的位置（索引从1开始）
def find(x): l = 0 r = len(total_num) - 1 while l < r: mid = (l + r) // 2 if total_num[mid] >= x: r = mid else: l = mid + 1 return l + 1# 对每个添加操作进行处理，将增量c添加到对应的位置
for x, c in add_num: new_x = find(x) # 找到total_num中x映射到a的位置a[new_x] += c # 将增量c添加到a数组的对应位置 # 计算前缀和数组s
for i in range(1, N): s[i] = s[i - 1] + a[i] # 前缀和公式# 对每个查询操作进行处理，计算并输出区间和
for l, r in query_num: xl = find(l) xr = find(r) print(s[xr] - s[xl - 1])
