Pythonで理解する蟻本「3-3 バブルソートの交換回数」(p.162)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-3 バブルソートの交換回数」(p.162)
のコードをPythonで書き直したものとなっています。

入力

入力例

4
3 1 4 2

解答

# 入力
n = int(input())
a = list(map(int,input().split()))

# BITのソースコード
class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

BIT = BinaryIndexedTree(n)
ans = 0
for j in range(n):
    ans += j - BIT.sum(a[j])
    BIT.add(a[j], 1)
print(ans)