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