1. 概要 本記事では，競技プログラミング（あるいは AtCoder Algorithm Lectures）での使用頻度が高い，代数構造に関する用語および，その代表例について解説します． 代数構造は典型的には，集合と集合上の演算の組として定義されます．例えば，整数に対す…

1. 概要 本記事では，静的な列に対する区間クエリを高速に処理するデータ構造である Disjoint Sparse Table （DST と略記することもあります）を解説します． Disjoint Sparse Table は，長さ $N$ の列に対して事前計算 $\mathrm{O}(N\log N)$ 時間を行うこ…

1. 概要 通常のセグメント木は，更新を行うたびに古い状態を破棄し，常に最新のバージョンだけを保持する構造になっています．それに対して 永続セグメント木 は，過去のすべてのバージョンに対してアクセスや更新が可能なセグメント木です． 永続セグメント…

1. 概要 本記事では，静的な配列に対するある種の区間クエリを高速に処理するデータ構造であるスパーステーブル（Sparse Table）を解説します． スパーステーブルは，事前計算に $\mathrm{O}(N\log N)$ 時間を使うことで，区間最小値などのクエリに $\mathrm…

1. 概要 本記事では，Sqrt Tree について解説します． Sqrt Tree は列の平方分割を再帰的に行うことでできる木構造です．特に静的なモノイド列に対する区間積クエリを高速に処理できます．具体的には，列の長さを $N$ とするとき，事前計算 $\mathrm{O}(N\lo…

1. 概要 本記事では Sqrt Tree などに続き，再び静的なモノイド列に対する区間積クエリの問題を扱います． 特に，長さ $N$ の列について $\mathrm{O}(N)$ 時間の事前計算を前提とした場合，クエリあたり $\mathrm{O}(\alpha(N))$ 時間（$\alpha(N)$ は逆アッ…