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