差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:inversion [2018/05/25] – [転倒数の求め方] ikatakos | programming_algorithm:dynamic_programming:inversion [2018/05/25] – ikatakos | ||
|---|---|---|---|
| 行 53: | 行 53: | ||
| これを用いて、以下のように算出する。 | これを用いて、以下のように算出する。 | ||
| - | ==BITを用意== | + | ===BITを用意=== |
| まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。 | まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。 | ||
| - | ==数列を先頭から順番に処理する== | + | ===数列を先頭から順番に処理する=== |
| $i$ 番目（1-indexed）の項を $p_i$ とする。 | $i$ 番目（1-indexed）の項を $p_i$ とする。 | ||
