Inversion Count

지난번에 Number of Swap Operations 글에 대해 정리했는데..

그중에 첫번째 경우 (이웃하는 경우만 swap 가능) 는 inversion 개수를 구하는 것과 같다..

구하는 방법은 전통적으로

1. bubble sort (n^2) 로 구할 수 있고

2. merge sort 를 응용해서 구할수도 있다 (nlogn)

그러나 최근에는 binary indexed tree 를 이용한 방법이 유행이다..

이와 관련하여 누군가 잘 정리해 두었다..

inversion_count_bit.pdf