1. 概要 アッカーマン関数はある漸化式によって定義される $2$ 変数関数で，極端に速く増加するという特徴があります．競技プログラミングでは，その逆関数のようなものである逆アッカーマン関数が，Union-Find や静的なモノイド列の区間積クエリの計算量評…

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

1. 概要 本記事では，Union-Find の計算量が $\mathrm{O}\left(N+Q\alpha(N)\right)$ であるという事実を証明します． この事実は競技プログラミングユーザーの多くが知っている非常に有名なものだと思いますが，Union-Find の基礎的な動作原理や，計算量 $\…