How to Count inversions in multi dimensional array?

1
votes

Given a 1-D array say with 4 elements 5 4 2 3,i know of the modified merge sort(divide and conquer) algorithm to count the no of inversions(pairs such that i < j and A[i] > A[j]. But if i am given a square 2-D array(N * N),how to count inversions in something better than O(N^4) ? Note that in 2-D arrays inversions are defined as pairs such that for 2 elements having co-ordinates (x1,y1) and (x2,y2)

x1 <= x2,
y1 <= y2,
and A[x2][y2] < A[x1][y1].
Say for N = 2
5 4
2 3

the no of inversions will be 4. pairs (5,4) (5,2) (5,3) and (4,3)

I am new to stack overflow.please forgive for formatting problems.

1
arraysalgorithm

1 Answers

1
votes

Inversion Count Using Binary Indexed Tree / Fenwick Tree

Fenwick Tree is very useful data-structure for maintaining frequencies for each data element and manipulating cumulative frequencies data table.

This tutorial - BIT - will give you great start with the data structure. It has all the implementation details.

Having understood the data structure, you can use it to count inversions in array. Suppose we have a[1...n] and inversion is defined as all pairs i, j such that i<j => a[i] > a[j]

Initially, all the frequencies are initialized to 0.

for i = n to 1
    res += range-sum(1, a[i]-1)
    insert(a[i])

Finally, res will be your answer.

Time taken: O(nlogn)

For multi-dimensional, create multi-dimensional binary indexed tree. The above tutorial gives an example of 2D-BIT

Here is my implementation as per above tutorial:

#define sz(x) ((int)x.size())
#define LSOne(x) (x & -x)
typedef long long LL;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

//Use one based indexing
class FenwickTree{
public:
  vvi ft;
  int n;
  FenwickTree(int _n){
    n=_n;
    ft.assign(n,vi(n,0));
  }
  int rsq(int x,int y){
    int sum=0;
    for(;x;x-=LSOne(x))sum += rsqY(x,y);
    return sum;
  }
  int rsqY(int x,int y){
    int sum=0;
    for(;y;y-=LSOne(y))sum += ft[x][y];
    return sum;
  }
  int rsq(int _x,int _y,int x,int y){
    return rsq(x,y)-rsq(x,_y-1)-rsq(_x-1,y)+rsq(_x-1,_y-1);
  }
  void update(int x,int y,int v){
    for(;x<=n;x+=LSOne(x))updateY(x,y,v);
  }
  void updateY(int x,int y,int v){
    for(;y<=n;y+=LSOne(y))ft[x][y] += v; 
  }
  void clear(){
    ft.assign(n,vi(n,0));
  }
};