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

1. 概要 本記事では，オイラーツアーテクニック について解説します． オイラーツアーテクニックは 論文 3 において導入されたテクニックです．これは木の情報を，頂点全体や辺全体を特定の方法で $1$ 列に並べることによって表現するものです．このテクニッ…

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