[C#] セグメント木を実装してみる
セグメント木とは セグメント木は名前の通り区間を扱うのが得意なデータ構造です。中身は完全二分木であり、区間の持つデータを管理します。 要素8件からなる配列のデータについて、セグメント木は具体的には以下のような形になります。 各ノードの中の数字は配列の区間データを格納します。 上記のような二分木のデータ構造を使うと、区間に関するクエリ(データの更新、取得)を計算量 O(log N)行えます。 なにが […]
Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。