是一种极其特殊的hash方式 必须保序
把无限空间中有限的个体映射到有限的空间中去以提高空间效率

[离散化vector] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> a;//用普通数组也不是不行 操作差不多
sort(a.begin(),a.end()); //将所有元素排序
a.erase(unique(a.begin(),a.end()),a.end()); 
//去重 unique非重复的元素在数组开头  erase返回下标到最后中间的元素 就是去重

int find(int x) //找到第一个大于等于x的位置 当然也可以lower_bound
{
    int l=0,r=a.size()-1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l+1； 储存是从0开始的 加1 元素映射到1到n  不加1就是映射到0到n-1 
}

因为从1开始vector不方便

[离散化普通数组] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lsh[N];
for(int i=1;i<=n;i++) cin>>lsh[i];
sort(lsh + 1 , lsh + n + 1);//排序
cnt = unique(lsh + 1, lsh + n + 1) - lsh - 1;//去重并求出离散化数组大小
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 1, r = cnt;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r; 前面存储是从1开始的 所以这直接return r
}

区间和

[区间和] [c++]
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
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;//操作读入是成对的 定义这么一个结构

const int N=300010;
int n,m;
int a[N],s[N];
vector<int> alls;
vector<PII> add,query; //定义两个PII 一个存操作c 一个存给的l r

int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size()-1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r+1; 本题是映射到从1开始 因为要用到前缀和
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);//待离散化的值
    }
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        query.push_back({l,r}); //注意pair类型插入需要大括号
        alls.push_back(l);
        alls.push_back(r);//将l r存入待离散化数组
    }
    sort(alls.begin(),alls.end());//排序
    alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重

    for(auto ite:add )
    {
        int x=find(ite.first);
        a[x]+=ite.second;//离散化 对应加上c
    }
    
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i]; //预处理前缀和

    for(auto item: query)
    {
        int l=find(item.first);
        int r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }

}