离散化

  • 离散化

    1、对于元素个数不多、值域很大的有序无重复数列，且更关注数列的相对大小(而不是绝对大小)，可以使用离散化的方式优化程序。离散化本质上是一种哈希，即把一个数字映射为另一个数字
    2、例如对于一个长 100 的有序无重复数列{1, 5, 20, ..., 10^18}(元素最大值为 1018)，只判断相对大小关系，可将其映射为{0, 1, 2, ..., 99}，便可以代表所需要的相对大小信息
    3、离散化通常可以将大数组的零散数据映射到小数组中。例如存储一条 109 的数轴上的点的值，但却只有较少数据量的一些零散数据，如{[0]:3, [4]:7, [11]:4, [10000]:21}，如果开辟 109 的数组不仅会爆栈还浪费大量空间。如果使用时只关注下标的相对大小，最好的办法是将有数据的点按照下标离散化为{[0]:3, [1]:7, [2]:4, [3]:21}，这样便存储到了小数组中

  • 代码实现

    1、通常读入的数组不是有序无重复的，因此我们需要先进行排序和去重。排序可以直接使用sort，去重通常使用unique配合erase实现(此外也给出了数组的实现方式)。然后，我们需要算出离散化后的值，通常使用二分查找的方式实现
    2、如下例，单独给出了去重和二分的框架。且在下面附上完整程序的一个示例

    /* 去重 - vector */
vector<int> vec = {1, 13, 2, 5, 10000, 2, 13}; // 使用 vector 保存原始数据
sort(vec.begin(), vec.end());                  // 使用 sort 排序
// unique 函数返回一个迭代器，指向不重复序列的尾后位置(即被排到末尾的重复元素的首元素位置)
// erase 从重复元素首元素，删除到末尾，删除掉所有重复元素
vec.erase(unique(vec.begin(), vec.end()), vec.end());

/* 去重 - 数组 */
int n = 7;                                     // 实际数组长度
int arr[100001] = {1, 13, 2, 5, 10000, 2, 13}; // 使用数组保存原始数据
sort(arr, arr + n);                            // 使用 sort 排序
// 使用 unique 返回的位置，减去首元素位置，得到不重复数列的长度
// 后面程序使用数组，只需要使用 arr[0] 到 arr[len] 即可，后面部分是重复元素
int len = unique(arr, arr + n) - arr;

/* 二分 - 查找当前数字在数组中的位置(查找映射值) */
// 也可以直接使用 lower_bound
// 原始数据的 vector 或 数组 是全局变量
int binary_search(int L, int R, int key)
{
    int mid;
    // 这种二分写法需要范围略大一些
    L--;
    R++;

    while (L + 1 != R)
    {
        mid = (R + L) / 2;
        if (vec[mid] < key)
            L = mid;
        else
            R = mid;
    }

    return R;
}
    #include <bits/stdc++.h>
using namespace std;

vector<int> vec, res; // vec 为原数列，res 为离散化后的数列

// 使用二分查找，查找离散化后的位置
int binary_search(int L, int R, int key)
{
    int mid;
    L--;
    R++;
    while (L + 1 != R)
    {
        mid = (R + L) / 2;
        if (vec[mid] < key)
            L = mid;
        else
            R = mid;
    }
    return R;
}

int main()
{
    int n, num;
    cin >> n;
    while (n--)
    {
        cin >> num;
        vec.push_back(num); // 输入 vec 原数列
    }

    // vec 排序去重
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    int value;
    for (int key : vec)
    {
        value = binary_search(0, vec.size() - 1, key); // 查找离散化后的值
        res.push_back(value);                          // 存入结果
    }

    // 输出映射的结果
    for (int i = 0; i < res.size(); i++)
        cout << vec[i] << ' ' << res[i] << endl;
    return 0;
}

例-数轴求和

  • 数轴求和

    1、数轴求和：假设有一条长度不超过 109 的数轴(默认值为 0)，程序首先输入两个参数：n(要添加的点的个数)、q(要询问的次数)。接下来 n 行，每行输入 i 和 x，表示数轴上 i 处的值加上 q；接下来 m 行，每行输入 l 和 r，表示询问区间[l, r]的区间和，并输出答案
    2、明显，我们需要关心的有数据的点并不多，不需要开辟巨大的数组(即使开辟也会爆栈)，可以使用离散化优化。一共有两大组数据：数轴点和值以及询问区间。我们可以将所有的点记录到一起，按照所有的点的相对大小位置(作为离散化的总的目录)来离散化处理，再分别按照两组数据对应的点离散化的结果，将数据按照离散化的下标转存，代码如下

  • 代码实现

    #include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> info;  // 存储数轴点和值
vector<pair<int, int>> query; // 存储查询区间
vector<int> all_point;        // 存储数轴点和区间点，即所有要离散化的点

// 查询 key 在所有点中的相对大小位置，离散化处理
int binary_search(int L, int R, int key)
{
    int mid;
    L--;
    R++;
    while (L + 1 != R)
    {
        mid = (L + R) / 2;
        if (all_point[mid] < key)
            L = mid;
        else
            R = mid;
    }
    return R;
}

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

    int p, q;
    // 读入数轴点和值
    for (int i = 0; i < n; i++)
    {
        cin >> p >> q;
        info.push_back({p, q});
        all_point.push_back(p);
    }
    // 读入询问区间
    for (int i = 0; i < m; i++)
    {
        cin >> p >> q;
        query.push_back({p, q});

        all_point.push_back(p);
        all_point.push_back(q);
    }

    // all_point 排序去重
    sort(all_point.begin(), all_point.end());
    all_point.erase(unique(all_point.begin(), all_point.end()), all_point.end());

    // 先离散化 info
    int arr[1000001]; // 记录 info 离散化处理后的结果
    for (auto item : info)
    {
        int x = binary_search(0, all_point.size() - 1, item.first); // 计算坐标离散化后的坐标
        arr[x] += item.second; // 将离散化后的数据存储到新数组，下标变成了离散化的下标
    }

    // 计算区间和，使用前缀和优化，先预处理前缀和
    int sum[10001] = {};
    sum[0] = arr[0];
    for (int i = 1; i < all_point.size(); i++)
        sum[i] = sum[i - 1] + arr[i];

    // 处理询问
    for (auto item : query)
    {
        // L 和 R 也处理成离散化的坐标
        int L = binary_search(0, all_point.size() - 1, item.first);
        int R = binary_search(0, all_point.size() - 1, item.second);

        // 计算前缀和，输出答案
        if (L == 0)
        {
            cout << sum[R] << endl;
            continue;
        }
        cout << sum[R] - sum[L - 1] << endl;
    }
    return 0;
}

页底评论