离散化

离散化思想

（erase去重）
（离散化二分模板，映射到r + 1 方便求前缀和）
r + 1从1开始映射
将每个数映射到下标，方便用二分。
个人认为这种思想与其叫离散化，不如叫坐标映射。

离散化实例

离散化用于本身数据很稀疏的情况，
求对数据进行操作后，某一范围内的和。

Tips

• 注意要对数据和区间同时排序离散化。- 注意给离散化后的数组内存不能开的太小了
• 离散化其实就是先对原数组进行去重，在之后对原数组的操作都可以转化为用二分查找离散后的下标，然后进行操作。
• 这样做的好处在于可以优化求前缀和的复杂度，（在对太稀疏的数组进行操作时太）。
• 由于一开始需要将所有原数组的值和查询区间都保留，然后对这些点排序后，再通过二分寻找下标进行插入和查询，所以需要用pair数组来存所有查询区间和数组元素以及它的值。（用数组下标存值则开的内存过于大了）