BITとは
Binary Indexed Treeのこと。長さ$N$の数列$(a_n)_{n=0, 1,\cdots, N-1}$を管理するとして、次のことが$O(\log N)で$実現できます。
- $a_i$に$x$を加算
- $\sum_{k=0}^i a_k$を求める
ただし、$i$は$0$から$N-1$の整数、$x$は適当な値とします。
因みに、数列の任意の連続する部分に関する和$a_s+a_{s+1}+\cdots+a_t$も、先頭から第$t$項までの和と第$s-1$項までの和の差として表せるので、BITを使って求めることができます。
転倒数とは
数列$(a_n)$について、$i < j$かつ$a_i > a_j$となる組$(i, j)$の個数のこと。反転数と呼ばれることもあるようです。
これをBITを使って求めることを考えましょう。転倒数を求めたい数列を$(a_n)$、BITで管理する数列を$(b_n)$とします。また、$(a_n)$の長さを$N$とします。$(b_n)$の長さについては方針を述べたあとに考えます。
気持ち
愚直に求めようとすると、明らかに$O(N^2)$かかります。これで間に合うならループを回して終わりです。ただ、問題中では間に合わないことが多いのでこれを$O(N\log N)$まで落としたいです。
方針
さて、転倒数は組$(i, j)$の個数という形で定義されていました。一方を固定して求め、足し上げることを考えます。
つまり、ある$j$に対して$i < j$かつ$a_i > a_j$となる$i$の個数を$t_j$とすると、転倒数は$\sum_j t_j$です。
$t_j$を順に求めていきたいですが、このままだと求めにくいので$i < j$かつ$a_i \leq a_j$となる$i$の個数$t^\prime_j$
をかわりに求めます。$(b_n)$の各項を$0$で初期化して、$j=0$から順に「$b_0$から$b_{a_j}$までの和を$t^\prime_j$とする」→「$b_{a_j}$に1を加算」を繰り返すことで求まります。
（このとき$b_k$は、「$j$回目の操作以前に$a_i=k$となる$i$を何個見たか」という情報を持っていると言えます。したがって、各ステップにおいて$\sum_{k=0}^{a_j} b_k$で$t^\prime_j$が求まると説明できます。）
ここで、$i<j$である$i$は$0,1,\cdots,j-1$の$j$個あることから$t_j=j-t^\prime_j$です。各$j$について$t_j$が求まったので、足し上げて転倒数が得られました。めでたし。
(b_n)の長さ
上述の内容をそのままやろうとすると数列$(a_n)$の最大値だけの長さが必要になります。しかし、実は$(a_n)$の項どうしの大小比較だけができれば良いので$(a_n)$に出現する値の種類数だけの長さがあれば十分です。これは$N$で上からおさえられます。
$(b_n)$の長さを圧縮する操作は$(a_n)$をコピーしてソートすればできるので、$O(N\log N)$でできます。
計算量
「方針」で述べたことを整理すると下の疑似コードのようになります。
ただし、$a_k$が数列$(a_n)$の項のうち小さい方から何番目か（最も小さいものを$0$番目とする）$f(a_k)$としています。$f$の計算は前処理に$O(N\log N)$かければ$O(1)$です。
inversion ← 0
for j in [0, N)
t'_j ← ∑[k=0,f(a[j])](b[k]) // BITを使ってO(log N)
t_j ← j - t'_j
b[f(a[j])] ← b[f(a[j])] + 1
inversion ← inversion + t_j // BITを使ってO(log N)
end
$(b_n)$の長さは$N$以下にできることから、BITの操作が$O(\log N)$になっています。転倒数を求め終わるまでに$O(\log N)$の操作を$N$回繰り返しているので、計算量は確かに$O(N\log N)$になっています。
おまけ：転倒数とバブルソートのスワップ回数
実は、これらが等しくなることがよくわからなかったので記事を書こうと思ったのですが、気づいてしまえば当たり前だったのでおまけ扱いにしました。
実際、バブルソートのスワップが数列の転倒数と等しくなることは、
- ソートが終わったとき、列の転倒数は$0$である
- $1$回のスワップで転倒数はちょうど$1$だけ減少する
ことから従います。