binaryindexedtree.d

import std.stdio;

class BinaryIndexedTree {
  int size;
  int[] bits;

  this(int l){
    size = l;
    bits.length = l+1;
  }

  int sum(int i){
    int s;
    while(i > 0){
      s += bits[i];
      i -= i & -i;
    }
    return s;
  }

  void add(int i, int x){
    while(i<=size){
      bits[i] += x;
      i += i & -i;
    }
  }
}

void main(char[][] args){
  /* バブルソートの計算回数を数える */
  int[] a = [3, 1, 4, 2];
  int ans;

  BinaryIndexedTree bits = new BinaryIndexedTree(a.length);

  foreach(int i, int v; a){
    ans += i - bits.sum(v);
    bits.add(v, 1);
    /* bits.bitsは交換しなくていい組の数 */
    writef("%d: ans=%d v=%d ", i, ans, v);
    writeln(bits.bits);
  }
  writeln(ans);
}

$ ./binaryindexedtree
0: ans=0 v=3 [0, 0, 0, 1, 1]
1: ans=1 v=1 [0, 1, 1, 1, 2]
2: ans=1 v=4 [0, 1, 1, 1, 3]
3: ans=3 v=2 [0, 1, 2, 1, 4]
3