fork download
copy 
  1. // C++ program to count inversions using Binary Indexed Tree
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // Returns sum of arr[0..index]. This function assumes
  6. // that the array is preprocessed and partial sums of
  7. // array elements are stored in BITree[].
  8. int getSum(int BITree[], int index)
  9. {
  10.     int sum = 0; // Initialize result
  11.  
  12.     // Traverse ancestors of BITree[index]
  13.     while (index > 0)
  14.     {
  15.         // Add current element of BITree to sum
  16.         sum += BITree[index];
  17.  
  18.         // Move index to parent node in getSum View
  19.         index -= index & (-index);
  20.     }
  21.     return sum;
  22. }
  23.  
  24. // Updates a node in Binary Index Tree (BITree) at given index
  25. // in BITree.  The given value 'val' is added to BITree[i] and
  26. // all of its ancestors in tree.
  27. void updateBIT(int BITree[], int n, int index, int val)
  28. {
  29.     // Traverse all ancestors and add 'val'
  30.     while (index <= n)
  31.     {
  32.        // Add 'val' to current node of BI Tree
  33.        BITree[index] += val;
  34.  
  35.        // Update index to that of parent in update View
  36.        index += index & (-index);
  37.     }
  38. }
  39.  
  40. // Returns inversion count arr[0..n-1]
  41. int getInvCount(int arr[], int n)
  42. {
  43.     int invcount = 0; // Initialize result
  44.  
  45.     // Find maximum element in arr[]
  46.     int maxElement = 0;
  47.     for (int i=0; i<n; i++)
  48.         if (maxElement < arr[i])
  49.             maxElement = arr[i];
  50.  
  51.     // Create a BIT with size equal to maxElement+1 (Extra
  52.     // one is used so that elements can be directly be
  53.     // used as index)
  54.     int BIT[maxElement+1];
  55.     for (int i=1; i<=maxElement; i++)
  56.         BIT[i] = 0;
  57.  
  58.     // Traverse all elements from right.
  59.     for (int i=n-1; i>=0; i--)
  60.     {
  61.         // Get count of elements smaller than arr[i]
  62.         invcount += getSum(BIT, arr[i]-1);
  63.  
  64.         // Add current element to BIT
  65.         updateBIT(BIT, maxElement, arr[i], 1);
  66.     }
  67.  
  68.     return invcount;
  69. }
  70.  
  71. // Driver program
  72. int main()
  73. {
  74.     int arr[] = {1, 2, 3};
  75.     int n = sizeof(arr)/sizeof(int);
  76.     cout << "Number of inversions are : " << getInvCount(arr,n);
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
1 2 3 4 5 6
stdout
copy 
Number of inversions are : 0
https://ideone.com/oNJBlX
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!