初期化配列の実装 - Qiita

こんにちは、最近ハマっている初期化配列について紹介したいと思います。 はじめに 皆さんプログラミングをする時に配列を使ってますか？使ってない人はほとんどいないのではないでしょうか？ 長さNの固定長配列AはN個の要素を格納でき、かつ任意の位置に保存された要素A[i]を最悪定数時間（以下、定数時間）で読み書き可能な最も基本的なデータ構造の一つです。配列の様々な操作の中で読み書きについで頻出する重要な操作が、配列の全ての要素を指定した値に書き換える初期化操作です。配列の初期化は配列長に対して線形な時間がかかるため、配列長が長い場合や、初期化が頻出する処理では配列の初期化操作が大きなボトルネックとなります。この問題を解決するデータ構造が初期化配列です。本記事ではシンプルな初期化配列の実装法、folkloreアルゴリズムを紹介したいと思います。 初期化配列とは通常の読み書きに加え、配列の全ての要素を

[tyru]

配列の初期化を定数時間で行うデータ構造

[castaneai]

実際にすべて初期化するのではなく、初期化しているように見せかけるアルゴリズム

[naga_sawa]

0 <= b < N を使って T-F 相互リンクを作りつつ、そのリンクを代入済みフラグとして未代入なら初期値を返すことで初期化配列として振る舞う/と理解/単純な代入済みフラグ配列だとそれの初期化にO(n)かかるもんね

[yhara]

へー