- Arrays, Competitive Programming, inversion, prefix, subarray

Counting inversions in an subarrays

Given an array arr[], the goal is to count the number of inversions in all the sub-arrays. An inversion is a pair of indices i and j such that i > j and arr[i] < arr[j]. A sub-array from index x to y ( x= j.Naive Approach: A naive approach is to generate all possible sub-arrays and count the number of inversions in each of the sub-arrays. Below is the implementation of the above approach:C++#include using namespace std;  void findSubarrayInversions(int arr[], int n){      int inversions[n][n];                          for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            inversions[i][j] = 0;        }    }          for (int i = 0; i < n; i++) {        for (int j = i; j < n; j++) {            int ans = 0;                                    for (int x = i; x