Using policy-based data structures for reverse counting

We will use the g header file to compile the code in the C compiler. g is a Linux-based header file for compiling code for policy-based data structures in C. Policy-based data structures are structures used for high performance and flexibility in your code. Since these data structures are very rich, we can use them for many functions such as searching the index for an element, inserting an element into an index position, removing an element from an index range, etc.

The Chinese translation of

Example

is:

Example

Let’s take an example of reversing counting -

Suppose the internal traversal to build the tree is 1,2,3,4,5, when we traverse to reverse it, the form of the tree becomes 5,4,3,2 ,1.

Let us take the following tree structure as input

 < 5, 4, 3, 2, 1 >

The given structure tree length is 4. Now we will consider the following steps to understand the process of inversion.

Step 1 - Element starts with index[0] i.e. 5, and paired with every element until index[4] is 1. So the total count between indexes 0 and 4 is 4.

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

Step 2 - Elements start from index[1] i.e. 4, and paired with each element until index[4 ] is 1. Therefore, the total count between indexes 1 to 4 is 3.

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

Step 3 - Element starts with index[2] i.e. 3, and paired with each element until index[4] That is 1. So the total count between indexes 2 and 4 is 2.

(3…2), (3…1)

Step 4 - Elements start at index[3], i.e. 2, and are paired with each element until index[4 ], that is, 1. Therefore, the total count between index 3 and 4 is 1.

(2…1)

This way we can write the inversion of a given construction tree. Therefore, the total number of reversals of count(4 3 2 1) is 10.

In this article, we will use policy-based data structures to solve the inversion counting problem.

grammar

Use the following syntax in the program -

vector <data_type> vector_variable_name

parameter

data_type - The data type used for vectors.

vector_variable_name − Variable name to use for vectors.

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

parameter

typedef - This is a reserved keyword used in C programs.

int − Data type of inserted array item.

null_type - This is a mapping strategy and is used as a collection. If we want to map, then the second parameter must be the map type.

less - Comparison between two functions.

rb_tree_tag - Tree type for red-black trees based on insertion and deletion.

tree_order_statistics_node_update − This is based on the header file ‘tree_policy.hpp’, which contains various operations for updating the tree container of node variants. Therefore, we will keep track of the nodes in the subtree.

pbds - Variable name for the policy-based data structure.

order_of_key()

algorithm

• We will use the header files iostream and vector to start the program. Then we will mention the header file policy-based data structures (pbds) based on g .

• We will use the necessary namespace based on the data structure according to GNU's policy, that is, 'using namespace __gnu_pbds'. It will initialize the tree according to the format of pbds, i.e. 'typedef tree, rb_tree_tag, tree_order_statistics_node_update> pbds;By using these, we will keep track of the nodes in the subtree .

• We are defining a function definition of double long data type 'inversion_Cnt', which accepts a vector integer parameter and stores the address of the array element.

• We store ‘0’ into the variable ‘cnt’ in order to process the reverse count of the total pairs.

• The object named pb is then initialized to a strategy-based variable 'pbds' to operate on the insertion and sorting of array elements.

• After initializing the variable, use a for loop to iterate over the array elements. This array element will be reversed according to the following two statements -

• cnt = i-pb.order_of_key(arr[i]); - By calculating <5,4>,< 等对值来返回第二个参数中的最小值5,3>,<5,2>,<5,1>,<4,3>,<4,2> wait.

• pb.insert(arr[i]); - By using the predefined function insert(), we add the inversion of the array element, i.e. arr[i].

• We start the main function and declare the vector array input.

• Then we use the variable 'count' to call the function 'inversion_Cnt'.

• Finally, the ‘count’ variable gives the total count of inversions in the array.

The Chinese translation of

Example

is:

Example

In this program, we will use strategic data structures to calculate the reverse of a number.

#include 
#include 
// *******g++ header file*********
#include 
#include 

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& 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 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 : "<
Copy after login

输出

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

结论

我们通过执行基于反转计数的程序来探索 Linux 头文件 (g++) 的概念。众所周知，C++程序用于操作系统，它有一个跟踪器来记录系统的每一个信息。与此程序相同，我们看到子树如何跟踪其每个节点。

The above is the detailed content of Using policy-based data structures for reverse counting. For more information, please follow other related articles on the PHP Chinese website!