离散化

What · 是什么

离散化(Discretization)是一种将大值域数据映射到紧凑连续排名的技巧：将原始值排序去重后，用每个值在有序序列中的位置(排名)代替原始值。映射后保持偏序关系(x<y ⟺ rank(x)<rank(y))，但值域从 10^9 压缩到 n 级别，使得数组下标可用。

Why · 为什么

How · 实现

伪代码

# 方法一: 同值同排名(常用)
tmp = sorted(set(arr))  # 排序+去重
for i in range(n):
  arr[i] = lower_bound(tmp, arr[i])  # 查排名

# 方法二: 同值不同排名(按出现顺序)
pairs = [(arr[i], i) for i in range(n)]
pairs.sort(key=lambda x: (x[0], x[1]))  # 值相同时按原始位置
for rank, (val, idx) in enumerate(pairs):
  arr[idx] = rank  # 排名从0或1开始

Python 实现

import bisect


def discretize_same(arr):
    """离散化方法一: 相同的值离散化为相同的排名。
    返回离散化后的数组(1-indexed排名)。
    保持偏序: x < y => rank(x) < rank(y)
    """
    tmp = sorted(set(arr))  # 排序+去重
    return [bisect.bisect_left(tmp, v) + 1 for v in arr]  # 1-indexed


def discretize_unique(arr):
    """离散化方法二: 相同的值按出现顺序离散化为不同排名。
    用于需要区分相同值不同位置的场合。
    """
    n = len(arr)
    pairs = [(arr[i], i) for i in range(n)]
    pairs.sort(key=lambda x: (x[0], x[1]))
    result = [0] * n
    for rank, (val, idx) in enumerate(pairs):
        result[idx] = rank + 1  # 1-indexed
    return result


def discretize_with_query(arr):
    """离散化并返回: 离散数组 + 查询函数(原值->排名)。
    便于后续多次查询。
    """
    tmp = sorted(set(arr))
    disc = [bisect.bisect_left(tmp, v) + 1 for v in arr]

    def query(val):
        """原值 -> 排名(1-indexed), 不存在返回插入位置。"""
        return bisect.bisect_left(tmp, val) + 1

    return disc, query, tmp  # tmp为去重有序数组


if __name__ == '__main__':
    # 测试方法一: 同值同排名
    arr1 = [1000, 500, 500, 2000, 1000]
    disc1 = discretize_same(arr1)
    print(f'Original: {arr1}')
    print(f'Discretized (same): {disc1}')  # [2, 1, 1, 3, 2]
    assert disc1 == [2, 1, 1, 3, 2]
    assert all(1 <= x <= 3 for x in disc1)  # 值域压缩到 [1,3]

    # 测试偏序保持
    arr2 = [300, 100, 200]
    disc2 = discretize_same(arr2)
    assert disc2 == [3, 1, 2]  # 100<200<300 => 1<2<3

    # 测试方法二: 同值不同排名
    arr3 = [100, 100, 50, 200]
    disc3 = discretize_unique(arr3)
    print(f'Discretized (unique): {disc3}')  # 50->1, 100(first)->2, 100(second)->3, 200->4
    assert disc3 == [2, 3, 1, 4]

    # 测试带查询函数
    arr4 = [10, 20, 10, 30]
    disc4, query, tmp = discretize_with_query(arr4)
    print(f'Discretized: {disc4}')  # [1, 2, 1, 3]
    print(f'Query 20: {query(20)}')  # 2
    print(f'Query 25: {query(25)}')  # 3 (插入位置)
    assert disc4 == [1, 2, 1, 3]
    assert query(20) == 2

    print('All discretization tests passed!')

易错点

• 忘记去重: set() 或 unique() 必须执行, 否则排名不连续(有空洞)
• lower_bound 返回的是 0-indexed 位置, 树状数组需要 1-indexed → 需 +1
• 方法一和方法二选择错误: 需区分相同值时用方法二, 否则用方法一
• 离散化后值域 [1,n] 但 n 可能仍大, 线段树仍需动态开点或离散化后值域分析

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/discrete/
• Wikipedia✓ https://en.wikipedia.org/wiki/Transitive_reduction