データ構造

データ構造は、問題で要求される操作から逆算して選ぶ。配列をそのまま持つ前に、「何を更新し」「どの範囲の何を答えるか」を整理する。

一点更新と区間の集約が必要なら セグメント木 を参照する。和、最小値、最大値、gcd などは、結合的な演算と単位元を決めることで同じ構造として扱える。

値の順序だけが重要なら座標圧縮を先に行うことが多い。Python での圧縮方法は 座標圧縮の実装 にまとめている。

このフォルダには今後、Union-Find、Fenwick Tree、遅延セグメント木、永続データ構造のノートを追加する。