bhasky_06's blog

Inverse counting using segment tree
By bhasky_06, history, 5 years ago, In English

I know how solve inverse counting using merge sort and infact solved a modified problem.but I am not able to understand how to solve simple inverse counting using segment tree.I read on various site but was not able to understand,kindly help me with the idea

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

»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Let's loop over the permutation, starting from the end, and maintain the array $$$was$$$ where $$$was[x] = 1$$$ if value $$$x$$$ was already visited, otherwise $$$was[x] = 0$$$. At each step you need to find the number pairs $$$(i,j)$$$ such that $$$ i < j \ \&\& \ p[i] > p[j] $$$ holds. This equals to $$$\sum_{x=1}^{p[i]-1} was[x]$$$. Finally, note that you can use segment tree to maintain the array $$$was$$$ efficiently.

→ Reply