查看“︁09-进阶算法/05-离散化”︁的源代码


== 离散化 ==

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

=== 基本方法 ===

<syntaxhighlight lang="cpp">
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}
</syntaxhighlight>

=== 手动离散化模板 ===

<syntaxhighlight lang="cpp">
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];
    }
};
</syntaxhighlight>

=== 应用场景 ===

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

[[Category:进阶算法]]
[[Category:三三文档]]