Inversion Count in Range

omggg's blog

By omggg, 6 years ago, In English

Ques : Find number of inversion counts in Range [L,R] for Q queries. ****

Array Size <=1000 ; Each integer from 1 to n occurs exactly once in this array.

Queries<= 100000

What is the best method you can suggest? Any help is much appreciated.

Thanks :)

inversions, inversion count, bit/fenwick tree, #fenwick tree, #sorting, #merge sort, #set, #segment tree, segment

omggg
6 years ago
8

Comments (6)

Show archived | Write comment?

Everule

6 years ago, hide # |

← Rev. 2 →

I think this can be done without a log factor in $$$O(n^2 + Q)$$$. Create a 2D array such that arr[l][r] gives us whether $$$A_l \gt A_r$$$ and $$$l \lt r$$$. Use prefix sums to calculate the inversions. It will just be the sum of arr[i][j] where $$$i$$$ and $$$j$$$ satisfy $$$l\le i \le r$$$ and $$$l\le j \le r$$$.

→ Reply

GustavoGuerra

6 years ago, hide # ^ |

If I understand correctly, it works in $$$O(n^2 + Q\cdot n)$$$, because you need to iterate over $$$[l ... r)$$$.

→ Reply

Everule

6 years ago, hide # ^ |

← Rev. 2 →

2D prefix sums can also be done in $$$O(1)$$$. Here's a simple implementation

simple implementation

    vector<vector<pair<int,int>>> prefix_sum(n+1, vector<pair<int,int>>(m+1, mp(0,0)));
    vector<vector<int>> gridsum(n+1, vector<int>(m+1, 0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=arr[i][j];
            prefix_sum[i][j].first=prefix_sum[i-1][j].first+x;
            prefix_sum[i][j].second=prefix_sum[i][j-1].second+x;
            gridsum[i][j]=gridsum[i-1][j-1] + prefix_sum[i][j].first + prefix_sum[i][j].second - x;
        }
    }

Now you can get 2D prefix sum for $$$a\le i \le b$$$ and $$$c \le j \le d$$$ by doing

gridsum[b][d] - gridsum[b][c-1] - gridsum[a-1][d] + gridsum[a-1][c-1]

→ Reply