09-进阶算法/05-离散化

离散化

离散化将很大但数量很少的值映射到较小的连续整数，常用于权值数组、线段树等场景。

基本方法

vector<int> a = {100, 99999, 5, 100, 5}; // 原始数据
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end()); // 去重

// 查询 x 离散化后的值（0-indexed）
auto get_id = [&](int x) -> int
{
    return lower_bound(b.begin(), b.end(), x) - b.begin();
};

// a 离散化后: {1, 2, 0, 1, 0}

手动离散化模板

struct Discrete
{
    int n;
    vector<int> val;
    Discrete(const vector<int>& a)
    {
        val = a;
        sort(val.begin(), val.end());
        val.erase(unique(val.begin(), val.end()), val.end());
        n = val.size() - 1; // 1-indexed
    }

    // 查询 x 的排名（1-indexed）
    int id(int x)
    {
        return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
    }

    // 恢复原始值
    int val_of(int id)
    {
        return val[id - 1];
    }
};

应用场景

• 权值线段树 / 树状数组（值域很大时先离散化）
• 扫描线算法
• 区间覆盖问题