差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:inversion [2018/05/25] – ikatakos | programming_algorithm:dynamic_programming:inversion [2018/05/28] – ikatakos | ||
---|---|---|---|
行 57: | 行 57: | ||
===数列を先頭から順番に処理する=== | ===数列を先頭から順番に処理する=== | ||
- | $i$ 番目(1-indexed)の項を $p_i$ とする。 | + | $i$ 番目(1-indexed)の項を $p_i$ とする。各項に付き、以下の2つの処理を行う。 |
==BITに加算する== | ==BITに加算する== | ||
$ADD(p_i, 1)$(BITの $p_i$ の位置に、1を加算する) | $ADD(p_i, 1)$(BITの $p_i$ の位置に、1を加算する) | ||
- | ==自分より右にある自分より大きい数の個数を求める== | + | ==自分より左にある自分より大きい数の個数を求める== |
先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 | 先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 | ||