0x08 离散化
[toc]
1. 什么是离散化
离散就对应着连续，而连续的数据是可以被无线划分的，比如实数和整数，在同一个区间[0, 100]。
那么离散化就是把连续的数据变成离散的数据。对于一些数据来说，虽然是连续的，但是其中其实可能只有有限可分个数据是真正需要的，那么我们就可以把这些数据从连续的数据中抽离出来，变成离散的数据，这就是离散化。
举个例子，有个无穷长的数轴，每个点默认值为0，每次对数轴上的一个点加c，总共有n次操作。最终求出来数轴上的某个区间的和。乍一看数轴有无限的点，对于有限空间的计算机是无法求解的，但是对于这个连续区间来说，只有有限个点真正参与到最终的求解中。因此我们就可以将这个连续区间上对于我们需要的值离散化。
2. 如何离散化
对于刚刚的数轴例子来说，数轴每个点的本身的值是带有意义的，因此我们在离散化时不能丢失这个信息。而这个信息是最终用于求和的，因此我们可以把求和的区间左右端点一并离散化，只需要保证离散化后它们仍然保持在数轴中的有序，就不影响最终的求和。
因此先将操作后的每个点和操作的点与值分别存入两个数组，再将需要查询的区间存入数组。对涉及到的点去重再排序，那么这些点就映射为了排序后的数组下标，然后再取出操作的数组，对离散化的数组进行操作。最终就可以求出和。
3. 优化
需要注意的是，离散化的数据是通过数组下标访问的，我们无法直接找到要查询的区间。但是因为这个离散化后的数组是有序的，但我们可以通过二分查找快速找出。
其次，后面的查询操作有多次，每次求子区间的和，我们可以使用前缀和优化时间复杂度。
最终，离散化的时间复杂度为，1. 离散化操作为O(n+m)，其中n+m为涉及到的操作点与查询点的和；2. 构建前缀和，O(n+m)；3. 对于每次查询，找出前缀和的点，O(log n + m)，总共m次查询，共O(m(log(n + m)))。
因此最终的时间复杂度为O(m * log n+m)。