組求逆序數(shù)：原理、模板與實(shí)戰(zhàn)應(yīng)用)
1. 項(xiàng)目概述從排序問題到逆序數(shù)在算法和數(shù)據(jù)結(jié)構(gòu)的日常應(yīng)用中我們經(jīng)常會遇到一類經(jīng)典問題如何高效地統(tǒng)計(jì)一個(gè)序列中“逆序?qū)Α钡臄?shù)量。所謂逆序?qū)褪侵冈谝粋€(gè)序列中如果存在兩個(gè)元素a[i]和a[j]滿足i j且a[i] a[j]那么(a[i], a[j])就構(gòu)成了一個(gè)逆序?qū)?。逆序?shù)的總數(shù)就是這個(gè)序列中所有逆序?qū)Φ臄?shù)量。這個(gè)概念聽起來簡單但在實(shí)際場景中卻無處不在比如衡量一個(gè)排列的“混亂程度”分析用戶行為序列的異常甚至在計(jì)算金融交易中的某些指標(biāo)時(shí)都可能需要用到它。最直觀的解法是雙層循環(huán)暴力枚舉時(shí)間復(fù)雜度為 O(n2)這在數(shù)據(jù)量稍大比如 n 10?時(shí)是完全不可接受的。因此我們需要尋找更高效的算法。歸并排序在合并過程中可以統(tǒng)計(jì)逆序數(shù)其時(shí)間復(fù)雜度為 O(n log n)這已經(jīng)是一個(gè)很大的進(jìn)步。然而歸并排序的過程會改變原數(shù)組的順序有時(shí)我們可能希望在不改變原序列的情況下進(jìn)行統(tǒng)計(jì)或者需要處理一些更動態(tài)的問題比如序列元素會更新。這時(shí)樹狀數(shù)組Binary Indexed Tree, BIT就閃亮登場了。樹狀數(shù)組求逆序數(shù)本質(zhì)上是一種“權(quán)值樹狀數(shù)組”的應(yīng)用。它的核心思想是將序列的值域映射到一個(gè)數(shù)組下標(biāo)上然后從左到右或從右到左遍歷原序列每遇到一個(gè)數(shù)就查詢在當(dāng)前已經(jīng)遍歷過的數(shù)中有多少個(gè)比它大或比它小的數(shù)這個(gè)查詢結(jié)果累加起來就是逆序數(shù)。查詢和更新操作都能在 O(log n) 的時(shí)間內(nèi)完成因此整體復(fù)雜度依然是 O(n log n)但相比歸并排序它提供了更大的靈活性。今天我們就來徹底拆解這個(gè)“樹狀數(shù)組求逆序數(shù)模板”不僅給你可以直接“抄作業(yè)”的代碼更要講清楚每一步背后的邏輯、常見的坑以及如何應(yīng)對各種變體問題。2. 核心原理與思路拆解2.1 為什么是樹狀數(shù)組要理解這個(gè)模板首先要明白為什么樹狀數(shù)組適合這個(gè)問題。樹狀數(shù)組本質(zhì)上是一個(gè)支持單點(diǎn)更新和前綴和查詢的數(shù)據(jù)結(jié)構(gòu)兩者時(shí)間復(fù)雜度都是 O(log n)。求逆序數(shù)的過程可以完美地轉(zhuǎn)化為一系列前綴和查詢和單點(diǎn)更新的操作。設(shè)想一下這個(gè)過程我們有一個(gè)序列arr。我們準(zhǔn)備一個(gè)輔助數(shù)組bit樹狀數(shù)組它的下標(biāo)代表數(shù)值需要經(jīng)過離散化處理后面會講。我們從左到右遍歷arr對于當(dāng)前元素arr[i]我們想知道在它之前已經(jīng)出現(xiàn)過的元素中有多少個(gè)是大于arr[i]的。因?yàn)閍rr[i]之前的元素都已經(jīng)通過更新操作記錄在了bit中。如何查詢“大于arr[i]的數(shù)量”呢我們可以查詢整個(gè)值域內(nèi)出現(xiàn)的總數(shù)減去小于等于arr[i]的數(shù)量。而“小于等于arr[i]的數(shù)量”正是bit中下標(biāo)從 1 到arr[i]的前綴和。設(shè)總數(shù)為total當(dāng)前已遍歷元素個(gè)數(shù)為i那么大于arr[i]的數(shù)量就是i - query(arr[i])。這里的query(x)就是查詢值小于等于x的元素個(gè)數(shù)。將這個(gè)數(shù)量累加到答案中。然后我們將arr[i]這個(gè)值“標(biāo)記”為已出現(xiàn)即對bit中下標(biāo)為arr[i]的位置執(zhí)行update(arr[i], 1)操作表示這個(gè)數(shù)值多出現(xiàn)了一次。這個(gè)過程清晰地將逆序數(shù)統(tǒng)計(jì)分解為了標(biāo)準(zhǔn)的樹狀數(shù)組操作。其優(yōu)勢在于在線處理可以邊讀入數(shù)據(jù)邊計(jì)算無需存儲整個(gè)數(shù)組后再處理。支持動態(tài)更新如果題目后續(xù)允許修改某個(gè)位置的值樹狀數(shù)組可以較容易地?cái)U(kuò)展先刪除舊值的影響再增加新值的影響。思路直觀將數(shù)值映射為下標(biāo)用前綴和表示累積數(shù)量非常符合直覺。2.2 關(guān)鍵前置步驟離散化樹狀數(shù)組的下標(biāo)通常從1開始并且我們無法直接開一個(gè)大小為10^9的數(shù)組來對應(yīng)可能很大的原始數(shù)值。因此離散化是必不可少的一步。離散化的目標(biāo)是將原始的、可能值域很大、不連續(xù)的數(shù)值映射到一個(gè)連續(xù)的、緊湊的整數(shù)區(qū)間通常是1到n上同時(shí)保持它們之間的大小關(guān)系不變。例如原始序列[999, 1, 20, 1]離散化后可能變成[3, 1, 2, 1]。逆序?qū)Φ臄?shù)量在離散化前后是保持不變的因?yàn)榇笮￡P(guān)系被保留了。離散化后我們的樹狀數(shù)組大小只需要開到n序列長度即可極大地節(jié)省了空間。離散化通常有兩種做法排序去重二分查找這是最通用和推薦的方法。先將原數(shù)組復(fù)制一份排序并去除重復(fù)元素得到唯一值的有序列表。然后對于原數(shù)組的每一個(gè)元素用二分查找如lower_bound找到其在有序列表中對應(yīng)的位置從1開始編號這個(gè)位置就是離散化后的值。借助map或unordered_map遍歷原數(shù)組為每個(gè)首次出現(xiàn)的數(shù)值分配一個(gè)遞增的id。這種方法在編碼上可能更簡單但map本身有 log 因子unordered_map最壞情況可能退化對于性能要求極高的場景方法1更穩(wěn)定。在我們的模板中將采用第一種方法因?yàn)樗矢咔医Y(jié)果確定。2.3 算法流程總覽結(jié)合離散化和樹狀數(shù)組整個(gè)算法的步驟可以概括如下輸入讀取整數(shù)序列arr。離散化將arr復(fù)制到temp數(shù)組對temp排序并去重得到唯一值列表vals。遍歷原arr將每個(gè)元素替換為其在vals中的下標(biāo)通常1以保證下標(biāo)從1開始得到離散化后的數(shù)組disc_arr。初始化創(chuàng)建一個(gè)大小為len(vals)5多加一些防止越界的樹狀數(shù)組bit所有元素初始為0。初始化答案ans 0。遍歷統(tǒng)計(jì)從左到右遍歷disc_arr中的每個(gè)元素num a.查詢計(jì)算當(dāng)前已遍歷的元素中值大于num的元素個(gè)數(shù)。公式為greater_count i - query(num)。其中i是當(dāng)前遍歷的次數(shù)從0開始計(jì)數(shù)query(num)返回樹狀數(shù)組中前num項(xiàng)的和即值小于等于num的元素個(gè)數(shù)。 b.累加將greater_count加到ans上。 c.更新執(zhí)行update(num, 1)將num這個(gè)值出現(xiàn)的次數(shù)加1。輸出遍歷結(jié)束后ans即為逆序?qū)倲?shù)。這個(gè)流程是模板的核心骨架。接下來我們將深入每一個(gè)環(huán)節(jié)的代碼實(shí)現(xiàn)和細(xì)節(jié)。3. 模板代碼逐行解析與實(shí)現(xiàn)下面給出一個(gè)用 C 實(shí)現(xiàn)的、風(fēng)格清晰且健壯的模板。我們將分段解析并解釋每一部分的作用和注意事項(xiàng)。3.1 數(shù)據(jù)結(jié)構(gòu)定義與輔助函數(shù)#include iostream #include vector #include algorithm using namespace std; class BIT { private: vectorint tree; int n; public: BIT(int size) : n(size), tree(size 1, 0) {} // 單點(diǎn)更新將下標(biāo)為 idx 的位置增加 val void update(int idx, int val) { while (idx n) { tree[idx] val; idx idx -idx; // 關(guān)鍵lowbit 操作跳到父節(jié)點(diǎn)或下一個(gè)管轄節(jié)點(diǎn) } } // 前綴和查詢返回下標(biāo)從 1 到 idx 的元素和 int query(int idx) { int sum 0; while (idx 0) { sum tree[idx]; idx - idx -idx; // 關(guān)鍵lowbit 操作跳到前一個(gè)管轄區(qū)間 } return sum; } };代碼解析與心得tree數(shù)組下標(biāo)從1開始這是樹狀數(shù)組的標(biāo)準(zhǔn)約定能簡化lowbit運(yùn)算。構(gòu)造函數(shù)中tree(size 1, 0)確保了有效下標(biāo)從1到size。update和query函數(shù)中的idx -idx是精髓它獲取了idx的二進(jìn)制表示中最低位的1所對應(yīng)的值即lowbit。update通過idx lowbit(idx)向上更新所有管轄當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)query通過idx - lowbit(idx)向前累加所有獨(dú)立的前綴區(qū)間。理解這個(gè)操作是理解樹狀數(shù)組的關(guān)鍵。將樹狀數(shù)組封裝成類提高了代碼的復(fù)用性和可讀性。在競賽或工程中這都是好習(xí)慣。3.2 離散化實(shí)現(xiàn)vectorint discretize(vectorint arr) { vectorint temp arr; // 1. 復(fù)制原數(shù)組 sort(temp.begin(), temp.end()); // 2. 排序 // 3. 去重。unique將重復(fù)元素移到末尾返回去重后的尾后迭代器然后erase刪除。 temp.erase(unique(temp.begin(), temp.end()), temp.end()); vectorint result(arr.size()); for (int i 0; i arr.size(); i) { // 4. 二分查找每個(gè)元素在去重排序數(shù)組中的位置從1開始 // lower_bound 返回第一個(gè)不小于 arr[i] 的迭代器相減得到下標(biāo)1使下標(biāo)從1開始 result[i] lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() 1; } return result; }注意事項(xiàng)與避坑指南去重是必須的如果不去重相同的原始值會被映射到不同的下標(biāo)嗎lower_bound對于相同值會返回第一個(gè)出現(xiàn)的位置所以相同值會被映射到同一個(gè)下標(biāo)這符合我們的需求。但去重能讓temp數(shù)組更小二分查找稍微快一點(diǎn)更重要的是概念清晰temp代表所有不同的值。下標(biāo)從1開始lower_bound(...) - temp.begin()得到的是從0開始的下標(biāo)。我們1是為了適配樹狀數(shù)組下標(biāo)從1開始的要求。這是最容易出錯(cuò)的地方之一忘記1會導(dǎo)致 update 和 query 時(shí)下標(biāo)為0陷入死循環(huán)或得到錯(cuò)誤結(jié)果。處理負(fù)數(shù)如果原序列包含負(fù)數(shù)sort和lower_bound依然可以正常工作因?yàn)樗鼈儽容^的是數(shù)值本身。離散化后負(fù)數(shù)會被映射到正數(shù)下標(biāo)不影響逆序?qū)y(tǒng)計(jì)。性能離散化的時(shí)間復(fù)雜度是 O(n log n)空間復(fù)雜度 O(n)。對于百萬級的數(shù)據(jù)這個(gè)開銷是可以接受的。3.3 主邏輯逆序數(shù)統(tǒng)計(jì)long long countInversions(vectorint arr) { if (arr.empty()) return 0; // 1. 離散化 vectorint disc_arr discretize(arr); int max_val *max_element(disc_arr.begin(), disc_arr.end()); // 2. 初始化樹狀數(shù)組大小設(shè)為 max_val 即可 BIT bit(max_val); long long ans 0; // 使用 long long逆序數(shù)可能很大 for (int i 0; i disc_arr.size(); i) { int num disc_arr[i]; // 3. 查詢已遍歷的數(shù)中有多少個(gè)大于當(dāng)前數(shù) num // 已遍歷的數(shù)總數(shù)為 i小于等于 num 的數(shù)為 bit.query(num) // 所以大于 num 的數(shù)為 i - bit.query(num) long long greater_count i - bit.query(num); ans greater_count; // 4. 更新將當(dāng)前數(shù) num 的出現(xiàn)次數(shù)1 bit.update(num, 1); } return ans; }逐行解讀與核心技巧返回值類型逆序?qū)Φ臄?shù)量最大可能達(dá)到n*(n-1)/2對于n10^5這個(gè)值約5*10^9超出了32位整型int的范圍。因此務(wù)必使用long long來存儲答案ans。這是一個(gè)非常經(jīng)典的坑無數(shù)人在此失分。查詢邏輯bit.query(num)返回的是值小于等于num的元素個(gè)數(shù)這些元素都是在當(dāng)前元素num之前下標(biāo)更小出現(xiàn)的。當(dāng)前已遍歷的元素總數(shù)是i注意i從0開始所以當(dāng)處理第1個(gè)元素時(shí)i0之前有0個(gè)元素。因此在num之前出現(xiàn)且值大于num的元素個(gè)數(shù)就是i - bit.query(num)。這個(gè)推導(dǎo)是算法的核心務(wù)必理解。更新時(shí)機(jī)先查詢再更新。因?yàn)槲覀円樵兊氖恰霸诋?dāng)前位置之前”的元素如果先更新就把自己也算進(jìn)去了邏輯就錯(cuò)了。樹狀數(shù)組大小max_val是離散化后的最大值樹狀數(shù)組需要能覆蓋這個(gè)下標(biāo)范圍。通常我們直接BIT bit(max_val)即可構(gòu)造函數(shù)里會分配max_val1的空間。3.4 完整可運(yùn)行模板將以上部分組合并添加一個(gè)簡單的main函數(shù)進(jìn)行測試#include iostream #include vector #include algorithm using namespace std; class BIT { /* 同上省略 */ }; vectorint discretize(vectorint arr) { /* 同上省略 */ } long long countInversions(vectorint arr) { /* 同上省略 */ } int main() { // 測試用例1: 普通序列 vectorint arr1 {7, 5, 6, 4}; cout Inversions in [7,5,6,4]: countInversions(arr1) endl; // 應(yīng)輸出 5 // (7,5), (7,6), (7,4), (5,4), (6,4) // 測試用例2: 已排序升序序列逆序數(shù)為0 vectorint arr2 {1, 2, 3, 4, 5}; cout Inversions in [1,2,3,4,5]: countInversions(arr2) endl; // 應(yīng)輸出 0 // 測試用例3: 逆序序列 vectorint arr3 {5, 4, 3, 2, 1}; cout Inversions in [5,4,3,2,1]: countInversions(arr3) endl; // 應(yīng)輸出 10 (C(5,2)10) // 測試用例4: 包含重復(fù)元素 vectorint arr4 {2, 3, 3, 1, 1}; cout Inversions in [2,3,3,1,1]: countInversions(arr4) endl; // 應(yīng)輸出 6 // (2,1), (2,1), (3,1), (3,1), (3,1), (3,1) 注意重復(fù)元素之間的對不算逆序?qū)?return 0; }這個(gè)模板清晰、模塊化并且包含了必要的測試。你可以直接復(fù)制BIT類、discretize函數(shù)和countInversions函數(shù)到你的代碼中作為求解逆序數(shù)問題的通用工具。4. 變體、邊界情況與性能優(yōu)化掌握了基礎(chǔ)模板我們來看看它如何應(yīng)對各種變化和極端情況。4.1 處理重復(fù)元素我們的模板已經(jīng)正確處理了重復(fù)元素。關(guān)鍵在于離散化步驟和查詢邏輯。離散化unique去重確保了相同的原始值映射到同一個(gè)離散化值。例如[2,3,3,1]離散化為[2,3,3,1]假設(shè)映射后值域是1~3。查詢邏輯bit.query(num)查詢的是“值小于等于num的個(gè)數(shù)”。當(dāng)遇到第二個(gè)3時(shí)bit.query(3)已經(jīng)包含了第一個(gè)3所以i - bit.query(3)計(jì)算的是嚴(yán)格大于3的個(gè)數(shù)第二個(gè)3和第一個(gè)3之間不會形成逆序?qū)@符合逆序?qū)Φ亩xij且a[i] a[j]對于相等情況不成立。因此該模板天然支持重復(fù)元素?zé)o需特殊處理。4.2 從右向左遍歷的視角我們之前的模板是從左到右遍歷統(tǒng)計(jì)“當(dāng)前元素與其之前元素構(gòu)成的逆序?qū)Α?。我們也可以從右向左遍歷統(tǒng)計(jì)“當(dāng)前元素與其之后元素構(gòu)成的逆序?qū)Α薄４藭r(shí)邏輯稍有不同long long countInversionsFromRight(vectorint arr) { vectorint disc_arr discretize(arr); int max_val *max_element(disc_arr.begin(), disc_arr.end()); BIT bit(max_val); long long ans 0; // 從右向左遍歷 for (int i disc_arr.size() - 1; i 0; --i) { int num disc_arr[i]; // 查詢在當(dāng)前元素之后已經(jīng)遍歷過的即原序列中在它右邊的且比它小的元素個(gè)數(shù) // 因?yàn)槭菑挠蚁蜃笏?query(num-1) 得到的是值小于 num 的個(gè)數(shù)注意不是小于等于 // 如果要查詢小于等于則是 query(num) ans bit.query(num - 1); // 統(tǒng)計(jì) a[i] a[j] (i j) 的對即右邊比它小的數(shù) bit.update(num, 1); } return ans; }從右向左遍歷時(shí)bit中記錄的是當(dāng)前元素右邊已經(jīng)出現(xiàn)的數(shù)。bit.query(num-1)查詢的是值嚴(yán)格小于num的數(shù)的個(gè)數(shù)這些數(shù)在原序列中位于當(dāng)前元素的右邊且值更小正好與當(dāng)前元素構(gòu)成逆序?qū)?。兩種遍歷方式結(jié)果相同可以根據(jù)個(gè)人習(xí)慣或具體問題選擇。4.3 空間與時(shí)間優(yōu)化空間優(yōu)化樹狀數(shù)組本身空間是 O(n)。離散化需要額外的 O(n) 空間存儲臨時(shí)數(shù)組。在內(nèi)存極度緊張的情況下可以考慮“在線離散化”或使用其他統(tǒng)計(jì)方法但會犧牲代碼清晰度。對于絕大多數(shù)情況O(n) 的空間是可以接受的。時(shí)間優(yōu)化算法整體 O(n log n) 的復(fù)雜度已經(jīng)接近最優(yōu)。常數(shù)優(yōu)化點(diǎn)包括使用數(shù)組代替vector在已知最大n且不是特別大的情況下用原生數(shù)組int tree[MAXN]可能比vector稍快但vector更安全便捷。離散化優(yōu)化如果輸入數(shù)據(jù)本身就是1到n的一個(gè)排列即每個(gè)數(shù)從1到n恰好出現(xiàn)一次那么可以跳過離散化步驟直接使用原數(shù)組作為下標(biāo)。這是一個(gè)常見的特例可以節(jié)省離散化的時(shí)間。循環(huán)展開與位運(yùn)算在極端優(yōu)化場景下可以手動展開update和query的循環(huán)但現(xiàn)代編譯器優(yōu)化已經(jīng)很好了收益不大且會降低可讀性。4.4 擴(kuò)展到二維或多維逆序?qū)錉顢?shù)組可以結(jié)合排序解決一些二維偏序問題例如求平面上的“逆序點(diǎn)對”。思路通常是固定一維如按x坐標(biāo)排序然后在另一維y坐標(biāo)上建立樹狀數(shù)組進(jìn)行統(tǒng)計(jì)。這已經(jīng)超出了基礎(chǔ)逆序數(shù)的范疇但思想是相通的通過排序降維然后在另一維上使用數(shù)據(jù)結(jié)構(gòu)進(jìn)行高效查詢和更新。5. 常見問題排查與實(shí)戰(zhàn)調(diào)試技巧即使有了模板在實(shí)際編碼和調(diào)試中也可能遇到各種問題。這里記錄一些常見坑點(diǎn)和調(diào)試方法。5.1 典型錯(cuò)誤與解決方案問題現(xiàn)象可能原因解決方案答案輸出負(fù)數(shù)或非常大答案ans使用int類型溢出將ans和中間變量greater_count改為long long程序運(yùn)行超時(shí) (TLE)離散化使用了map且數(shù)據(jù)量大樹狀數(shù)組操作寫成了 O(n)使用排序二分進(jìn)行離散化檢查update/query循環(huán)條件確保是while(idx n)和while(idx 0)且idx通過lowbit正確跳轉(zhuǎn)答案總是0或明顯偏小離散化后下標(biāo)從0開始而樹狀數(shù)組下標(biāo)從1開始檢查離散化函數(shù)確保對lower_bound的結(jié)果加1(... - temp.begin() 1)答案偏大查詢和更新順序錯(cuò)誤先更新后查詢確保在循環(huán)中先query再update段錯(cuò)誤 (Segmentation Fault)樹狀數(shù)組tree大小不夠樹狀數(shù)組大小應(yīng)至少為max_val 1。在構(gòu)造函數(shù)中tree(size1, 0)傳入的size應(yīng)是離散化后的最大值max_val處理重復(fù)元素結(jié)果錯(cuò)誤對逆序?qū)Χx理解有誤或查詢邏輯寫錯(cuò)牢記逆序?qū)σ髧?yán)格大于。使用i - query(num)邏輯時(shí)query(num)包含等于num的所以差值就是大于num的正確5.2 調(diào)試心得與單元測試從小數(shù)據(jù)開始不要一上來就用大數(shù)據(jù)測試。先用手工能算出來的小數(shù)組如[3,1,2],[1,1,1],[5,4,3,2,1]驗(yàn)證結(jié)果是否正確。打印中間變量在懷疑出錯(cuò)的地方打印離散化前后的數(shù)組、每次循環(huán)的i,num,query(num),greater_count,ans等。這是最直接的調(diào)試方法。對比暴力算法寫一個(gè) O(n2) 的暴力雙重循環(huán)函數(shù)用于對小數(shù)據(jù)n 1000進(jìn)行結(jié)果比對確保復(fù)雜算法的正確性。測試邊界測試空數(shù)組、單元素?cái)?shù)組、全部元素相同的數(shù)組、已經(jīng)排序的數(shù)組、完全逆序的數(shù)組。內(nèi)存與越界檢查使用vector的at()方法訪問如tree.at(idx)可以在調(diào)試時(shí)捕獲越界訪問比[]運(yùn)算符更安全確定無誤后再換回[]提升性能。5.3 一個(gè)綜合調(diào)試案例假設(shè)我們寫錯(cuò)了離散化忘記了1// 錯(cuò)誤代碼片段 result[i] lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin(); // 忘記 1對于輸入[2, 3, 1]離散化后temp [1, 2, 3]arr[0]2lower_bound(...)得到下標(biāo)1從0開始所以result[0]1錯(cuò)誤應(yīng)該是2最終disc_arr [1, 2, 0]因?yàn)?的下標(biāo)是0。運(yùn)行主邏輯時(shí)當(dāng)num0進(jìn)入bit.query(0)while(idx 0)條件不成立直接返回0。這會導(dǎo)致統(tǒng)計(jì)錯(cuò)誤。通過打印disc_arr就能立刻發(fā)現(xiàn)問題。掌握這個(gè)模板不僅僅是背下代碼更要理解其背后的映射思想將數(shù)值映射為下標(biāo)、前綴和思想查詢小于等于某值的個(gè)數(shù)以及離線處理思想通過排序/遍歷確定時(shí)間順序。這能幫助你在遇到諸如“統(tǒng)計(jì)區(qū)間內(nèi)小于某個(gè)值的元素個(gè)數(shù)”、“動態(tài)排名”等問題時(shí)能夠靈活運(yùn)用樹狀數(shù)組這一利器。 樹狀數(shù)組求逆序數(shù)：原理、模板與實(shí)戰(zhàn)應(yīng)用
1. 項(xiàng)目概述從排序問題到逆序數(shù)在算法和數(shù)據(jù)結(jié)構(gòu)的日常應(yīng)用中我們經(jīng)常會遇到一類經(jīng)典問題如何高效地統(tǒng)計(jì)一個(gè)序列中“逆序?qū)Α钡臄?shù)量。所謂逆序?qū)褪侵冈谝粋€(gè)序列中如果存在兩個(gè)元素a[i]和a[j]滿足i j且a[i] a[j]那么(a[i], a[j])就構(gòu)成了一個(gè)逆序?qū)?。逆序?shù)的總數(shù)就是這個(gè)序列中所有逆序?qū)Φ臄?shù)量。這個(gè)概念聽起來簡單但在實(shí)際場景中卻無處不在比如衡量一個(gè)排列的“混亂程度”分析用戶行為序列的異常甚至在計(jì)算金融交易中的某些指標(biāo)時(shí)都可能需要用到它。最直觀的解法是雙層循環(huán)暴力枚舉時(shí)間復(fù)雜度為 O(n2)這在數(shù)據(jù)量稍大比如 n 10?時(shí)是完全不可接受的。因此我們需要尋找更高效的算法。歸并排序在合并過程中可以統(tǒng)計(jì)逆序數(shù)其時(shí)間復(fù)雜度為 O(n log n)這已經(jīng)是一個(gè)很大的進(jìn)步。然而歸并排序的過程會改變原數(shù)組的順序有時(shí)我們可能希望在不改變原序列的情況下進(jìn)行統(tǒng)計(jì)或者需要處理一些更動態(tài)的問題比如序列元素會更新。這時(shí)樹狀數(shù)組Binary Indexed Tree, BIT就閃亮登場了。樹狀數(shù)組求逆序數(shù)本質(zhì)上是一種“權(quán)值樹狀數(shù)組”的應(yīng)用。它的核心思想是將序列的值域映射到一個(gè)數(shù)組下標(biāo)上然后從左到右或從右到左遍歷原序列每遇到一個(gè)數(shù)就查詢在當(dāng)前已經(jīng)遍歷過的數(shù)中有多少個(gè)比它大或比它小的數(shù)這個(gè)查詢結(jié)果累加起來就是逆序數(shù)。查詢和更新操作都能在 O(log n) 的時(shí)間內(nèi)完成因此整體復(fù)雜度依然是 O(n log n)但相比歸并排序它提供了更大的靈活性。今天我們就來徹底拆解這個(gè)“樹狀數(shù)組求逆序數(shù)模板”不僅給你可以直接“抄作業(yè)”的代碼更要講清楚每一步背后的邏輯、常見的坑以及如何應(yīng)對各種變體問題。2. 核心原理與思路拆解2.1 為什么是樹狀數(shù)組要理解這個(gè)模板首先要明白為什么樹狀數(shù)組適合這個(gè)問題。樹狀數(shù)組本質(zhì)上是一個(gè)支持單點(diǎn)更新和前綴和查詢的數(shù)據(jù)結(jié)構(gòu)兩者時(shí)間復(fù)雜度都是 O(log n)。求逆序數(shù)的過程可以完美地轉(zhuǎn)化為一系列前綴和查詢和單點(diǎn)更新的操作。設(shè)想一下這個(gè)過程我們有一個(gè)序列arr。我們準(zhǔn)備一個(gè)輔助數(shù)組bit樹狀數(shù)組它的下標(biāo)代表數(shù)值需要經(jīng)過離散化處理后面會講。我們從左到右遍歷arr對于當(dāng)前元素arr[i]我們想知道在它之前已經(jīng)出現(xiàn)過的元素中有多少個(gè)是大于arr[i]的。因?yàn)閍rr[i]之前的元素都已經(jīng)通過更新操作記錄在了bit中。如何查詢“大于arr[i]的數(shù)量”呢我們可以查詢整個(gè)值域內(nèi)出現(xiàn)的總數(shù)減去小于等于arr[i]的數(shù)量。而“小于等于arr[i]的數(shù)量”正是bit中下標(biāo)從 1 到arr[i]的前綴和。設(shè)總數(shù)為total當(dāng)前已遍歷元素個(gè)數(shù)為i那么大于arr[i]的數(shù)量就是i - query(arr[i])。這里的query(x)就是查詢值小于等于x的元素個(gè)數(shù)。將這個(gè)數(shù)量累加到答案中。然后我們將arr[i]這個(gè)值“標(biāo)記”為已出現(xiàn)即對bit中下標(biāo)為arr[i]的位置執(zhí)行update(arr[i], 1)操作表示這個(gè)數(shù)值多出現(xiàn)了一次。這個(gè)過程清晰地將逆序數(shù)統(tǒng)計(jì)分解為了標(biāo)準(zhǔn)的樹狀數(shù)組操作。其優(yōu)勢在于在線處理可以邊讀入數(shù)據(jù)邊計(jì)算無需存儲整個(gè)數(shù)組后再處理。支持動態(tài)更新如果題目后續(xù)允許修改某個(gè)位置的值樹狀數(shù)組可以較容易地?cái)U(kuò)展先刪除舊值的影響再增加新值的影響。思路直觀將數(shù)值映射為下標(biāo)用前綴和表示累積數(shù)量非常符合直覺。2.2 關(guān)鍵前置步驟離散化樹狀數(shù)組的下標(biāo)通常從1開始并且我們無法直接開一個(gè)大小為10^9的數(shù)組來對應(yīng)可能很大的原始數(shù)值。因此離散化是必不可少的一步。離散化的目標(biāo)是將原始的、可能值域很大、不連續(xù)的數(shù)值映射到一個(gè)連續(xù)的、緊湊的整數(shù)區(qū)間通常是1到n上同時(shí)保持它們之間的大小關(guān)系不變。例如原始序列[999, 1, 20, 1]離散化后可能變成[3, 1, 2, 1]。逆序?qū)Φ臄?shù)量在離散化前后是保持不變的因?yàn)榇笮￡P(guān)系被保留了。離散化后我們的樹狀數(shù)組大小只需要開到n序列長度即可極大地節(jié)省了空間。離散化通常有兩種做法排序去重二分查找這是最通用和推薦的方法。先將原數(shù)組復(fù)制一份排序并去除重復(fù)元素得到唯一值的有序列表。然后對于原數(shù)組的每一個(gè)元素用二分查找如lower_bound找到其在有序列表中對應(yīng)的位置從1開始編號這個(gè)位置就是離散化后的值。借助map或unordered_map遍歷原數(shù)組為每個(gè)首次出現(xiàn)的數(shù)值分配一個(gè)遞增的id。這種方法在編碼上可能更簡單但map本身有 log 因子unordered_map最壞情況可能退化對于性能要求極高的場景方法1更穩(wěn)定。在我們的模板中將采用第一種方法因?yàn)樗矢咔医Y(jié)果確定。2.3 算法流程總覽結(jié)合離散化和樹狀數(shù)組整個(gè)算法的步驟可以概括如下輸入讀取整數(shù)序列arr。離散化將arr復(fù)制到temp數(shù)組對temp排序并去重得到唯一值列表vals。遍歷原arr將每個(gè)元素替換為其在vals中的下標(biāo)通常1以保證下標(biāo)從1開始得到離散化后的數(shù)組disc_arr。初始化創(chuàng)建一個(gè)大小為len(vals)5多加一些防止越界的樹狀數(shù)組bit所有元素初始為0。初始化答案ans 0。遍歷統(tǒng)計(jì)從左到右遍歷disc_arr中的每個(gè)元素num a.查詢計(jì)算當(dāng)前已遍歷的元素中值大于num的元素個(gè)數(shù)。公式為greater_count i - query(num)。其中i是當(dāng)前遍歷的次數(shù)從0開始計(jì)數(shù)query(num)返回樹狀數(shù)組中前num項(xiàng)的和即值小于等于num的元素個(gè)數(shù)。 b.累加將greater_count加到ans上。 c.更新執(zhí)行update(num, 1)將num這個(gè)值出現(xiàn)的次數(shù)加1。輸出遍歷結(jié)束后ans即為逆序?qū)倲?shù)。這個(gè)流程是模板的核心骨架。接下來我們將深入每一個(gè)環(huán)節(jié)的代碼實(shí)現(xiàn)和細(xì)節(jié)。3. 模板代碼逐行解析與實(shí)現(xiàn)下面給出一個(gè)用 C 實(shí)現(xiàn)的、風(fēng)格清晰且健壯的模板。我們將分段解析并解釋每一部分的作用和注意事項(xiàng)。3.1 數(shù)據(jù)結(jié)構(gòu)定義與輔助函數(shù)#include iostream #include vector #include algorithm using namespace std; class BIT { private: vectorint tree; int n; public: BIT(int size) : n(size), tree(size 1, 0) {} // 單點(diǎn)更新將下標(biāo)為 idx 的位置增加 val void update(int idx, int val) { while (idx n) { tree[idx] val; idx idx -idx; // 關(guān)鍵lowbit 操作跳到父節(jié)點(diǎn)或下一個(gè)管轄節(jié)點(diǎn) } } // 前綴和查詢返回下標(biāo)從 1 到 idx 的元素和 int query(int idx) { int sum 0; while (idx 0) { sum tree[idx]; idx - idx -idx; // 關(guān)鍵lowbit 操作跳到前一個(gè)管轄區(qū)間 } return sum; } };代碼解析與心得tree數(shù)組下標(biāo)從1開始這是樹狀數(shù)組的標(biāo)準(zhǔn)約定能簡化lowbit運(yùn)算。構(gòu)造函數(shù)中tree(size 1, 0)確保了有效下標(biāo)從1到size。update和query函數(shù)中的idx -idx是精髓它獲取了idx的二進(jìn)制表示中最低位的1所對應(yīng)的值即lowbit。update通過idx lowbit(idx)向上更新所有管轄當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)query通過idx - lowbit(idx)向前累加所有獨(dú)立的前綴區(qū)間。理解這個(gè)操作是理解樹狀數(shù)組的關(guān)鍵。將樹狀數(shù)組封裝成類提高了代碼的復(fù)用性和可讀性。在競賽或工程中這都是好習(xí)慣。3.2 離散化實(shí)現(xiàn)vectorint discretize(vectorint arr) { vectorint temp arr; // 1. 復(fù)制原數(shù)組 sort(temp.begin(), temp.end()); // 2. 排序 // 3. 去重。unique將重復(fù)元素移到末尾返回去重后的尾后迭代器然后erase刪除。 temp.erase(unique(temp.begin(), temp.end()), temp.end()); vectorint result(arr.size()); for (int i 0; i arr.size(); i) { // 4. 二分查找每個(gè)元素在去重排序數(shù)組中的位置從1開始 // lower_bound 返回第一個(gè)不小于 arr[i] 的迭代器相減得到下標(biāo)1使下標(biāo)從1開始 result[i] lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() 1; } return result; }注意事項(xiàng)與避坑指南去重是必須的如果不去重相同的原始值會被映射到不同的下標(biāo)嗎lower_bound對于相同值會返回第一個(gè)出現(xiàn)的位置所以相同值會被映射到同一個(gè)下標(biāo)這符合我們的需求。但去重能讓temp數(shù)組更小二分查找稍微快一點(diǎn)更重要的是概念清晰temp代表所有不同的值。下標(biāo)從1開始lower_bound(...) - temp.begin()得到的是從0開始的下標(biāo)。我們1是為了適配樹狀數(shù)組下標(biāo)從1開始的要求。這是最容易出錯(cuò)的地方之一忘記1會導(dǎo)致 update 和 query 時(shí)下標(biāo)為0陷入死循環(huán)或得到錯(cuò)誤結(jié)果。處理負(fù)數(shù)如果原序列包含負(fù)數(shù)sort和lower_bound依然可以正常工作因?yàn)樗鼈儽容^的是數(shù)值本身。離散化后負(fù)數(shù)會被映射到正數(shù)下標(biāo)不影響逆序?qū)y(tǒng)計(jì)。性能離散化的時(shí)間復(fù)雜度是 O(n log n)空間復(fù)雜度 O(n)。對于百萬級的數(shù)據(jù)這個(gè)開銷是可以接受的。3.3 主邏輯逆序數(shù)統(tǒng)計(jì)long long countInversions(vectorint arr) { if (arr.empty()) return 0; // 1. 離散化 vectorint disc_arr discretize(arr); int max_val *max_element(disc_arr.begin(), disc_arr.end()); // 2. 初始化樹狀數(shù)組大小設(shè)為 max_val 即可 BIT bit(max_val); long long ans 0; // 使用 long long逆序數(shù)可能很大 for (int i 0; i disc_arr.size(); i) { int num disc_arr[i]; // 3. 查詢已遍歷的數(shù)中有多少個(gè)大于當(dāng)前數(shù) num // 已遍歷的數(shù)總數(shù)為 i小于等于 num 的數(shù)為 bit.query(num) // 所以大于 num 的數(shù)為 i - bit.query(num) long long greater_count i - bit.query(num); ans greater_count; // 4. 更新將當(dāng)前數(shù) num 的出現(xiàn)次數(shù)1 bit.update(num, 1); } return ans; }逐行解讀與核心技巧返回值類型逆序?qū)Φ臄?shù)量最大可能達(dá)到n*(n-1)/2對于n10^5這個(gè)值約5*10^9超出了32位整型int的范圍。因此務(wù)必使用long long來存儲答案ans。這是一個(gè)非常經(jīng)典的坑無數(shù)人在此失分。查詢邏輯bit.query(num)返回的是值小于等于num的元素個(gè)數(shù)這些元素都是在當(dāng)前元素num之前下標(biāo)更小出現(xiàn)的。當(dāng)前已遍歷的元素總數(shù)是i注意i從0開始所以當(dāng)處理第1個(gè)元素時(shí)i0之前有0個(gè)元素。因此在num之前出現(xiàn)且值大于num的元素個(gè)數(shù)就是i - bit.query(num)。這個(gè)推導(dǎo)是算法的核心務(wù)必理解。更新時(shí)機(jī)先查詢再更新。因?yàn)槲覀円樵兊氖恰霸诋?dāng)前位置之前”的元素如果先更新就把自己也算進(jìn)去了邏輯就錯(cuò)了。樹狀數(shù)組大小max_val是離散化后的最大值樹狀數(shù)組需要能覆蓋這個(gè)下標(biāo)范圍。通常我們直接BIT bit(max_val)即可構(gòu)造函數(shù)里會分配max_val1的空間。3.4 完整可運(yùn)行模板將以上部分組合并添加一個(gè)簡單的main函數(shù)進(jìn)行測試#include iostream #include vector #include algorithm using namespace std; class BIT { /* 同上省略 */ }; vectorint discretize(vectorint arr) { /* 同上省略 */ } long long countInversions(vectorint arr) { /* 同上省略 */ } int main() { // 測試用例1: 普通序列 vectorint arr1 {7, 5, 6, 4}; cout Inversions in [7,5,6,4]: countInversions(arr1) endl; // 應(yīng)輸出 5 // (7,5), (7,6), (7,4), (5,4), (6,4) // 測試用例2: 已排序升序序列逆序數(shù)為0 vectorint arr2 {1, 2, 3, 4, 5}; cout Inversions in [1,2,3,4,5]: countInversions(arr2) endl; // 應(yīng)輸出 0 // 測試用例3: 逆序序列 vectorint arr3 {5, 4, 3, 2, 1}; cout Inversions in [5,4,3,2,1]: countInversions(arr3) endl; // 應(yīng)輸出 10 (C(5,2)10) // 測試用例4: 包含重復(fù)元素 vectorint arr4 {2, 3, 3, 1, 1}; cout Inversions in [2,3,3,1,1]: countInversions(arr4) endl; // 應(yīng)輸出 6 // (2,1), (2,1), (3,1), (3,1), (3,1), (3,1) 注意重復(fù)元素之間的對不算逆序?qū)?return 0; }這個(gè)模板清晰、模塊化并且包含了必要的測試。你可以直接復(fù)制BIT類、discretize函數(shù)和countInversions函數(shù)到你的代碼中作為求解逆序數(shù)問題的通用工具。4. 變體、邊界情況與性能優(yōu)化掌握了基礎(chǔ)模板我們來看看它如何應(yīng)對各種變化和極端情況。4.1 處理重復(fù)元素我們的模板已經(jīng)正確處理了重復(fù)元素。關(guān)鍵在于離散化步驟和查詢邏輯。離散化unique去重確保了相同的原始值映射到同一個(gè)離散化值。例如[2,3,3,1]離散化為[2,3,3,1]假設(shè)映射后值域是1~3。查詢邏輯bit.query(num)查詢的是“值小于等于num的個(gè)數(shù)”。當(dāng)遇到第二個(gè)3時(shí)bit.query(3)已經(jīng)包含了第一個(gè)3所以i - bit.query(3)計(jì)算的是嚴(yán)格大于3的個(gè)數(shù)第二個(gè)3和第一個(gè)3之間不會形成逆序?qū)@符合逆序?qū)Φ亩xij且a[i] a[j]對于相等情況不成立。因此該模板天然支持重復(fù)元素?zé)o需特殊處理。4.2 從右向左遍歷的視角我們之前的模板是從左到右遍歷統(tǒng)計(jì)“當(dāng)前元素與其之前元素構(gòu)成的逆序?qū)Α?。我們也可以從右向左遍歷統(tǒng)計(jì)“當(dāng)前元素與其之后元素構(gòu)成的逆序?qū)Α薄４藭r(shí)邏輯稍有不同long long countInversionsFromRight(vectorint arr) { vectorint disc_arr discretize(arr); int max_val *max_element(disc_arr.begin(), disc_arr.end()); BIT bit(max_val); long long ans 0; // 從右向左遍歷 for (int i disc_arr.size() - 1; i 0; --i) { int num disc_arr[i]; // 查詢在當(dāng)前元素之后已經(jīng)遍歷過的即原序列中在它右邊的且比它小的元素個(gè)數(shù) // 因?yàn)槭菑挠蚁蜃笏?query(num-1) 得到的是值小于 num 的個(gè)數(shù)注意不是小于等于 // 如果要查詢小于等于則是 query(num) ans bit.query(num - 1); // 統(tǒng)計(jì) a[i] a[j] (i j) 的對即右邊比它小的數(shù) bit.update(num, 1); } return ans; }從右向左遍歷時(shí)bit中記錄的是當(dāng)前元素右邊已經(jīng)出現(xiàn)的數(shù)。bit.query(num-1)查詢的是值嚴(yán)格小于num的數(shù)的個(gè)數(shù)這些數(shù)在原序列中位于當(dāng)前元素的右邊且值更小正好與當(dāng)前元素構(gòu)成逆序?qū)?。兩種遍歷方式結(jié)果相同可以根據(jù)個(gè)人習(xí)慣或具體問題選擇。4.3 空間與時(shí)間優(yōu)化空間優(yōu)化樹狀數(shù)組本身空間是 O(n)。離散化需要額外的 O(n) 空間存儲臨時(shí)數(shù)組。在內(nèi)存極度緊張的情況下可以考慮“在線離散化”或使用其他統(tǒng)計(jì)方法但會犧牲代碼清晰度。對于絕大多數(shù)情況O(n) 的空間是可以接受的。時(shí)間優(yōu)化算法整體 O(n log n) 的復(fù)雜度已經(jīng)接近最優(yōu)。常數(shù)優(yōu)化點(diǎn)包括使用數(shù)組代替vector在已知最大n且不是特別大的情況下用原生數(shù)組int tree[MAXN]可能比vector稍快但vector更安全便捷。離散化優(yōu)化如果輸入數(shù)據(jù)本身就是1到n的一個(gè)排列即每個(gè)數(shù)從1到n恰好出現(xiàn)一次那么可以跳過離散化步驟直接使用原數(shù)組作為下標(biāo)。這是一個(gè)常見的特例可以節(jié)省離散化的時(shí)間。循環(huán)展開與位運(yùn)算在極端優(yōu)化場景下可以手動展開update和query的循環(huán)但現(xiàn)代編譯器優(yōu)化已經(jīng)很好了收益不大且會降低可讀性。4.4 擴(kuò)展到二維或多維逆序?qū)錉顢?shù)組可以結(jié)合排序解決一些二維偏序問題例如求平面上的“逆序點(diǎn)對”。思路通常是固定一維如按x坐標(biāo)排序然后在另一維y坐標(biāo)上建立樹狀數(shù)組進(jìn)行統(tǒng)計(jì)。這已經(jīng)超出了基礎(chǔ)逆序數(shù)的范疇但思想是相通的通過排序降維然后在另一維上使用數(shù)據(jù)結(jié)構(gòu)進(jìn)行高效查詢和更新。5. 常見問題排查與實(shí)戰(zhàn)調(diào)試技巧即使有了模板在實(shí)際編碼和調(diào)試中也可能遇到各種問題。這里記錄一些常見坑點(diǎn)和調(diào)試方法。5.1 典型錯(cuò)誤與解決方案問題現(xiàn)象可能原因解決方案答案輸出負(fù)數(shù)或非常大答案ans使用int類型溢出將ans和中間變量greater_count改為long long程序運(yùn)行超時(shí) (TLE)離散化使用了map且數(shù)據(jù)量大樹狀數(shù)組操作寫成了 O(n)使用排序二分進(jìn)行離散化檢查update/query循環(huán)條件確保是while(idx n)和while(idx 0)且idx通過lowbit正確跳轉(zhuǎn)答案總是0或明顯偏小離散化后下標(biāo)從0開始而樹狀數(shù)組下標(biāo)從1開始檢查離散化函數(shù)確保對lower_bound的結(jié)果加1(... - temp.begin() 1)答案偏大查詢和更新順序錯(cuò)誤先更新后查詢確保在循環(huán)中先query再update段錯(cuò)誤 (Segmentation Fault)樹狀數(shù)組tree大小不夠樹狀數(shù)組大小應(yīng)至少為max_val 1。在構(gòu)造函數(shù)中tree(size1, 0)傳入的size應(yīng)是離散化后的最大值max_val處理重復(fù)元素結(jié)果錯(cuò)誤對逆序?qū)Χx理解有誤或查詢邏輯寫錯(cuò)牢記逆序?qū)σ髧?yán)格大于。使用i - query(num)邏輯時(shí)query(num)包含等于num的所以差值就是大于num的正確5.2 調(diào)試心得與單元測試從小數(shù)據(jù)開始不要一上來就用大數(shù)據(jù)測試。先用手工能算出來的小數(shù)組如[3,1,2],[1,1,1],[5,4,3,2,1]驗(yàn)證結(jié)果是否正確。打印中間變量在懷疑出錯(cuò)的地方打印離散化前后的數(shù)組、每次循環(huán)的i,num,query(num),greater_count,ans等。這是最直接的調(diào)試方法。對比暴力算法寫一個(gè) O(n2) 的暴力雙重循環(huán)函數(shù)用于對小數(shù)據(jù)n 1000進(jìn)行結(jié)果比對確保復(fù)雜算法的正確性。測試邊界測試空數(shù)組、單元素?cái)?shù)組、全部元素相同的數(shù)組、已經(jīng)排序的數(shù)組、完全逆序的數(shù)組。內(nèi)存與越界檢查使用vector的at()方法訪問如tree.at(idx)可以在調(diào)試時(shí)捕獲越界訪問比[]運(yùn)算符更安全確定無誤后再換回[]提升性能。5.3 一個(gè)綜合調(diào)試案例假設(shè)我們寫錯(cuò)了離散化忘記了1// 錯(cuò)誤代碼片段 result[i] lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin(); // 忘記 1對于輸入[2, 3, 1]離散化后temp [1, 2, 3]arr[0]2lower_bound(...)得到下標(biāo)1從0開始所以result[0]1錯(cuò)誤應(yīng)該是2最終disc_arr [1, 2, 0]因?yàn)?的下標(biāo)是0。運(yùn)行主邏輯時(shí)當(dāng)num0進(jìn)入bit.query(0)while(idx 0)條件不成立直接返回0。這會導(dǎo)致統(tǒng)計(jì)錯(cuò)誤。通過打印disc_arr就能立刻發(fā)現(xiàn)問題。掌握這個(gè)模板不僅僅是背下代碼更要理解其背后的映射思想將數(shù)值映射為下標(biāo)、前綴和思想查詢小于等于某值的個(gè)數(shù)以及離線處理思想通過排序/遍歷確定時(shí)間順序。這能幫助你在遇到諸如“統(tǒng)計(jì)區(qū)間內(nèi)小于某個(gè)值的元素個(gè)數(shù)”、“動態(tài)排名”等問題時(shí)能夠靈活運(yùn)用樹狀數(shù)組這一利器。