atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ データ構造 区間クエリ Disjoint Sparse Table Sqrt Tree 逆アッカーマン関数 モノイド 1. 概要 本記事では Sqrt Tree などに続き，再び静的なモノイド列に対する区間積クエリの問題を扱います． 特に，長さ $N$ の列について $\mathrm{O}(N)$ 時間の事前計算を前提とした場合，クエリあたり $\mathrm{O}(\alpha(N))$ 時間（$\alpha(N)$ は逆アッカーマン関数）での計算が可能で，このことの解説が本記事の主目標です．アイデアとしては，Sqrt Tree の単純な一般化にあたるので，Sqrt Tree について理解していれば本記事の内容も理解しやすいと思います． 競技プログラミングにおいて $\alpha(N)$ が計算量解析に登場… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fstatic_range_product" title="静的な列の区間積クエリ - 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:09:56 rich https://info.atcoder.jp/entry/algorithm_lectures/static_range_product 1.0 100%