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