Skip to content →

37zigenのHP Posts

永続配列

この記事では部分永続配列(fat nodes)と全永続配列(永続 m 分木を流用)を解説する。永続配列を使うと、いくつものデータ構造が機械的に永続化できる。

Cipolla のアルゴリズム

\(p\) を奇素数として \(\mathbb{F}_p\) における平方根を \(O(\log p)\) で求める Cipolla のアルゴリズムを解説する。フロベニウス写像との関連を説明して、平方根以外の場合についても拡張する。