离散化

#algorithm/离散化

什么是离散化

离散化是把无限空间中有限的个体影射到有限的空间去，依此提高算法的效率。

离散化是指将连续的数据转化为离散的数据，通常是将连续的数值分成若干个区间，然后用离散值来代表原始数据。离散化常用于处理数值型数据，特别是连续的数值型数据，因为这类数据通常难以处理，需要将其离散化之后才能使用一些算法。

离散化本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。 通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。 用来离散化的可以是大整数、浮点数、字符串等等。

区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0 现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c 接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和

输入格式

第一行包含两个整数 n 和 m。 接下来 n 行，每行包含两个整数 x 和 c。 再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

\(−109≤x≤109,\) \(1≤n,m≤105,\) \(−109≤l≤r≤109,\) \(−10000≤c≤10000\)

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

解析

从图中可以看出，我们要算出各区间中的和，这个数据比较小可以直接for循环完成求和 但如果数据很大呢？

举个例子

如果数据是只有\(1\)和\(10^9\)这两个位置有值，其他位置都为\(0\)，要求\([1, 10^{9}]\)的和，这时单是\(for\)循环时间复杂度就会达到惊人的\(O(10^{9})\)，这时使用离散化算法就只会用到\(1\)和\(10^{9}\)这两个位置的值，再用前缀和求值，复杂度就会降到\(O(1)\)，所以离散化的目的是就为了降低算法的时间复杂度

Source Code

#include <bits/stdc++.h>
using namespace std;
#define FastIOS ios::sync_with_stdio(false), cout.tie(0), cin.tie(0)
#define int long long
int n, m, i, j, k, t = 0;
const int N = 1e6 + 10;
typedef pair<int, int> PII;
int a[N]; //存储坐标插入的值
int sum[N]; //存储数组a的前缀和
vector<int> alls; //存储（所有与插入和查询有关的）坐标
vector<PII> add, query; //存储插入和询问操作的数据

int find(int x){ //返回的是输入的坐标的离散化下标
    int l = 0, r = alls.size() - 1;
    while(l < r){
        int mid = l + (r - l >> 1);
        if(alls[mid] >= x)
            r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

void solve()
{
    cin >> n >> m;
    for(i = 0; i < n; i++){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }  

    for(i = 0; i < m; i ++){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
  
    sort(alls.begin(), alls.end());
    //去重，返回一个迭代器，指向数组去重后不重复的序列的最后一个元素的下一个元素
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
  
    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
  
    for(i = 1; i <= alls.size(); i++)
        sum[i] = sum[i - 1] + a[i];
  
    for(auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << sum[r] - sum[l - 1] << '\n';
    }
}

signed main()
{
    FastIOS;
    solve();
    return 0;
}
// Thank U

AcWing 802. 画个图辅助理解~ - AcWing