离散化

离散化(discrete)，就是当我们只关心数据的相对大小关系时，用排名代替原数据进行处理的一种预处理方法。

离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。

当原数据很大或含有负数、小数时，难以表示为数组下标，一些算法和数据结构（如BIT）无法运作，这时我们就可以考虑将其离散化。

离散化+二分查询

离散化的排序可以用二分来实现。

vector<int> arr;	  // 待离散数组
vector<int> dsc;	  // 离散后数组

// 离散化
void discrete() {
    dsc = arr;
    sort(dsc.begin(), dsc.end());
    dsc.erase(unique(dsc.begin(), dsc.end()), dsc.end());
    /*
    // 代替unique的做法
    dsc = arr;
    sort(dsc.begin(), dsc.end());
    int j = 0;
    for (int i = 0; i < dsc.size(); i ++) {
        if (!i || dsc[i] != dsc[i - 1]) {
            dsc[++ j] = dsc[i];
        }
    }
    dsc.erase(dsc.begin() + j, dic.end());
    */
}

// 二分查询
int query (int x){
    int idx = lower_bound(dsc.begin(), dsc.end(), x) - dsc.begin(); // 下标从1开始
    // int idx = upper_bound(dsc.begin(), dsc.end(), x) - dsc.begin(); // 下标从0开始
}

查询是$O(\log n)$的

离散化+哈希查询

查询是$O(1)$的

vector<int> arr;			    // 待离散数组
unordered_map<int, int> dsc;    // hash表

// 离散
void discrete() {
    int idx = 0;
    for (int i = 0 ; i < arr,size(); i ++) {
        if (!dsc.count[arr[i]]) {
            dsc[arr[i]] = ++idx;
        }
    }
}

// hash查询
int query(int x) {
    return dsc[x];
}

练习eg:

LeetCode-1331. 数组序号转换

Acwing-121.赶牛入圈

---

离散化+树状数组

练习eg:

LeetCode-327. 区间和的个数