atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ データ構造 スパーステーブル Disjoint Sparse Table 区間クエリ モノイド 1. 概要 本記事では，静的な列に対する区間クエリを高速に処理するデータ構造である Disjoint Sparse Table （DST と略記することもあります）を解説します． Disjoint Sparse Table は，長さ $N$ の列に対して事前計算 $\mathrm{O}(N\log N)$ 時間を行うことで，モノイドに対する区間積クエリをクエリあたり $\mathrm{O}(1)$ 時間で処理するデータ構造です． 同様の計算量はスパーステーブルでも達成できましたが，スパーステーブルが適用できるのは二項演算がべき等な場合（$\min$，$\max$，$\gcd$ など）に限られて… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fdisjoint_sparse_table" title="Disjoint Sparse Table - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:16:31 rich https://info.atcoder.jp/entry/algorithm_lectures/disjoint_sparse_table 1.0 100%