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

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