基於策略的資料結構的反轉計數

---

我們將使用 g++ 標頭檔案在 C++ 編譯器中編譯程式碼。g++ 是一個基於 Linux 的標頭檔案，用於在 C++ 中編譯基於策略的資料結構的程式碼。基於策略的資料結構是這樣一些結構，用於提高程式碼的效能和靈活性。這些資料結構非常有用，我們可以將它們用於許多功能，例如搜尋元素的索引、將元素插入到索引位置、從索引範圍內刪除元素等。

示例

讓我們來看一個反轉計數的例子：

假設構建的樹的內部遍歷是 **1,2,3,4,5**，當我們遍歷反轉它時，樹的結構變成 **5,4,3,2,1**。

讓我們以以下樹結構作為輸入

 < 5, 4, 3, 2, 1 >

給定的樹結構長度為 4。現在我們將考慮以下步驟來理解反轉過程。

**步驟 1** - 元素從 **index[0]** 開始，即 **5**，並與每個元素配對，直到 **index[4]**，即 **1**。因此，索引 0 到 4 之間的總數為 **4**。

(5…4), (5…3), (5…2), (5…1)

**步驟 2** - 元素從 **index[1]** 開始，即 **4**，並與每個元素配對，直到 **index[4]**，即 **1**。因此，索引 1 到 4 之間的總數為 **3**。

(4…3), (4…2), (4…1)

**步驟 3** - 元素從 **index[2]** 開始，即 **3**，並與每個元素配對，直到 **index[4]**，即 **1**。因此，索引 2 到 4 之間的總數為 **2**。

(3…2), (3…1)

**步驟 4** - 元素從 **index[3]** 開始，即 **2**，並與每個元素配對，直到 **index[4]**，即 **1**。因此，索引 3 到 4 之間的總數為 **1**。

(2…1)

這樣，我們可以編寫給定構建樹的反轉。因此，計數的反轉總數 (4+3+2+1) 為 **10**。

在這篇文章中，我們將使用基於策略的資料結構來解決反轉計數問題。

語法

程式中使用的語法如下：

vector <data_type> vector_variable_name

引數

**data_type** - 用於向量的 資料型別。

**vector_variable_name** - 用於向量的變數名。

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

引數

**typedef** - 這是 C++ 程式中使用的保留關鍵字。

**int** - 用於插入陣列項的資料型別。

**null_type** - 這是一個對映策略，用作集合。如果我們想要對映，則第二個引數必須是對映型別。

**less<int>** - 兩個函式之間的比較。

**rb_tree_tag** - 用於紅黑樹的樹型別，基於插入和刪除操作。

**tree_order_statistics_node_update** - 基於標頭檔案 'tree_policy.hpp'，包含用於基於樹的容器更新節點變體的各種操作。因此，我們將跟蹤子樹中的節點。

**pbds** - 基於策略的資料結構的變數名。

order_of_key()

演算法

• 我們將從名為 **iostream** 和 **vector** 的標頭檔案開始程式。然後，我們將提到基於 g++ 的基於策略的資料結構 (pbds) 標頭檔案。

• 我們將使用基於 GNU 的基於策略的資料結構的必要名稱空間，即 **‘using namespace __gnu_pbds’**。它將基於 pbds 初始化樹格式，即 **‘typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;’** 透過使用這些，我們將跟蹤子樹中的節點。

• 我們正在定義雙精度長資料型別的函式定義 **‘inversion_Cnt’**，它接受向量整數的引數並存儲陣列元素的地址。

• 我們將 **‘0’** 儲存到變數 **‘cnt’** 中，以處理總對的反轉計數。

• 然後初始化名為 **pb** 的物件到基於策略的變數 **‘pbds’**，以處理陣列元素的插入和配對順序。

• 初始化變數後，使用 **for** 迴圈迭代陣列元素。此陣列元素將基於以下兩個語句執行反轉操作：

• **cnt += i-pb.order_of_key(arr[i]);** - 這透過計算對值（如 <5,4>,<5,3>,<5,2>,<5,1>,<4,3>,<4,2> 等）來返回第二個引數中最小的值。

• **pb.insert(arr[i]);** - 透過使用預定義函式 insert()，我們正在新增陣列元素的反轉，即 arr[i]。

• 我們啟動主函式並宣告向量陣列輸入。

• 然後，我們使用 **‘count’** 變數呼叫函式 **‘inversion_Cnt’**。

• 最後，**‘count’** 變數給出陣列中反轉的總數。

示例

在這個程式中，我們將使用基於策略的資料結構來計算數字的反轉。

#include <iostream>
#include <vector>
// *******g++ header file*********
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
double long inversion_Cnt( vector<int>& arr) {
   double long cnt = 0;
   pbds pb;
   for(int i = 0; i < arr.size(); i++) {
      cnt += i-pb.order_of_key(arr[i]); 
      pb.insert(arr[i]); // add the array element 
   }
   return cnt;
}
int main() {
   vector<int> arr = {5, 4, 3, 2, 1}; // The inversion of following input array is <5,4>, <5,3>, <5,2>, <5,1>, <4,3>, <4,2>, <4,1>, <3,2>, <3,1>, <2,1>
   double long count = inversion_Cnt(arr);
   cout<<"Total number of inversion count using Policy based data structure is : "<<count<<endl;
   return 0;
}

輸出

Total number of inversion count using Policy based data structure is : 10

結論

我們透過執行基於反轉計數的程式來探索了 Linux 標頭檔案 (g++) 的概念。眾所周知，C++ 程式用於作業系統，它有一個跟蹤器來記錄系統的每條資訊。與這個程式一樣，我們看到子樹是如何跟蹤它的每個節點的。