基于策略的数据结构的反转计数

---

我们将使用 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++ 程序用于操作系统，它有一个跟踪器来记录系统的每条信息。与这个程序一样，我们看到子树是如何跟踪它的每个节点的。