omggg's blog

Inversion Count in Range
By omggg, 4 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 :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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>A_r$$$ and $$$l<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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      simple implementation

      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
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please provide the problem link ?

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here's what you're looking for https://www.youtube.com/watch?v=kPaJfAUwViY&t=1456s (fenwick tree solution)

→ Reply