転倒数

計算機科学および離散数学における列の転倒（てんとう、英: inversion）は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。

$ \mathrm{inv}(A)=\#\{(A_{i},A_{j})\mid i<j{\,\,\mathrm{ and }\,\,}A_{i}>A_{j}\}

$ f(x + y) = f(x) + f(y) + \sum_i\sum_j c(x, i)c(y, j)[i > j]

code:python

init(N)

inv = 0

bit_add(a, 1)

inv += bit_sum(N) - bit_sum(a)