atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ データ構造 区間クエリ Sqrt Tree Disjoint Sparse Table モノイド 1. 概要 本記事では，Sqrt Tree について解説します． Sqrt Tree は列の平方分割を再帰的に行うことでできる木構造です．特に静的なモノイド列に対する区間積クエリを高速に処理できます．具体的には，列の長さを $N$ とするとき，事前計算 $\mathrm{O}(N\log \log N)$ 時間のもと，クエリあたり $\mathrm{O}(1)$ 時間で区間積を処理することができます． 区間積クエリの解法としてはセグメント木や Disjoint Sparse Table（以下 DST とも略記します）を用いる方法も有名ですが，クエリの個数 $Q$ が $N$ に近い状況であれば… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fsqrt_tree" title="Sqrt Tree - 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:10:06 rich https://info.atcoder.jp/entry/algorithm_lectures/sqrt_tree 1.0 100%