c++ - 如何在数组中找到反转对及其索引位置？

Question

我发现很难在数组中找到反转对。我得到了数组中反转对的数量，但逻辑似乎很复杂，以至于我无法列出对。我是 C++ 新手，感谢任何帮助。

 Example:
 Input:  arr[] = {8, 4, 2, 1}
 Output: 6

期待这个输出

给定数组有六个反转（8,4）和索引（0,1），（4,2）和索引（1,2），（8,2）和索引（0,2），（8,1）和索引（0,3）、（4,1）和索引（1,3）、（2,1）和索引（2,4）

// C++ program to count inversions using Binary Indexed Tree 
#include<bits/stdc++.h> 
using namespace std; 

// Returns sum of arr[0..index]. This function assumes 
// that the array is preprocessed and partial sums of 
// array elements are stored in BITree[]. 
int getSum(int BITree[], int index) 
{ 
    int sum = 0; // Initialize result 

    // Traverse ancestors of BITree[index] 
    while (index > 0) 
    { 
        // Add current element of BITree to sum 
        sum += BITree[index]; 

        // Move index to parent node in getSum View 
        index -= index & (-index); 
    } 
    return sum; 
} 

// Updates a node in Binary Index Tree (BITree) at given index 
// in BITree. The given value 'val' is added to BITree[i] and 
// all of its ancestors in tree. 
void updateBIT(int BITree[], int n, int index, int val) 
{ 
    // Traverse all ancestors and add 'val' 
    while (index <= n) 
    { 
    // Add 'val' to current node of BI Tree 
    BITree[index] += val; 

    // Update index to that of parent in update View 
    index += index & (-index); 
    } 
} 

// Returns inversion count arr[0..n-1] 
int getInvCount(int arr[], int n) 
{ 
    int invcount = 0; // Initialize result 

    // Find maximum element in arr[] 
    int maxElement = 0; 
    for (int i=0; i<n; i++) 
        if (maxElement < arr[i]) 
            maxElement = arr[i]; 

    // Create a BIT with size equal to maxElement+1 (Extra 
    // one is used so that elements can be directly be 
    // used as index) 
    int BIT[maxElement+1]; 
    for (int i=1; i<=maxElement; i++) 
        BIT[i] = 0; 

    // Traverse all elements from right. 
    for (int i=n-1; i>=0; i--) 
    { 
        // Get count of elements smaller than arr[i] 
        invcount += getSum(BIT, arr[i]-1); 

        // Add current element to BIT 
        updateBIT(BIT, maxElement, arr[i], 1); 
    } 

    return invcount; 
} 

// Driver program 
int main() 
{ 
    int arr[] = {8, 4, 2, 1}; 
    int n = sizeof(arr)/sizeof(int); 
    cout << "Number of inversions are : " << getInvCount(arr,n); 
    return 0; 
} 

该程序创建了新的数组 BITree[]，使其更加复杂。如何找到元素的位置。

标签： c++fenwick-tree