准备春招，算法题冲冲冲！

假设有一个数据之间 差值过大 的 整数 数组，我们想把它当成数组下标来用，会发现很多空间被浪费了（如a[1001] ~ a[100001]根本用不到）、可能容量不够（如a[1e9]）。

针对这种情况，我们能把这些数 映射 成范围为0 ~ n-1的数，方便做题。而这就是 离散化 思想。

离散化

离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的 全/偏序 关系。

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化。

用来离散化的可以是大整数、浮点数、字符串等等。

思路

接下来看看如何给整数序列做离散化操作。

首先，序列中可能存在重复元素，需要 去重：

// 先排序
vector<int> a;
sort(a.begin(), a.end());
// 再去重
a.erase(unique(a.begin(), a.end()), a.end());

然后就要想法儿对这些元素进行映射了，可以用 二分 来做：

// 映射算法: {1000, 1000001} -> {0, 1}
int mapping(int x)
{
    int l = -1, r = a.size();
    while (l + 1 < r)
    {
        int mid = l + (r - l) / 2;
        if (a.at(mid) >= x)
            r = mid;
        else
            l = mid;
	}
    return r;
}

最终得到的映射序列就是离散化后的结果。

例题

802. 区间和 - AcWing题库

这道题要操作的数据范围大，而且稀疏，刚好适合用离散化来做。可以将要操作的整数进行离散化。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 获取离散化后x在nums数组的位置, 1起点要+1
int mapping(int x, const vector<int> &nums)
{
    int l = -1, r = nums.size();
    while (l + 1 < r)
    {
        int mid = l + (r - l) / 2;
        if (nums.at(mid) >= x)
            r = mid;
        else
            l = mid;
    }
    return r + 1;
}

int main()
{
    int n, m;
    cin >> n >> m;

    // 存储操作数
    vector<pair<int, int>> opAdd, opQuery;
    opAdd.reserve(n);
    opQuery.reserve(m);
    // 存储离散化数组
    vector<int> nums;
    nums.reserve(n + 2 * m + 10);
    // 将操作数录入离散化数组
    int opA, opB;
    for (int i = 0; i < n; ++i)
    {
        cin >> opA >> opB;
        opAdd.emplace_back(opA, opB);
        nums.emplace_back(opA);
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> opA >> opB;
        opQuery.emplace_back(opA, opB);
        nums.emplace_back(opA);
        nums.emplace_back(opB);
    }

    // 离散化nums
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    // 离散化后要操作的数组
    vector<int> ans(nums.size() + 10, 0);

    // 进行加法和除法操作
    for (auto [pos, num] : opAdd)
    {
        pos = mapping(pos, nums);
        ans.at(pos) += num;
    }

    // 求前缀和
    for (int i = 1; i < ans.size(); ++i)
    {
        ans.at(i) = ans.at(i - 1) + ans.at(i);
    }

    // 询问前缀和
    for (auto [l, r] : opQuery)
    {
        l = mapping(l, nums);
        r = mapping(r, nums);
        cout << ans.at(r) - ans.at(l - 1) << '\n';
    }
}

参考资料

• 算法基础课 - AcWing
• 离散化 - OI Wiki (oi-wiki.org)