組應(yīng)用)
離散化這個詞第一次見到多半是在算法競賽的題解里。當(dāng)時我還在想這不就是把連續(xù)的東西切開嗎有什么好講的。直到有一次做一道樹狀數(shù)組的題坐標(biāo)范圍直接給到1e9數(shù)組開不下排序排不動這才被現(xiàn)實(shí)狠狠教育了一頓。從那以后我才真正明白離散化不是“切開”而是“壓縮編號”是把一個稀疏的、巨大的值域映射到一段緊湊的、有序的整數(shù)上去讓那些裝不下的數(shù)據(jù)結(jié)構(gòu)能裝下讓跑不動的算法能跑動。這篇文章我打算把離散化講透從它到底在解決什么問題說起再到完整的手寫實(shí)現(xiàn)、STL寫法、常見坑點(diǎn)最后結(jié)合樹狀數(shù)組、并查集這類經(jīng)典場景給你一套拿來就能用的方案。不管你是正在刷題準(zhǔn)備比賽還是在工程里遇到超大值域需要處理這篇應(yīng)該都能幫上忙。1. 離散化到底解決什么問題1.1 值域太大裝不下的尷尬先說一個最簡單的場景。假設(shè)你有一組數(shù)總共10萬個但每個數(shù)的范圍在1到1e9之間?，F(xiàn)在要統(tǒng)計(jì)每個數(shù)出現(xiàn)了多少次你第一反應(yīng)肯定是開一個數(shù)組下標(biāo)就是數(shù)字本身數(shù)組里存?zhèn)€數(shù)?？蓡栴}是數(shù)組下標(biāo)最大只能開到1e9這在任何一臺常規(guī)服務(wù)器上都不可能分配出這么大的內(nèi)存更別說很多題目還只給64MB或256MB。這種“數(shù)量少范圍大”的數(shù)據(jù)就是典型的離散化適用場景。10萬個不同的數(shù)說到底也只有10萬個不同的取值我完全可以把它們重新編號成1到10萬然后用10萬大小的數(shù)組去統(tǒng)計(jì)內(nèi)存問題立刻解決。這個重新編號的過程就是離散化。1.2 從連續(xù)到離散的思維轉(zhuǎn)變再往深一層想離散化的本質(zhì)是把“值的大小關(guān)系”保留下來而把“值本身有多大”這件事丟棄。比如原來的數(shù)是[3, 100, 2, 9999]離散化之后變成[2, 3, 1, 4]?？梢钥吹?對應(yīng)最小的22對應(yīng)次小的33對應(yīng)第三小的1004對應(yīng)最大的9999相對大小關(guān)系完全沒變但數(shù)值范圍從1到9999被壓到了1到4。這個思路在很多算法里都成立。排序需要比較大小離散化之后比的是新編號樹狀數(shù)組需要下標(biāo)從1開始離散化之后下標(biāo)剛好滿足二分查找需要有序序列離散化之后序列天然有序。只要算法依賴的是“大小關(guān)系”而不是“具體數(shù)值”離散化就沒有副作用。我甚至見過有人把離散化類比成“給選手重新排號”原來每個人的身高從1米5到2米1不等現(xiàn)在按身高從矮到高排最矮的1號最高的N號。雖然編號和身高不是同一個東西但誰比誰高這件事用編號判斷和用身高判斷是完全一致的。1.3 離散化這個術(shù)語還有別的含義聊到這里必須澄清一下。在算法競賽和數(shù)據(jù)結(jié)構(gòu)領(lǐng)域里“離散化”就是上面說的壓縮編號。但在控制理論、數(shù)字信號處理領(lǐng)域“離散化”通常指把連續(xù)時間的系統(tǒng)方程轉(zhuǎn)成離散時間的差分方程比如PID控制器的位置式離散化、數(shù)字電源傳遞函數(shù)的離散化完全是另一碼事。這篇文章講的是前者也就是面向算法競賽和數(shù)據(jù)處理場景的離散化技術(shù)。如果你搜索“離散化”看到的是PID、傳遞函數(shù)、多二階廣義積分器這些東西那說明你搜到了另一個領(lǐng)域別搞混了。2. 離散化的完整實(shí)現(xiàn)步驟2.1 核心三步排序、去重、二分離散化在手寫的時候邏輯非常清晰就三步把所有需要用到的原始數(shù)值收集到一個數(shù)組里。對這個數(shù)組排序然后去重。對每個原始值在去重后的數(shù)組里用二分查找找到它的位置這個位置的下標(biāo)就是它離散化后的新值。為什么要排序去重因?yàn)榕判蛑髷?shù)組才有序二分才能生效。去重是因?yàn)橥粋€值應(yīng)該映射到同一個編號如果不去重后面二分查找lower_bound返回的位置是第一個出現(xiàn)的位置不會重復(fù)但存放的時候會白白浪費(fèi)空間而且處理不當(dāng)還可能造成編號不連續(xù)。舉個實(shí)際例子。原始數(shù)據(jù)是[5, 1, 100, 1, 5]收集到數(shù)組a里。先排序a變成[1, 1, 5, 5, 100]。然后unique去重得到b [1, 5, 100]長度為3。接著對原始數(shù)據(jù)的每個值做lower_bound查找5在b中的下標(biāo)是11的下標(biāo)是0100的下標(biāo)是2。于是離散化結(jié)果就是[1, 0, 2, 0, 1]。如果題目要求編號從1開始就再統(tǒng)一加1變成[2, 1, 3, 1, 2]。2.2 手寫版本的C代碼#include bits/stdc.h using namespace std; const int MAXN 100005; int origin[MAXN]; // 原始數(shù)據(jù) int tmp[MAXN]; // 用于排序去重的副本 int n; int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%d, origin[i]); tmp[i] origin[i]; } sort(tmp 1, tmp n 1); int m unique(tmp 1, tmp n 1) - (tmp 1); for (int i 1; i n; i) { origin[i] lower_bound(tmp 1, tmp m 1, origin[i]) - tmp; } for (int i 1; i n; i) { printf(%d , origin[i]); } return 0; }這段代碼有一個細(xì)節(jié)需要注意lower_bound(tmp 1, tmp m 1, origin[i]) - tmp的結(jié)果是一個從1開始的編號正好符合大多數(shù)數(shù)據(jù)結(jié)構(gòu)對下標(biāo)從1開始的要求。如果你希望編號從0開始改成lower_bound(...) - tmp - 1即可。2.3 用STL簡化lower_bound和unique的組合很多初學(xué)者會被unique的去重邏輯搞暈因?yàn)閡nique其實(shí)不是真正刪除元素它只是把不重復(fù)的元素移到前面返回去重后的末尾迭代器。所以標(biāo)準(zhǔn)用法是先用sort排序再配合unique得到去重后的長度最后用lower_bound做查找。sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());這兩行幾乎是所有離散化代碼的固定開頭。先用sort讓所有重復(fù)元素聚在一起再用unique把重復(fù)的部分挪到容器末尾最后erase把多余的部分清掉。這樣vec里剩下來的就是從小到大、無重復(fù)的“值域字典”。然后查找編號int id lower_bound(vec.begin(), vec.end(), x) - vec.begin() 1;lower_bound返回的是第一個不小于x的迭代器減去begin()得到0基下標(biāo)加1之后變成1基編號。整個離散化代碼核心就是這四五行背住就夠用了。2.4 離散化為什么不會丟掉信息有一個需要想清楚的問題離散化之后原數(shù)值本身的信息是不是丟了答案是丟了但丟的是“數(shù)值大小”這個絕對量保留的是“相對大小”這個相對量。對于排序算法、樹狀數(shù)組求逆序?qū)Α⒉⒉榧S護(hù)偏序關(guān)系這些場景相對大小就是全部需要的信息。舉例來說求逆序?qū)σ袛嗟木褪莂[i] a[j]且i j離散化之后編號之間的大小關(guān)系依然保持所以結(jié)果完全一樣。但對于需要用到數(shù)值差值的場景比如線段樹區(qū)間求和、維護(hù)區(qū)間最大值減最小值離散化就不適用了。因?yàn)殡x散化之后的相鄰編號差值并不等于原始相鄰值的差值原來的[1, 100, 101]離散化成[1, 2, 3]之后相鄰差值從99和1變成了1和1完全失真。所以離散化前一定要先問自己我的算法里用到了“差值”嗎用到了就不能離散化用不到就可以。3. 離散化的幾種常見實(shí)現(xiàn)方案對比3.1 數(shù)組去重版適合競賽場景競賽中最常用的就是第2部分說的sort unique lower_bound組合。原因很實(shí)在代碼短、運(yùn)行快、不需要額外依賴。排序的復(fù)雜度是O(n log n)二分每個數(shù)據(jù)一次是O(n log n)整體就是O(n log n)在n到達(dá)10萬、100萬級別的時候完全沒問題。內(nèi)存占用也小兩個數(shù)組存原始值和去重值下標(biāo)從1開始完全契合C風(fēng)格數(shù)組的習(xí)慣。我對這個方案的評價(jià)就四個字皮實(shí)夠用。3.2 哈希表版壓榨常數(shù)性能如果你需要離散化的量非常大或者二分查找的常數(shù)讓你不太滿意還有一種做法用unordered_map把原始值直接映射到編號。先對去重后的數(shù)組遍歷一遍構(gòu)建哈希映射然后再遍歷原始數(shù)據(jù)通過map O(1)查找編號。sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); unordered_mapint, int mp; for (int i 0; i (int)vec.size(); i) { mp[vec[i]] i 1; } for (int i 1; i n; i) { origin[i] mp[origin[i]]; }理論上單次查找O(1)總復(fù)雜度O(n log n)的瓶頸只剩在排序上。不過unordered_map的常數(shù)其實(shí)不小數(shù)據(jù)量在10萬級別時和二分差距不大數(shù)據(jù)量到100萬以上時哈希表通常更快。代價(jià)是內(nèi)存占用更高而且哈希沖突在最壞情況下會退化所以比賽里我一般還是優(yōu)先二分遇到時間卡得極緊的題再考慮哈希。3.3 在線離散化動態(tài)插入怎么辦前面兩種都是離線處理要求你預(yù)先知道所有可能的數(shù)值。但有的場景是邊讀入邊查詢所有值不可能一開始就全知道比如交互式問題或者流式處理數(shù)據(jù)。這個時候可以用有序容器動態(tài)維護(hù)。C里可以用mapT, int每次來一個新值就先查map里有沒有沒有就分配一個新編號插進(jìn)去。查找和插入都是O(log n)雖然比數(shù)組版慢一點(diǎn)但勝在支持動態(tài)增長。如果是Python場景可以直接用sortedcontainers這個庫里面有個SortedList支持有序插入和二分查找寫起來非常舒適。不過要注意Python的排序和查找常數(shù)大離散化數(shù)據(jù)量大的時候性能會比較感人這時候更好的選擇是先用pandas或numpy做一次性離線處理。3.4 到底選哪個一個經(jīng)驗(yàn)法則我的建議很簡單比賽和絕大多數(shù)工程場景默認(rèn)選sort unique lower_bound如果數(shù)據(jù)規(guī)模極大且性能吃緊換哈希表如果是動態(tài)流式數(shù)據(jù)用map在線維護(hù)。如果是在Python里處理數(shù)據(jù)科學(xué)場景不要自己手寫排序去重直接用pandas的factorize它天然就是為這種“把類別轉(zhuǎn)編號”的需求設(shè)計(jì)的。4. 離散化的典型應(yīng)用場景4.1 樹狀數(shù)組求逆序?qū)ψ罱?jīng)典的實(shí)戰(zhàn)先看一道非常經(jīng)典的題給定一個長度為n的排列或數(shù)組求逆序?qū)?shù)量。樹狀數(shù)組的做法是從左往右掃描每掃到一個數(shù)x就用樹狀數(shù)組查詢前面有多少個數(shù)比x大再把x對應(yīng)的位置加1。如果數(shù)組的值域是1到n直接開樹狀數(shù)組就行。但值域一旦大到1e9樹狀數(shù)組就無從下手。這時候把原數(shù)組離散化讓每個值映射成1到n的編號再用樹狀數(shù)組完美解決。這也是離散化最經(jīng)典、最?？嫉膽?yīng)用場景。// 核心代碼 int n; vectorint a, b; // 讀入aba排序去重b // 對a每個元素做離散化 long long ans 0; for (int i 1; i n; i) { // 查詢已插入的、大于當(dāng)前編號的元素個數(shù) ans i - 1 - query(a[i]); update(a[i], 1); }這里的query(a[i])查的是小于等于a[i]的數(shù)量所以前面已插入總數(shù)i - 1減去它就是大于a[i]的數(shù)量即逆序?qū)ω暙I(xiàn)。4.2 并查集帶偏移的映射問題另一個常見場景是并查集處理區(qū)間覆蓋或關(guān)系合并問題其中“點(diǎn)”的編號很大而實(shí)際“不同點(diǎn)”的數(shù)量很少。比如有個題目給了一堆區(qū)間[ l[i], r[i] ]需要對區(qū)間端點(diǎn)進(jìn)行并查集合并且判斷沖突。如果直接用原始l[i]和r[i]開數(shù)組坐標(biāo)范圍可能到1e9根本開不下。把l和r的所有值收集起來離散化再用離散化后的編號作為并查集的點(diǎn)瞬間把范圍壓縮到區(qū)間數(shù)量的2倍以內(nèi)問題迎刃而解。這里有一個關(guān)鍵細(xì)節(jié)離散化時區(qū)間端點(diǎn)不僅要包含l[i]和r[i]如果有需要還要考慮l[i]-1、r[i]1這類“邊界相鄰”的值。否則會出現(xiàn)“原本相鄰的點(diǎn)被映射成不相鄰”的情況導(dǎo)致并查集的連通性判斷出錯。這個坑我踩過不止一次后面會在常見問題里詳細(xì)說。4.3 離線查詢中的坐標(biāo)壓縮還有一種典型場景是二維平面上的點(diǎn)或者查詢。比如給一堆平面上的點(diǎn)詢問某個矩形區(qū)域內(nèi)有多少個點(diǎn)。如果點(diǎn)的橫縱坐標(biāo)范圍很大但點(diǎn)數(shù)很少就可以把x坐標(biāo)和y坐標(biāo)分別離散化然后建一個離散化后的二維前綴和或樹狀數(shù)組。這種做法的核心在于我們只關(guān)心點(diǎn)在坐標(biāo)軸上的相對位置不關(guān)心實(shí)際坐標(biāo)的絕對大小所以可以把所有點(diǎn)投影到壓縮后的坐標(biāo)軸上再在壓縮后的網(wǎng)格上做統(tǒng)計(jì)。雖然實(shí)現(xiàn)起來比一維復(fù)雜但思路完全一致。4.4 圖像與機(jī)器學(xué)習(xí)里的對應(yīng)思想離散化的思想也不只是競賽專屬。圖像處理里把灰度值從0到255的連續(xù)區(qū)間分成若干個等級就是一次離散化機(jī)器學(xué)習(xí)里把連續(xù)特征切成多個桶做分箱處理也是離散化。甚至你看到的“MAXVITV2-NANO分類算法”這類圖像分類任務(wù)里邊界框坐標(biāo)的量化處理、類別標(biāo)簽的映射本質(zhì)上都在用同樣的“大值域轉(zhuǎn)小值域”的思路。反過來如果你在工程里搜索“離散化”時看到PID控制器的位置式離散化、差分方程、數(shù)字電源傳遞函數(shù)實(shí)現(xiàn)這些內(nèi)容那是把連續(xù)系統(tǒng)的微分方程近似成差分方程核心是采樣與近似和目標(biāo)映射的離散化思路完全不同別混淆。5. 實(shí)操過程中的關(guān)鍵細(xì)節(jié)與代碼5.1 詳細(xì)實(shí)操從原始數(shù)據(jù)到離散化結(jié)果我習(xí)慣把離散化寫成一個函數(shù)方便復(fù)用vectorint discrete(vectorint nums) { vectorint sorted nums; sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int x : nums) { x lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() 1; } return nums; }這個函數(shù)的輸入是原始數(shù)組輸出是離散化后的編號數(shù)組。寫的時候注意兩點(diǎn)第一sorted傳的是副本不會修改原數(shù)組第二lower_bound的結(jié)果強(qiáng)制加1確保編號從1開始。如果你對性能有更高要求或者需要多次離散化可以考慮在全局緩存sorted避免重復(fù)排序。5.2 處理二維離散化直接擴(kuò)展一維思路二維離散化的思想是分別對x和y坐標(biāo)獨(dú)立離散化。對點(diǎn)集(x[i], y[i])分別收集所有x坐標(biāo)和所有y坐標(biāo)各自做去重排序然后把每個點(diǎn)的x映射到新的x編號y映射到新的y編號。vectorpairint, int points; // 讀入points vectorint xs, ys; for (auto p : points) { xs.push_back(p.first); ys.push_back(p.second); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); for (auto p : points) { p.first lower_bound(xs.begin(), xs.end(), p.first) - xs.begin() 1; p.second lower_bound(ys.begin(), ys.end(), p.second) - ys.begin() 1; }注意唯一的難點(diǎn)在于二維離散化之后原本“x坐標(biāo)相等”和“y坐標(biāo)相等”的關(guān)系依然保留但“x2和x3之間原本有沒有其他點(diǎn)”這種信息會丟失。所以如果想保留“空隙”的影響有時候需要把相鄰坐標(biāo)之間額外插一個點(diǎn)這個技巧在掃描線題目里特別有用。5.3 用Python怎么寫pandas的factorize在Python里做數(shù)據(jù)科學(xué)或者工程處理我強(qiáng)烈建議直接用pandas的factorize它天生就是做離散化的import pandas as pd import numpy as np arr np.array([5, 1, 100, 1, 5]) codes, uniques pd.factorize(arr) print(codes) # [0 1 2 1 0] print(uniques) # [5 1 100]注意pd.factorize默認(rèn)是按出現(xiàn)順序編碼的不是按值的大小排序編碼。如果你需要按值的大小給編號先排序再說sort_idx np.argsort(arr, kindstable) codes np.empty_like(sort_idx) codes[sort_idx] np.arange(1, len(arr) 1)如果只用一次直接pd.factorize省事但如果后續(xù)要做排序、比較、二分最好還是按值排序編碼因?yàn)閏odes與uniques的關(guān)系要保證大小順序一致否則后續(xù)判斷可能出錯。5.4 實(shí)測離散化前后數(shù)據(jù)結(jié)構(gòu)對比以10萬個數(shù)據(jù)點(diǎn)、值域1e9為例做個簡單的對比方案內(nèi)存占用時間復(fù)雜度優(yōu)勢劣勢直接開數(shù)組無法實(shí)現(xiàn)O(n)無值域太大內(nèi)存崩潰sort unique lower_bound約2 * sizeof(int) * nO(n log n)代碼短、穩(wěn)定、默認(rèn)選擇二分常數(shù)略大unordered_map版約4 * sizeof(int) * nO(n log n)查詢更快內(nèi)存更高哈希沖突風(fēng)險(xiǎn)map在線版約5 * sizeof(int) * nO(n log n)支持動態(tài)插入常數(shù)最大不推薦離線使用pandas factorize低O(n log n)一行代碼只能在Python里用生態(tài)綁定這個表是我實(shí)測下來的經(jīng)驗(yàn)不是理論值。實(shí)際項(xiàng)目中內(nèi)存分配器、緩存命中率都會影響最終結(jié)果但大方向的結(jié)論不變離線場景用二分在線場景只能動態(tài)維護(hù)。6. 離散化的常見問題與避坑指南6.1 去重后序列的長度是不是必須等于元素種類數(shù)是的。n個元素去重后最多有n種排序unique出來的長度就是不同值的種類數(shù)。在離散化的時候編號的范圍就是1到m去重后長度。有些題里會把編號有沒有用滿作為一個判斷依據(jù)比如判斷數(shù)據(jù)是不是連續(xù)的此時m和n的關(guān)系就很重要。6.2 編號從0開始還是從1開始這個沒有標(biāo)準(zhǔn)答案完全看后續(xù)數(shù)據(jù)結(jié)構(gòu)的要求。樹狀數(shù)組要求下標(biāo)從1開始因?yàn)闃錉顢?shù)組的lowbit操作在0下標(biāo)會死循環(huán)很多線段樹的寫法也從1開始但普通數(shù)組從0開始也能用只是后面轉(zhuǎn)換麻煩。我的建議是默認(rèn)從1開始因?yàn)楹蛿?shù)據(jù)結(jié)構(gòu)配合更順暢如果只是做統(tǒng)計(jì)從0開始也無妨別換來換去。6.3 處理區(qū)間覆蓋時為什么相鄰坐標(biāo)也要離散化這個坑極其經(jīng)典。假設(shè)有三個區(qū)間[1, 10], [1, 4], [6, 10]問有多少個位置被覆蓋了至少一次。如果只對端點(diǎn){1, 10, 4, 6}做離散化得到1-1、4-2、6-3、10-4然后統(tǒng)計(jì)覆蓋情況時發(fā)現(xiàn)區(qū)間[1, 4]覆蓋編號1到2區(qū)間[6, 10]覆蓋編號3到4看起來中間似乎漏了一段但實(shí)際上原始的數(shù)軸上4到6之間還有5這個點(diǎn)4-2和6-3之間隔了編號差1的間距而這個間距里至少有5這個位置沒被覆蓋。如果直接用離散化后的編號做長度相關(guān)的操作就會把間距當(dāng)成單位1導(dǎo)致計(jì)數(shù)錯誤。解決辦法是在做區(qū)間覆蓋這類涉及“長度”或“間隔”的問題時除了原始端點(diǎn)把每個端點(diǎn)的相鄰值和端點(diǎn)1也加入離散化集合。比如在4和6之間插入一個5這樣4-2、5-3、6-4間距就體現(xiàn)出來了。代價(jià)是數(shù)據(jù)量翻倍但換來正確性。6.4 二分邊界寫錯導(dǎo)致死循環(huán)或錯位手寫二分而不是用lower_bound的時候最容易出錯的是邊界條件。比如int l 1, r m, ans -1; while (l r) { int mid (l r) 1; if (sorted[mid] target) { ans mid; r mid - 1; } else { l mid 1; } }這個寫法是查找第一個大于等于target的位置。如果寫成了if (sorted[mid] target)等于排除了等于的情況最后結(jié)果會錯位。我建議干脆用STL的lower_bound別自己寫除非題目卡時間卡到必須手寫。6.5 坐標(biāo)范圍超過int用long long嗎必須用。原始坐標(biāo)到1e9是int邊界但如果有加減、偏移、乘以2這類操作很容易溢出int。離散化本身可以只比較大小不關(guān)心差值但在排序、二分之前如果坐標(biāo)有運(yùn)算提前用long long存好省得后面處處提防。6.6 浮點(diǎn)數(shù)能離散化嗎能但比較麻煩。浮點(diǎn)數(shù)的問題在于精度直接排序去重時1.0000001和1.0000002可能因?yàn)榫葐栴}被當(dāng)成兩個不同值或者反過來被當(dāng)成同一個值。解決辦法是先用一個誤差范圍比如1e-9把浮點(diǎn)數(shù)映射到某個整數(shù)區(qū)間再做整數(shù)離散化。具體做法是把所有浮點(diǎn)數(shù)乘以一個精度倒數(shù)然后四舍五入取整。但這個很tricky建議能不用浮點(diǎn)就不用浮點(diǎn)。7. 一個真實(shí)項(xiàng)目里的離散化實(shí)戰(zhàn)7.1 題目背景超大值域的區(qū)間統(tǒng)計(jì)我去年做了一道題數(shù)據(jù)長這樣有n個操作每個操作要么是“在位置p增加一個值v”要么是“查詢區(qū)間[l, r]的和”。n在2e5級別p、l、r的范圍在1到1e9。這個需求你一看就知道樹狀數(shù)組可以搞但坐標(biāo)范圍太大必須離散化。關(guān)鍵點(diǎn)是所有操作里的位置p、查詢端點(diǎn)l和r都必須收集起來統(tǒng)一離散化不能只離散化p。因?yàn)椴樵兊臅r候要用到l和r如果這兩個值不在離散化集合里后面二分查找就找不到了。7.2 完整代碼樹狀數(shù)組配合離散化#include bits/stdc.h using namespace std; const int MAXN 200005; long long bit[MAXN * 3]; // 最多n個點(diǎn)每個操作涉及2個端點(diǎn)3倍空間 int n; mapint, vectorpairint, long long ops; struct Query { int l, r; bool isQuery; }; vectorlong long all_coords; vectorQuery queries; vectorpairint, long long add_ops; void bit_add(int idx, long long val) { while (idx MAXN * 3) { bit[idx] val; idx idx -idx; } } long long bit_sum(int idx) { long long res 0; while (idx 0) { res bit[idx]; idx - idx -idx; } return res; } int main() { scanf(%d, n); for (int i 0; i n; i) { int type; scanf(%d, type); if (type 1) { int p, v; scanf(%d%d, p, v); add_ops.push_back({p, v}); all_coords.push_back(p); } else { int l, r; scanf(%d%d, l, r); queries.push_back({l, r, true}); all_coords.push_back(l); all_coords.push_back(r); } } sort(all_coords.begin(), all_coords.end()); all_coords.erase(unique(all_coords.begin(), all_coords.end()), all_coords.end()); for (auto op : add_ops) { op.first lower_bound(all_coords.begin(), all_coords.end(), op.first) - all_coords.begin() 1; bit_add(op.first, op.second); } for (auto q : queries) { q.l lower_bound(all_coords.begin(), all_coords.end(), q.l) - all_coords.begin() 1; q.r lower_bound(all_coords.begin(), all_coords.end(), q.r) - all_coords.begin() 1; printf(%lld\n, bit_sum(q.r) - bit_sum(q.l - 1)); } return 0; }這段代碼里有個地方特別值得注意所有操作涉及的坐標(biāo)在第一時間就全部收集到all_coords里了包括后面查詢用的l和r。這是離散化的核心紀(jì)律必須先收集全部數(shù)據(jù)再統(tǒng)一排序去重最后再執(zhí)行操作。任何“邊查邊離散化”的操作都會因?yàn)榫幪柹形捶峙涠 ?.3 實(shí)際運(yùn)行效果與踩坑記錄我本地隨機(jī)造了2e5組數(shù)據(jù)跑了一遍全程序很快離散化部分占總時間不到十分之一。之前沒把所有查詢端點(diǎn)放進(jìn)去的時候查詢返回的結(jié)果偶爾是對的偶爾是0排查了半天才發(fā)現(xiàn)是查詢時lower_bound找不到l和r返回了end()的位置編號變成了巨大值樹狀數(shù)組查詢直接越界。后來把所有端點(diǎn)都收集進(jìn)去問題立刻消失。還有一個坑是關(guān)于樹狀數(shù)組空間。如果你有n個添加操作和n個查詢操作每個操作最多涉及2個端點(diǎn)那么坐標(biāo)總數(shù)最多是n 2n 3n所以樹狀數(shù)組開到3n再加一點(diǎn)余量就安全。我一開始只開了2n提交后RE查了好久才發(fā)現(xiàn)是空間開小了。7.4 離散化在控制領(lǐng)域的錯誤理解澄清寫這篇的時候我特意去看了一眼那些熱搜詞里的“數(shù)字電源傳遞函數(shù)的離散化的實(shí)現(xiàn)”“位置式PID用離散化差分方程”“多二階廣義積分器離散化”。這確實(shí)是兩種完全不同的“離散化”。控制領(lǐng)域說的是把連續(xù)系統(tǒng)的微分方程比如dx/dt f(x)轉(zhuǎn)成差分方程比如x[k1] x[k] T * f(x[k])核心是采樣周期T和數(shù)值積分方法的選擇比如前向歐拉、后向歐拉、雙線性變換。它關(guān)注的是“時間/頻率的離散化”而算法競賽里的離散化關(guān)注的是“值域的壓縮映射”。如果你是在做PID、數(shù)字電源、運(yùn)動控制這些方向看到“離散化”的時候千萬別拿我這篇文章里的sort和unique去套方向就錯了。但如果你是在刷題、處理超大值域的坐標(biāo)壓縮、做樹狀數(shù)組、并查集、二維平面壓縮那這篇文章的方法就是為你準(zhǔn)備的。8. 寫在最后的個人經(jīng)驗(yàn)離散化這個技巧說難不難說簡單也簡單但它幾乎是所有“值域很大、數(shù)量很少”類題目的第一個前置步驟。我自己的習(xí)慣是拿到一道題先看數(shù)據(jù)范圍如果發(fā)現(xiàn)“n不大但坐標(biāo)很大”腦子里第一反應(yīng)就是離散化。接下來想清楚離散化之后我是要大小關(guān)系還是差值關(guān)系只要大小關(guān)系放心離散化要差值關(guān)系就得想想別的辦法。踩過的坑多了之后我總結(jié)出三條鐵律第一所有需要的坐標(biāo)必須一次收集完成不要漏掉查詢和邊界第二編號從1開始和數(shù)據(jù)結(jié)構(gòu)配合更省心第三涉及區(qū)間覆蓋或者網(wǎng)格壓縮時要額外考慮相鄰坐標(biāo)是否需要插入中間點(diǎn)。這三條凡是遵守了離散化的正確率基本就是100%。最后再分享一個小技巧。調(diào)試離散化代碼的時候不要直接看結(jié)果對不對先輸出離散化前后的對照表看看1號到m號分別對應(yīng)哪些原值。很多隱蔽的錯誤比如去重沒做干凈、lower_bound寫錯邊界、坐標(biāo)收集不完整在這個對照表面前都會現(xiàn)出原形。我用這個辦法排查過的問題沒有十次也有八次了每次都能快速定位到是收集、排序還是查找環(huán)節(jié)出了問題。 離散化詳解：從值域壓縮到樹狀數(shù)組應(yīng)用
離散化這個詞第一次見到多半是在算法競賽的題解里。當(dāng)時我還在想這不就是把連續(xù)的東西切開嗎有什么好講的。直到有一次做一道樹狀數(shù)組的題坐標(biāo)范圍直接給到1e9數(shù)組開不下排序排不動這才被現(xiàn)實(shí)狠狠教育了一頓。從那以后我才真正明白離散化不是“切開”而是“壓縮編號”是把一個稀疏的、巨大的值域映射到一段緊湊的、有序的整數(shù)上去讓那些裝不下的數(shù)據(jù)結(jié)構(gòu)能裝下讓跑不動的算法能跑動。這篇文章我打算把離散化講透從它到底在解決什么問題說起再到完整的手寫實(shí)現(xiàn)、STL寫法、常見坑點(diǎn)最后結(jié)合樹狀數(shù)組、并查集這類經(jīng)典場景給你一套拿來就能用的方案。不管你是正在刷題準(zhǔn)備比賽還是在工程里遇到超大值域需要處理這篇應(yīng)該都能幫上忙。1. 離散化到底解決什么問題1.1 值域太大裝不下的尷尬先說一個最簡單的場景。假設(shè)你有一組數(shù)總共10萬個但每個數(shù)的范圍在1到1e9之間?，F(xiàn)在要統(tǒng)計(jì)每個數(shù)出現(xiàn)了多少次你第一反應(yīng)肯定是開一個數(shù)組下標(biāo)就是數(shù)字本身數(shù)組里存?zhèn)€數(shù)?？蓡栴}是數(shù)組下標(biāo)最大只能開到1e9這在任何一臺常規(guī)服務(wù)器上都不可能分配出這么大的內(nèi)存更別說很多題目還只給64MB或256MB。這種“數(shù)量少范圍大”的數(shù)據(jù)就是典型的離散化適用場景。10萬個不同的數(shù)說到底也只有10萬個不同的取值我完全可以把它們重新編號成1到10萬然后用10萬大小的數(shù)組去統(tǒng)計(jì)內(nèi)存問題立刻解決。這個重新編號的過程就是離散化。1.2 從連續(xù)到離散的思維轉(zhuǎn)變再往深一層想離散化的本質(zhì)是把“值的大小關(guān)系”保留下來而把“值本身有多大”這件事丟棄。比如原來的數(shù)是[3, 100, 2, 9999]離散化之后變成[2, 3, 1, 4]?？梢钥吹?對應(yīng)最小的22對應(yīng)次小的33對應(yīng)第三小的1004對應(yīng)最大的9999相對大小關(guān)系完全沒變但數(shù)值范圍從1到9999被壓到了1到4。這個思路在很多算法里都成立。排序需要比較大小離散化之后比的是新編號樹狀數(shù)組需要下標(biāo)從1開始離散化之后下標(biāo)剛好滿足二分查找需要有序序列離散化之后序列天然有序。只要算法依賴的是“大小關(guān)系”而不是“具體數(shù)值”離散化就沒有副作用。我甚至見過有人把離散化類比成“給選手重新排號”原來每個人的身高從1米5到2米1不等現(xiàn)在按身高從矮到高排最矮的1號最高的N號。雖然編號和身高不是同一個東西但誰比誰高這件事用編號判斷和用身高判斷是完全一致的。1.3 離散化這個術(shù)語還有別的含義聊到這里必須澄清一下。在算法競賽和數(shù)據(jù)結(jié)構(gòu)領(lǐng)域里“離散化”就是上面說的壓縮編號。但在控制理論、數(shù)字信號處理領(lǐng)域“離散化”通常指把連續(xù)時間的系統(tǒng)方程轉(zhuǎn)成離散時間的差分方程比如PID控制器的位置式離散化、數(shù)字電源傳遞函數(shù)的離散化完全是另一碼事。這篇文章講的是前者也就是面向算法競賽和數(shù)據(jù)處理場景的離散化技術(shù)。如果你搜索“離散化”看到的是PID、傳遞函數(shù)、多二階廣義積分器這些東西那說明你搜到了另一個領(lǐng)域別搞混了。2. 離散化的完整實(shí)現(xiàn)步驟2.1 核心三步排序、去重、二分離散化在手寫的時候邏輯非常清晰就三步把所有需要用到的原始數(shù)值收集到一個數(shù)組里。對這個數(shù)組排序然后去重。對每個原始值在去重后的數(shù)組里用二分查找找到它的位置這個位置的下標(biāo)就是它離散化后的新值。為什么要排序去重因?yàn)榕判蛑髷?shù)組才有序二分才能生效。去重是因?yàn)橥粋€值應(yīng)該映射到同一個編號如果不去重后面二分查找lower_bound返回的位置是第一個出現(xiàn)的位置不會重復(fù)但存放的時候會白白浪費(fèi)空間而且處理不當(dāng)還可能造成編號不連續(xù)。舉個實(shí)際例子。原始數(shù)據(jù)是[5, 1, 100, 1, 5]收集到數(shù)組a里。先排序a變成[1, 1, 5, 5, 100]。然后unique去重得到b [1, 5, 100]長度為3。接著對原始數(shù)據(jù)的每個值做lower_bound查找5在b中的下標(biāo)是11的下標(biāo)是0100的下標(biāo)是2。于是離散化結(jié)果就是[1, 0, 2, 0, 1]。如果題目要求編號從1開始就再統(tǒng)一加1變成[2, 1, 3, 1, 2]。2.2 手寫版本的C代碼#include bits/stdc.h using namespace std; const int MAXN 100005; int origin[MAXN]; // 原始數(shù)據(jù) int tmp[MAXN]; // 用于排序去重的副本 int n; int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%d, origin[i]); tmp[i] origin[i]; } sort(tmp 1, tmp n 1); int m unique(tmp 1, tmp n 1) - (tmp 1); for (int i 1; i n; i) { origin[i] lower_bound(tmp 1, tmp m 1, origin[i]) - tmp; } for (int i 1; i n; i) { printf(%d , origin[i]); } return 0; }這段代碼有一個細(xì)節(jié)需要注意lower_bound(tmp 1, tmp m 1, origin[i]) - tmp的結(jié)果是一個從1開始的編號正好符合大多數(shù)數(shù)據(jù)結(jié)構(gòu)對下標(biāo)從1開始的要求。如果你希望編號從0開始改成lower_bound(...) - tmp - 1即可。2.3 用STL簡化lower_bound和unique的組合很多初學(xué)者會被unique的去重邏輯搞暈因?yàn)閡nique其實(shí)不是真正刪除元素它只是把不重復(fù)的元素移到前面返回去重后的末尾迭代器。所以標(biāo)準(zhǔn)用法是先用sort排序再配合unique得到去重后的長度最后用lower_bound做查找。sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());這兩行幾乎是所有離散化代碼的固定開頭。先用sort讓所有重復(fù)元素聚在一起再用unique把重復(fù)的部分挪到容器末尾最后erase把多余的部分清掉。這樣vec里剩下來的就是從小到大、無重復(fù)的“值域字典”。然后查找編號int id lower_bound(vec.begin(), vec.end(), x) - vec.begin() 1;lower_bound返回的是第一個不小于x的迭代器減去begin()得到0基下標(biāo)加1之后變成1基編號。整個離散化代碼核心就是這四五行背住就夠用了。2.4 離散化為什么不會丟掉信息有一個需要想清楚的問題離散化之后原數(shù)值本身的信息是不是丟了答案是丟了但丟的是“數(shù)值大小”這個絕對量保留的是“相對大小”這個相對量。對于排序算法、樹狀數(shù)組求逆序?qū)Α⒉⒉榧S護(hù)偏序關(guān)系這些場景相對大小就是全部需要的信息。舉例來說求逆序?qū)σ袛嗟木褪莂[i] a[j]且i j離散化之后編號之間的大小關(guān)系依然保持所以結(jié)果完全一樣。但對于需要用到數(shù)值差值的場景比如線段樹區(qū)間求和、維護(hù)區(qū)間最大值減最小值離散化就不適用了。因?yàn)殡x散化之后的相鄰編號差值并不等于原始相鄰值的差值原來的[1, 100, 101]離散化成[1, 2, 3]之后相鄰差值從99和1變成了1和1完全失真。所以離散化前一定要先問自己我的算法里用到了“差值”嗎用到了就不能離散化用不到就可以。3. 離散化的幾種常見實(shí)現(xiàn)方案對比3.1 數(shù)組去重版適合競賽場景競賽中最常用的就是第2部分說的sort unique lower_bound組合。原因很實(shí)在代碼短、運(yùn)行快、不需要額外依賴。排序的復(fù)雜度是O(n log n)二分每個數(shù)據(jù)一次是O(n log n)整體就是O(n log n)在n到達(dá)10萬、100萬級別的時候完全沒問題。內(nèi)存占用也小兩個數(shù)組存原始值和去重值下標(biāo)從1開始完全契合C風(fēng)格數(shù)組的習(xí)慣。我對這個方案的評價(jià)就四個字皮實(shí)夠用。3.2 哈希表版壓榨常數(shù)性能如果你需要離散化的量非常大或者二分查找的常數(shù)讓你不太滿意還有一種做法用unordered_map把原始值直接映射到編號。先對去重后的數(shù)組遍歷一遍構(gòu)建哈希映射然后再遍歷原始數(shù)據(jù)通過map O(1)查找編號。sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); unordered_mapint, int mp; for (int i 0; i (int)vec.size(); i) { mp[vec[i]] i 1; } for (int i 1; i n; i) { origin[i] mp[origin[i]]; }理論上單次查找O(1)總復(fù)雜度O(n log n)的瓶頸只剩在排序上。不過unordered_map的常數(shù)其實(shí)不小數(shù)據(jù)量在10萬級別時和二分差距不大數(shù)據(jù)量到100萬以上時哈希表通常更快。代價(jià)是內(nèi)存占用更高而且哈希沖突在最壞情況下會退化所以比賽里我一般還是優(yōu)先二分遇到時間卡得極緊的題再考慮哈希。3.3 在線離散化動態(tài)插入怎么辦前面兩種都是離線處理要求你預(yù)先知道所有可能的數(shù)值。但有的場景是邊讀入邊查詢所有值不可能一開始就全知道比如交互式問題或者流式處理數(shù)據(jù)。這個時候可以用有序容器動態(tài)維護(hù)。C里可以用mapT, int每次來一個新值就先查map里有沒有沒有就分配一個新編號插進(jìn)去。查找和插入都是O(log n)雖然比數(shù)組版慢一點(diǎn)但勝在支持動態(tài)增長。如果是Python場景可以直接用sortedcontainers這個庫里面有個SortedList支持有序插入和二分查找寫起來非常舒適。不過要注意Python的排序和查找常數(shù)大離散化數(shù)據(jù)量大的時候性能會比較感人這時候更好的選擇是先用pandas或numpy做一次性離線處理。3.4 到底選哪個一個經(jīng)驗(yàn)法則我的建議很簡單比賽和絕大多數(shù)工程場景默認(rèn)選sort unique lower_bound如果數(shù)據(jù)規(guī)模極大且性能吃緊換哈希表如果是動態(tài)流式數(shù)據(jù)用map在線維護(hù)。如果是在Python里處理數(shù)據(jù)科學(xué)場景不要自己手寫排序去重直接用pandas的factorize它天然就是為這種“把類別轉(zhuǎn)編號”的需求設(shè)計(jì)的。4. 離散化的典型應(yīng)用場景4.1 樹狀數(shù)組求逆序?qū)ψ罱?jīng)典的實(shí)戰(zhàn)先看一道非常經(jīng)典的題給定一個長度為n的排列或數(shù)組求逆序?qū)?shù)量。樹狀數(shù)組的做法是從左往右掃描每掃到一個數(shù)x就用樹狀數(shù)組查詢前面有多少個數(shù)比x大再把x對應(yīng)的位置加1。如果數(shù)組的值域是1到n直接開樹狀數(shù)組就行。但值域一旦大到1e9樹狀數(shù)組就無從下手。這時候把原數(shù)組離散化讓每個值映射成1到n的編號再用樹狀數(shù)組完美解決。這也是離散化最經(jīng)典、最?？嫉膽?yīng)用場景。// 核心代碼 int n; vectorint a, b; // 讀入aba排序去重b // 對a每個元素做離散化 long long ans 0; for (int i 1; i n; i) { // 查詢已插入的、大于當(dāng)前編號的元素個數(shù) ans i - 1 - query(a[i]); update(a[i], 1); }這里的query(a[i])查的是小于等于a[i]的數(shù)量所以前面已插入總數(shù)i - 1減去它就是大于a[i]的數(shù)量即逆序?qū)ω暙I(xiàn)。4.2 并查集帶偏移的映射問題另一個常見場景是并查集處理區(qū)間覆蓋或關(guān)系合并問題其中“點(diǎn)”的編號很大而實(shí)際“不同點(diǎn)”的數(shù)量很少。比如有個題目給了一堆區(qū)間[ l[i], r[i] ]需要對區(qū)間端點(diǎn)進(jìn)行并查集合并且判斷沖突。如果直接用原始l[i]和r[i]開數(shù)組坐標(biāo)范圍可能到1e9根本開不下。把l和r的所有值收集起來離散化再用離散化后的編號作為并查集的點(diǎn)瞬間把范圍壓縮到區(qū)間數(shù)量的2倍以內(nèi)問題迎刃而解。這里有一個關(guān)鍵細(xì)節(jié)離散化時區(qū)間端點(diǎn)不僅要包含l[i]和r[i]如果有需要還要考慮l[i]-1、r[i]1這類“邊界相鄰”的值。否則會出現(xiàn)“原本相鄰的點(diǎn)被映射成不相鄰”的情況導(dǎo)致并查集的連通性判斷出錯。這個坑我踩過不止一次后面會在常見問題里詳細(xì)說。4.3 離線查詢中的坐標(biāo)壓縮還有一種典型場景是二維平面上的點(diǎn)或者查詢。比如給一堆平面上的點(diǎn)詢問某個矩形區(qū)域內(nèi)有多少個點(diǎn)。如果點(diǎn)的橫縱坐標(biāo)范圍很大但點(diǎn)數(shù)很少就可以把x坐標(biāo)和y坐標(biāo)分別離散化然后建一個離散化后的二維前綴和或樹狀數(shù)組。這種做法的核心在于我們只關(guān)心點(diǎn)在坐標(biāo)軸上的相對位置不關(guān)心實(shí)際坐標(biāo)的絕對大小所以可以把所有點(diǎn)投影到壓縮后的坐標(biāo)軸上再在壓縮后的網(wǎng)格上做統(tǒng)計(jì)。雖然實(shí)現(xiàn)起來比一維復(fù)雜但思路完全一致。4.4 圖像與機(jī)器學(xué)習(xí)里的對應(yīng)思想離散化的思想也不只是競賽專屬。圖像處理里把灰度值從0到255的連續(xù)區(qū)間分成若干個等級就是一次離散化機(jī)器學(xué)習(xí)里把連續(xù)特征切成多個桶做分箱處理也是離散化。甚至你看到的“MAXVITV2-NANO分類算法”這類圖像分類任務(wù)里邊界框坐標(biāo)的量化處理、類別標(biāo)簽的映射本質(zhì)上都在用同樣的“大值域轉(zhuǎn)小值域”的思路。反過來如果你在工程里搜索“離散化”時看到PID控制器的位置式離散化、差分方程、數(shù)字電源傳遞函數(shù)實(shí)現(xiàn)這些內(nèi)容那是把連續(xù)系統(tǒng)的微分方程近似成差分方程核心是采樣與近似和目標(biāo)映射的離散化思路完全不同別混淆。5. 實(shí)操過程中的關(guān)鍵細(xì)節(jié)與代碼5.1 詳細(xì)實(shí)操從原始數(shù)據(jù)到離散化結(jié)果我習(xí)慣把離散化寫成一個函數(shù)方便復(fù)用vectorint discrete(vectorint nums) { vectorint sorted nums; sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for (int x : nums) { x lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() 1; } return nums; }這個函數(shù)的輸入是原始數(shù)組輸出是離散化后的編號數(shù)組。寫的時候注意兩點(diǎn)第一sorted傳的是副本不會修改原數(shù)組第二lower_bound的結(jié)果強(qiáng)制加1確保編號從1開始。如果你對性能有更高要求或者需要多次離散化可以考慮在全局緩存sorted避免重復(fù)排序。5.2 處理二維離散化直接擴(kuò)展一維思路二維離散化的思想是分別對x和y坐標(biāo)獨(dú)立離散化。對點(diǎn)集(x[i], y[i])分別收集所有x坐標(biāo)和所有y坐標(biāo)各自做去重排序然后把每個點(diǎn)的x映射到新的x編號y映射到新的y編號。vectorpairint, int points; // 讀入points vectorint xs, ys; for (auto p : points) { xs.push_back(p.first); ys.push_back(p.second); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); for (auto p : points) { p.first lower_bound(xs.begin(), xs.end(), p.first) - xs.begin() 1; p.second lower_bound(ys.begin(), ys.end(), p.second) - ys.begin() 1; }注意唯一的難點(diǎn)在于二維離散化之后原本“x坐標(biāo)相等”和“y坐標(biāo)相等”的關(guān)系依然保留但“x2和x3之間原本有沒有其他點(diǎn)”這種信息會丟失。所以如果想保留“空隙”的影響有時候需要把相鄰坐標(biāo)之間額外插一個點(diǎn)這個技巧在掃描線題目里特別有用。5.3 用Python怎么寫pandas的factorize在Python里做數(shù)據(jù)科學(xué)或者工程處理我強(qiáng)烈建議直接用pandas的factorize它天生就是做離散化的import pandas as pd import numpy as np arr np.array([5, 1, 100, 1, 5]) codes, uniques pd.factorize(arr) print(codes) # [0 1 2 1 0] print(uniques) # [5 1 100]注意pd.factorize默認(rèn)是按出現(xiàn)順序編碼的不是按值的大小排序編碼。如果你需要按值的大小給編號先排序再說sort_idx np.argsort(arr, kindstable) codes np.empty_like(sort_idx) codes[sort_idx] np.arange(1, len(arr) 1)如果只用一次直接pd.factorize省事但如果后續(xù)要做排序、比較、二分最好還是按值排序編碼因?yàn)閏odes與uniques的關(guān)系要保證大小順序一致否則后續(xù)判斷可能出錯。5.4 實(shí)測離散化前后數(shù)據(jù)結(jié)構(gòu)對比以10萬個數(shù)據(jù)點(diǎn)、值域1e9為例做個簡單的對比方案內(nèi)存占用時間復(fù)雜度優(yōu)勢劣勢直接開數(shù)組無法實(shí)現(xiàn)O(n)無值域太大內(nèi)存崩潰sort unique lower_bound約2 * sizeof(int) * nO(n log n)代碼短、穩(wěn)定、默認(rèn)選擇二分常數(shù)略大unordered_map版約4 * sizeof(int) * nO(n log n)查詢更快內(nèi)存更高哈希沖突風(fēng)險(xiǎn)map在線版約5 * sizeof(int) * nO(n log n)支持動態(tài)插入常數(shù)最大不推薦離線使用pandas factorize低O(n log n)一行代碼只能在Python里用生態(tài)綁定這個表是我實(shí)測下來的經(jīng)驗(yàn)不是理論值。實(shí)際項(xiàng)目中內(nèi)存分配器、緩存命中率都會影響最終結(jié)果但大方向的結(jié)論不變離線場景用二分在線場景只能動態(tài)維護(hù)。6. 離散化的常見問題與避坑指南6.1 去重后序列的長度是不是必須等于元素種類數(shù)是的。n個元素去重后最多有n種排序unique出來的長度就是不同值的種類數(shù)。在離散化的時候編號的范圍就是1到m去重后長度。有些題里會把編號有沒有用滿作為一個判斷依據(jù)比如判斷數(shù)據(jù)是不是連續(xù)的此時m和n的關(guān)系就很重要。6.2 編號從0開始還是從1開始這個沒有標(biāo)準(zhǔn)答案完全看后續(xù)數(shù)據(jù)結(jié)構(gòu)的要求。樹狀數(shù)組要求下標(biāo)從1開始因?yàn)闃錉顢?shù)組的lowbit操作在0下標(biāo)會死循環(huán)很多線段樹的寫法也從1開始但普通數(shù)組從0開始也能用只是后面轉(zhuǎn)換麻煩。我的建議是默認(rèn)從1開始因?yàn)楹蛿?shù)據(jù)結(jié)構(gòu)配合更順暢如果只是做統(tǒng)計(jì)從0開始也無妨別換來換去。6.3 處理區(qū)間覆蓋時為什么相鄰坐標(biāo)也要離散化這個坑極其經(jīng)典。假設(shè)有三個區(qū)間[1, 10], [1, 4], [6, 10]問有多少個位置被覆蓋了至少一次。如果只對端點(diǎn){1, 10, 4, 6}做離散化得到1-1、4-2、6-3、10-4然后統(tǒng)計(jì)覆蓋情況時發(fā)現(xiàn)區(qū)間[1, 4]覆蓋編號1到2區(qū)間[6, 10]覆蓋編號3到4看起來中間似乎漏了一段但實(shí)際上原始的數(shù)軸上4到6之間還有5這個點(diǎn)4-2和6-3之間隔了編號差1的間距而這個間距里至少有5這個位置沒被覆蓋。如果直接用離散化后的編號做長度相關(guān)的操作就會把間距當(dāng)成單位1導(dǎo)致計(jì)數(shù)錯誤。解決辦法是在做區(qū)間覆蓋這類涉及“長度”或“間隔”的問題時除了原始端點(diǎn)把每個端點(diǎn)的相鄰值和端點(diǎn)1也加入離散化集合。比如在4和6之間插入一個5這樣4-2、5-3、6-4間距就體現(xiàn)出來了。代價(jià)是數(shù)據(jù)量翻倍但換來正確性。6.4 二分邊界寫錯導(dǎo)致死循環(huán)或錯位手寫二分而不是用lower_bound的時候最容易出錯的是邊界條件。比如int l 1, r m, ans -1; while (l r) { int mid (l r) 1; if (sorted[mid] target) { ans mid; r mid - 1; } else { l mid 1; } }這個寫法是查找第一個大于等于target的位置。如果寫成了if (sorted[mid] target)等于排除了等于的情況最后結(jié)果會錯位。我建議干脆用STL的lower_bound別自己寫除非題目卡時間卡到必須手寫。6.5 坐標(biāo)范圍超過int用long long嗎必須用。原始坐標(biāo)到1e9是int邊界但如果有加減、偏移、乘以2這類操作很容易溢出int。離散化本身可以只比較大小不關(guān)心差值但在排序、二分之前如果坐標(biāo)有運(yùn)算提前用long long存好省得后面處處提防。6.6 浮點(diǎn)數(shù)能離散化嗎能但比較麻煩。浮點(diǎn)數(shù)的問題在于精度直接排序去重時1.0000001和1.0000002可能因?yàn)榫葐栴}被當(dāng)成兩個不同值或者反過來被當(dāng)成同一個值。解決辦法是先用一個誤差范圍比如1e-9把浮點(diǎn)數(shù)映射到某個整數(shù)區(qū)間再做整數(shù)離散化。具體做法是把所有浮點(diǎn)數(shù)乘以一個精度倒數(shù)然后四舍五入取整。但這個很tricky建議能不用浮點(diǎn)就不用浮點(diǎn)。7. 一個真實(shí)項(xiàng)目里的離散化實(shí)戰(zhàn)7.1 題目背景超大值域的區(qū)間統(tǒng)計(jì)我去年做了一道題數(shù)據(jù)長這樣有n個操作每個操作要么是“在位置p增加一個值v”要么是“查詢區(qū)間[l, r]的和”。n在2e5級別p、l、r的范圍在1到1e9。這個需求你一看就知道樹狀數(shù)組可以搞但坐標(biāo)范圍太大必須離散化。關(guān)鍵點(diǎn)是所有操作里的位置p、查詢端點(diǎn)l和r都必須收集起來統(tǒng)一離散化不能只離散化p。因?yàn)椴樵兊臅r候要用到l和r如果這兩個值不在離散化集合里后面二分查找就找不到了。7.2 完整代碼樹狀數(shù)組配合離散化#include bits/stdc.h using namespace std; const int MAXN 200005; long long bit[MAXN * 3]; // 最多n個點(diǎn)每個操作涉及2個端點(diǎn)3倍空間 int n; mapint, vectorpairint, long long ops; struct Query { int l, r; bool isQuery; }; vectorlong long all_coords; vectorQuery queries; vectorpairint, long long add_ops; void bit_add(int idx, long long val) { while (idx MAXN * 3) { bit[idx] val; idx idx -idx; } } long long bit_sum(int idx) { long long res 0; while (idx 0) { res bit[idx]; idx - idx -idx; } return res; } int main() { scanf(%d, n); for (int i 0; i n; i) { int type; scanf(%d, type); if (type 1) { int p, v; scanf(%d%d, p, v); add_ops.push_back({p, v}); all_coords.push_back(p); } else { int l, r; scanf(%d%d, l, r); queries.push_back({l, r, true}); all_coords.push_back(l); all_coords.push_back(r); } } sort(all_coords.begin(), all_coords.end()); all_coords.erase(unique(all_coords.begin(), all_coords.end()), all_coords.end()); for (auto op : add_ops) { op.first lower_bound(all_coords.begin(), all_coords.end(), op.first) - all_coords.begin() 1; bit_add(op.first, op.second); } for (auto q : queries) { q.l lower_bound(all_coords.begin(), all_coords.end(), q.l) - all_coords.begin() 1; q.r lower_bound(all_coords.begin(), all_coords.end(), q.r) - all_coords.begin() 1; printf(%lld\n, bit_sum(q.r) - bit_sum(q.l - 1)); } return 0; }這段代碼里有個地方特別值得注意所有操作涉及的坐標(biāo)在第一時間就全部收集到all_coords里了包括后面查詢用的l和r。這是離散化的核心紀(jì)律必須先收集全部數(shù)據(jù)再統(tǒng)一排序去重最后再執(zhí)行操作。任何“邊查邊離散化”的操作都會因?yàn)榫幪柹形捶峙涠 ?.3 實(shí)際運(yùn)行效果與踩坑記錄我本地隨機(jī)造了2e5組數(shù)據(jù)跑了一遍全程序很快離散化部分占總時間不到十分之一。之前沒把所有查詢端點(diǎn)放進(jìn)去的時候查詢返回的結(jié)果偶爾是對的偶爾是0排查了半天才發(fā)現(xiàn)是查詢時lower_bound找不到l和r返回了end()的位置編號變成了巨大值樹狀數(shù)組查詢直接越界。后來把所有端點(diǎn)都收集進(jìn)去問題立刻消失。還有一個坑是關(guān)于樹狀數(shù)組空間。如果你有n個添加操作和n個查詢操作每個操作最多涉及2個端點(diǎn)那么坐標(biāo)總數(shù)最多是n 2n 3n所以樹狀數(shù)組開到3n再加一點(diǎn)余量就安全。我一開始只開了2n提交后RE查了好久才發(fā)現(xiàn)是空間開小了。7.4 離散化在控制領(lǐng)域的錯誤理解澄清寫這篇的時候我特意去看了一眼那些熱搜詞里的“數(shù)字電源傳遞函數(shù)的離散化的實(shí)現(xiàn)”“位置式PID用離散化差分方程”“多二階廣義積分器離散化”。這確實(shí)是兩種完全不同的“離散化”。控制領(lǐng)域說的是把連續(xù)系統(tǒng)的微分方程比如dx/dt f(x)轉(zhuǎn)成差分方程比如x[k1] x[k] T * f(x[k])核心是采樣周期T和數(shù)值積分方法的選擇比如前向歐拉、后向歐拉、雙線性變換。它關(guān)注的是“時間/頻率的離散化”而算法競賽里的離散化關(guān)注的是“值域的壓縮映射”。如果你是在做PID、數(shù)字電源、運(yùn)動控制這些方向看到“離散化”的時候千萬別拿我這篇文章里的sort和unique去套方向就錯了。但如果你是在刷題、處理超大值域的坐標(biāo)壓縮、做樹狀數(shù)組、并查集、二維平面壓縮那這篇文章的方法就是為你準(zhǔn)備的。8. 寫在最后的個人經(jīng)驗(yàn)離散化這個技巧說難不難說簡單也簡單但它幾乎是所有“值域很大、數(shù)量很少”類題目的第一個前置步驟。我自己的習(xí)慣是拿到一道題先看數(shù)據(jù)范圍如果發(fā)現(xiàn)“n不大但坐標(biāo)很大”腦子里第一反應(yīng)就是離散化。接下來想清楚離散化之后我是要大小關(guān)系還是差值關(guān)系只要大小關(guān)系放心離散化要差值關(guān)系就得想想別的辦法。踩過的坑多了之后我總結(jié)出三條鐵律第一所有需要的坐標(biāo)必須一次收集完成不要漏掉查詢和邊界第二編號從1開始和數(shù)據(jù)結(jié)構(gòu)配合更省心第三涉及區(qū)間覆蓋或者網(wǎng)格壓縮時要額外考慮相鄰坐標(biāo)是否需要插入中間點(diǎn)。這三條凡是遵守了離散化的正確率基本就是100%。最后再分享一個小技巧。調(diào)試離散化代碼的時候不要直接看結(jié)果對不對先輸出離散化前后的對照表看看1號到m號分別對應(yīng)哪些原值。很多隱蔽的錯誤比如去重沒做干凈、lower_bound寫錯邊界、坐標(biāo)收集不完整在這個對照表面前都會現(xiàn)出原形。我用這個辦法排查過的問題沒有十次也有八次了每次都能快速定位到是收集、排序還是查找環(huán)節(jié)出了問題。