差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:inversion [2018/05/25] – [転倒数の求め方] ikatakos | programming_algorithm:dynamic_programming:inversion [2018/05/28] – ikatakos | ||
|---|---|---|---|
| 行 53: | 行 53: | ||
| これを用いて、以下のように算出する。 | これを用いて、以下のように算出する。 | ||
| - | ==BITを用意== | + | ===BITを用意=== |
| まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。 | まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。 | ||
| - | ==数列を先頭から順番に処理する== | + | ===数列を先頭から順番に処理する=== |
| - | $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にあるのは「自分より左に各数がいくつあるか」の情報である。 | ||
