离散化（超详细）

离散化

有这么种情况，当整数范围很大，比如大到1e9，而数据范围很小，只有1e5甚至更小，我们若是想经常查询或者修改这些整数的位置，显而易见哈希就是很好的方法，但是由于整数太大，没有那么多数组将其存下，此时我们就可以用离散化的方法来解决

离散化：离散化的本质是建立了一段数列到自然数之间的映射关系（value -> index)，通过建立新索引，来缩小目标区间，使得可以进行一系列连续数组可以进行的操作比如二分，前缀和等…

上面是y总给出的定义，可能有点抽象，简而言之就是

使用一个新的数组，这个新数组的值是原序列的下标，利用这个关系，建立起新数组的下标与原序列的关系，桥梁就是 新数组的值 == 原序列的下标

注意，原序列的下标是离散的，不是相邻的

还是有点抽象，可以举个例子

原序列前5个数的下标和值是 arr[0] = 1 ,arr[10] = 20 arr[200] = 300 arr[3000] = 5000 arr[40000] = 10000

新数组alls [0] = 0,alls[1] = 10,alls[2] = 200,alls[3] = 3000,alls[4] = 40000

注意观察橙色的数字，我们会发现，arr的下标就是alls数组的

这样我们就可以得到一个关系，arr [ alls[0] ] = 1, arr[ alls[ 1] ] = 20,arr[ alls [ 2]] = 300 , arr[ alls [3]] = 5000,arr[ alls[ 4]] = 10000;

这样是不是就变得很简单， 很清晰了

没错，离散化就是这样一种很简单的坐标映射

ps : 实际上我们在处理arr的数据时，是不开arr这个数组，而是直接把arr的下标存入alls中，毕竟arr也没法开那么大

有了以上的概念，那我们就可以开始写代码了

代码分为五大块，我会一一解读

这是例题链接：802. 区间和 - AcWing题库

本题综合了二分与前缀和，是个很好的模板题

1 存入离散化下标

在这一步，我们将要把所有的用到的arr下标存入alls数组当中

或许有的人会问，为什么 l 和 r 也要存进去啊

因为l和r可能也是很大的那种数字，比如1e9，并且l和r对应的其实是原序列的下标，而我们访问的其实是alls的数组，所以要将其与alls映射所以我们也需要将其离散化

又有人也行会问了，那离散l和r后，怎么保证求前缀和操作时的正确性，不会出现区间乱了的问题吗。

这个就问的很好了，当初我也是思考了很久

后来我恍然想到

原序列 l 和 r 中间的下标 一定是l

这就很好的解决了疑问

  for(int i=1;i<=n;i++){ //离散化增加值区间
     
       std::cin>>x>>c;//将x位置处加上c
       add.push_back({x,c});//保存一下下标和值
        alls.push_back(x);//将下标读入离散数组，开始映射
    }
    
    for(int i=1;i<=m;i++){  //离散化查询区间
        
        std::cin>>l>>r;//输出l到r区间的值
        query.push_back({l,r});
        alls.push_back(l);//将两个下标存入离散下标数组
        alls.push_back(r);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2 排序去重

为什么一定要排序去重呢

排序是为了方便我们使用二分排序

去重是因为假设，我们 在修改时曾经用到过下标100，后来查询时又用到了下标 100，那么alls里面就会有两个100，那么alls会有两个下标映射这个值，也就是100这个值，这显然是不合理的，因为alls与原序列也是一一映射关系，只有确保唯一性，才能保证正确性

// 2 排序去重
     sort(alls.begin(),alls.end());
     alls.erase(unique(alls.begin(),alls.end()),alls.end());
1
2
3

3 插入操作

使用alls的下标映射新的数组，相信大家到这应该已经能理解了

for(auto item:add){
        int x = find(item.first); //将这个下标在alls数组中找到，使用alls的下标作为下标
        sum[x]+=item.second;
    }
1
2
3
4

4 前缀和

    for(int i=1;i<=alls.size();i++)sum[i] +=sum[i-1];
1

5 查询

 for(auto item:query){
        int l = find(item.first);
        int r  =find(item.second);
        std::cout<<sum[r]-sum[l-1]<<std::endl;
    }
1
2
3
4
5

6 完整代码

#include
#include
#include

typedef std::pair<int,int>PLL;
int n,m;//n次询问，m次查询
int x,c;//在x加上 c
int l,r;//输出区间值
std::vector<int>alls;//所有的下标放的位置
std::vector<PLL>add;//插入修改值
std::vector<PLL>query;//查询操作
int sum[3000000];//离散化后的数组，变成前缀和数组

int find(int x){
    int l = -1,r = alls.size();
    int mid = l+r>>1;
    while(l+1<r){
        if(alls[mid]>=x)r=mid;
        else l = mid;
        mid = l+r>>1;
    }
    return l+1;
}
int main(){
    std:: cin>>n>>m;
    
    // 1 第一步 离散化下标
    for(int i=1;i<=n;i++){ //离散化插入区间
     
       std::cin>>x>>c;
       add.push_back({x,c});
        alls.push_back(x);
    }
    
    for(int i=1;i<=m;i++){  //离散化查询区间
        
        std::cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    
  // 2 排序去重
     sort(alls.begin(),alls.end());
     alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    // 3 插入操作
    for(auto item:add){
        int x = find(item.first); //将这个下标在alls数组中找到，使用alls的下标作为下标
        sum[x]+=item.second;
    }
    
    // 4 前缀和
    for(int i=1;i<=alls.size();i++)sum[i] +=sum[i-1];
    
    // 5 查询
    for(auto item:query){
        int l = find(item.first);
        int r  =find(item.second);
        std::cout<<sum[r]-sum[l-1]<<std::endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64