在C++中使用Fenwick树(二进制索引树)统计插入排序的移位数

Question

我试图解决插入排序的hackerrank问题，该问题要求在使用插入sort - https://www.hackerrank.com/challenges/insertion-sort/leaderboard对数组进行排序时计算移位数。在讨论论坛上我了解到，使用二叉索引树的概念，可以针对这个问题优化解决方案。我甚至理解了使用link - https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/的BIT的概念。但我仍然不能理解它是如何应用于这个问题的。我可能听起来很傻，但任何直观的解释，以及我在论坛上找到的使用BIT概念的以下代码，但一些更清晰的解释将会对我实际掌握解决方案有很大帮助。

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std ;
#define MAXN 100002
#define MAX 1000002
int n,a[MAXN],c[MAX] ;
int main()
{
 int runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d",&n) ;
  for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
  long long ret = 1LL * n * (n - 1) / 2 ;
  memset(c,0,sizeof c) ;
  for(int i = 0;i < n;i++)
  {
   for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ;
   for(int j = a[i];j < MAX;j += j & -j) c[j]++ ;
  }
  cout << ret << endl ;
 }
 return 0 ;
}

Answer 1

它是用python编写的。这对你有帮助吗？

 def insertionSort(arr):
count = 0
bit = [0] * 10000001
bit_sum = 0
count = 0

for n in arr:
    count += bit_sum
    idx = n
    while idx:
        count -= bit[idx]
        idx -= idx & -idx

    idx = n
    while idx < 10000001:
        bit[idx] += 1
        idx += idx & -idx

    bit_sum += 1

print(count)

python代码在这里