これは競プロの知見を収集するための査読付きの半共有 wiki である。 アルゴリズムについての説明が中心となっている。なお、データ構造については scrapbox.io/data-structures (通称: デ wiki) を利用するのがよいだろう。
個人ブログの記事として情報を書くと属人性が高すぎ、古い記事のメンテのコストが高く、記事が不正確なまま残りやすいという問題があった。一方で誰でも自由に編集できる共有 wiki であると属人性が低すぎ、誰が書いたのかが分かりにくいため適切なクレジットが行なわれず、また記事の正確性も担保されないという問題があった。 そこでこの半共有 wiki は、GitHub 上のプルリクエストとレビュープロセスという管理形態を用いて、これらの問題の解決を目指している。 もし興味があれば kmyk/algorithm-encyclopedia から編集に参加してほしい。
- Aho-Corasick 法
- Aho-Corasick 法とは、複数のパターン文字列をまとめて扱える文字列検索アルゴリズムのひとつ。まず前処理として、固定された $k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ たちから Trie 木を作り、その上に適切に辺を張って $O(\sum \vert P_i \vert)$ でオートマトンを作る。このオートマトンを利用して、与えられたテキスト文字列 $T$ に対して $O(\vert T \vert)$ で検索を行う。
- Bellman-Ford 法
- Bellman-Ford 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。負辺があっても動作する。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。
- Borůvka 法
- Borůvka 法とは、最小全域木を求めるアルゴリズムのひとつ。
- Boyer-Moore 法 (BM法)
-
Boyer-Moore 法とは、文字列検索アルゴリズムのひとつ。どこで不一致が起きたらパターン文字列をいくつずらせばよいかの情報を $O(\vert P \vert)$ かけて構築しておき、パターン文字列をその末尾から順にテキスト文字列と照合していく。ランダムな文字列に対しては $O(\vert T \vert / \vert P \vert)$ だが、最悪ケースでは $O(\vert P \vert \cdot \vert T \vert)$ かかる。
- input
- パターン文字列 $P$ とテキスト文字列 $T$
- output
- パターン文字列 $P$ がテキスト文字列 $T$ に含まれるかどうか。含まれるならその位置も求める。
- time complexity
- 前処理は $O(\vert P \vert)$ である。検索は、ランダムな文字列に対しては $O(\vert T \vert / \vert P \vert)$ だが最悪ケースは $O(\vert P \vert \cdot \vert T \vert)$ である。
- Boyer-Moore-Horspool 法
-
Boyer-Moore-Horspool 法は、文字列検索アルゴリズムのひとつ。Boyer-Moore 法を簡略化したものである。
- input
- パターン文字列 $P$ とテキスト文字列 $T$
- output
- パターン文字列 $P$ がテキスト文字列 $T$ に含まれるかどうか。含まれるならその位置も求める。
- Chu-Liu/Edmonds' algorithm
-
Chu-Liu/Edmonds' algorithm とは、与えられた辺重み付き有向グラフ $G$ と頂点 $r$ に対し、$r$ を根とする最小全域有向木を $O(V E)$ で求めるアルゴリズムである。
- input
- 辺重み $c : V \to \mathbb{R}$ 付き有向グラフ $G = (V, E)$ および頂点 $r \in V$
- output
- $r$ を根とする最小全域有向木 $T$
- time complexity
- $O(V E)$
- DSU on tree (Sack)
- DSU on tree とは、それぞれの頂点 $x$ に可換 monoid $(M, +, 0)$ の要素の重み $a_x$ のついた木 $T$ のそれぞれの部分木について、その部分木内の重みの総和を全体で $O(n \log n)$ で求めるアルゴリズムである。ただし、その計算の過程において、monoid 演算 $+$ がある要素 $A \in M$ と頂点 $x$ に対し $A + a_x$ という形でしか出現しないという特徴がある。
- Dial's algorithm
- Dial's algorithm とは、単一始点最短経路問題を解くアルゴリズムのひとつ。非負かつ最大値の小さい整数重みのグラフについてしか動作しないが、重みの最大値を $k$ として $O(k \vert V \vert + \vert E \vert)$ で動く。キューの持ち方を工夫して Dijkstra 法をさらに高速化したものになっている。0-1 BFS の一般化でもあり、$k = 1$ のときは 0-1 BFS に一致する。
- Dijkstra 法
- Dijkstra 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。グラフに負の辺があると動作しない。辺が非負という仮定をもとに動的計画法を利用して高速に動作し、計算量は $O(\vert V \vert ^ 2)$ や $O(\vert E \vert \log \vert V \vert)$ などである。
- Dinic 法
- Dinic 法は最大流問題を解くアルゴリズムのひとつ。 残余グラフ上において、辺の本数の意味での $s$-$t$ 最短経路 DAG を BFS により構成し、増加パスをこの DAG の上の DFS により探して流せるだけ流す、という一連のステップを繰り返す。 計算量は $O(\lvert V \rvert^2 \lvert E \rvert)$ だが実用的にはかなり速い。
- Eppstein's algorithm
-
Eppstein's algorithm とは、与えられたグラフ $G$ の $s-t$ 歩道であって $K$ 番目に短いものを $O(K + E + V \log V)$ で求めるアルゴリズムである。
- time complexity
- $O(K + E + V \log V)$
- Eratosthenes の篩
- Eratosthenes の篩とは、素数判定アルゴリズムのひとつ。
- Euclid の互除法
-
Euclid の互除法とは、ふたつの自然数の最大公約数を求めるアルゴリズムのひとつ。
- input
- 自然数 $a, b$
- output
- 最大公約数 $\mathrm{gcd}(a, b)$
- time complexity
- $O(\log a + \log b)$
- Ford-Fulkerson 法
- Ford-Fulkerson 法は最大流問題を解くアルゴリズムのひとつ。 増加パスを DFS で探してそこにフローを流していくことを繰り返す。 計算量は出力の $s$-$t$ 最大流量を $F$ として $O(F \cdot \lvert E \rvert)$ である。
- Garner 法
-
Garner 法とは、中国剰余定理で存在が示されるところの $\forall i. x \equiv a_i \pmod{m_i}$ を満たす整数 $x$ について、それを別の $M$ で割った余り $x \bmod M$ を求めるアルゴリズムである。計算の過程で現われる整数の大きさが $m_i$ や $M$ の $2$ 乗程度で抑えられることを特徴とする。
- input
- 整数と正整数の対の長さ $k$ の列 $((a_0, m_0), (a_1, m_1), \dots, (a _ {k-1}, m _ {k-1}))$ および正整数 $M$
- output
- $\forall i. x \equiv a_i \pmod{m_i}$ を満たす $x$ を $M$ で割った余り $x \bmod M$
- time complexity
- $\bmod m_i$ および $\bmod M$ での演算を $O(1)$ と仮定して $O(k^2)$
- Johnson のアルゴリズム
- Johnson のアルゴリズムとは、全点対間最短経路問題を解くアルゴリズムのひとつ。負閉路が存在しない場合に動作する。$O(\lvert V \rvert ^ 2 \log \lvert V \rvert + \lvert V \rvert\lvert E \rvert)$ で動く。
- Karatsuba 法
- Karatsuba 法とは、多項式乗算と多倍長整数乗算を $\Theta ( N ^ { \log _ 2 3} )$ 回の環演算で行うアルゴリズムである。
- Kitamasa 法
-
Kitamasa 法とは、$k + 1$ 項間の線型漸化式で定まる数列の第 $N$ 項を $O(k^2 \log N)$ で求めるアルゴリズムである。高速 Kitamasa 法とは異なる。
- input
- $k + 1$ 項間の線型漸化式で定まる数列 $a$ の漸化式および初めの $k$ 項 $(a_0, a_1, \dots, a _ {k-1})$ および自然数 $N$
- output
- 数列 $a$ の第 $N$ 項 $a_N$
- time complexity
- $O(k^2 \log N)$
- Knuth-Morris-Pratt 法 (KMP 法)
-
Knuth-Morris-Pratt 法とは文字列検索アルゴリズムのひとつ。パターン文字列 $P$ の各 prefix について最長の border (prefix かつ suffix であるような文字列) を $O(\vert P \vert)$ で求めておくことで、与えられたテキスト文字列 $T$ に対する検索を $O(\vert T \vert)$ で行う。
- input
- パターン文字列 $P$ とテキスト文字列 $T$
- output
- パターン文字列 $P$ がテキスト文字列 $T$ に含まれるかどうか。含まれるならその位置も求める。
- time complexity
- 前処理に $O(\vert P \vert)$ かつ検索に $O(\vert T \vert)$
- Knuth-Yao speedup
- Knuth-Yao speedup とは、Monge な $N \times N$ 行列 $f$ に対して $\mathrm{dp}(l, r) = \min \lbrace \mathrm{dp}(l, m) + \mathrm{dp}(m + 1, r) \mid l \le m \lt r \rbrace + f(l, r)$ (ただし $l \le r$) で定まる関数 $\mathrm{dp}$ のグラフを $O(N^2)$ で求めるアルゴリズムである。
- Kruskal 法
- Kruskal 法とは、最小全域木を求めるアルゴリズムのひとつ。
- Lagrange 補間多項式
- Lagrange 補間多項式とは、与えられた点群 $\lbrace (x_i, y_i) \mid i \lt N \rbrace$ をすべて通る ($\forall i \lt N. f(x_i) = y_i$ を満たす) ような最小次数の多項式 $f$ のことである。 Lagrange 補間多項式を $\Theta (N (\log N) ^ 2)$ で計算するアルゴリズムが存在する。
- Manacher 法
-
Manacher 法とは、与えられた文字列 $S$ に対して、そのすべての位置 $i$ (ただし $0 \le i \lt \vert S \vert$) について「$S$ における $i$ 番目の文字を中心とする最長の回文の半径」をまとめて $O(\vert S \vert)$ で求めるアルゴリズムのひとつ。そのままでは奇数長の回文についてのみしか求まらない。偶数長の回文についても求めたいときは、$S$ の各文字の間にダミーの文字列を計 $\vert S \vert - 1$ 個挿入してできる文字列 $S'$ に対してもう一度 Manacher 法をすることになる。
- input
- 文字列 $S$
- output
- すべての $i$ について、$S$ における $i$ 番目の文字を中心とする最長の回文の半径
- time complexity
- $O(\vert S \vert)$
- Mo's algorithm (クエリ平方分割)
- Mo's algorithm とは、群 $G$ の要素の列 $(a_0, a_1, \dots, a _ {N-1})$ と区間の列 $\lbrack l_0, r_0), \lbrack l_1, r_1), \dots, \lbrack l _ {Q-1}, r _ {Q-1})$ が与えられたとき、それぞれの区間中の要素の総和 $\sum _ {i \in \lbrack l_j, r_j)} a_i$ を全体で $O(N \sqrt{Q})$ あるいは $O((N + Q) \sqrt{N})$ で求めるアルゴリズムである。ただし、その計算の過程において、群の演算 $\cdot$ が要素 $A \in G$ と添字 $i$ に対し $A \cdot a_i, A \cdot a_i^{-1}, a_i \cdot A, a_i^{-1} \cdot A$ のいずれかの形でしか出現しないという特徴がある。
- Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム (Alien DP; WQS binary search)
- 辺の重みが Monge 性を満たすような完全 DAG について、辺を丁度 $d$ 本使う条件下での $0$-$(N - 1)$ 最短路長を $\Theta (N \log(\max _ {e \in E} \lvert c(e) \rvert))$ で計算する。 ラグランジュ双対問題との強双対性が $c$ の Monge 性から成り立ち、ラグランジュ緩和問題もまた Monge 性を利用して高速に解くことができる。
- Monotone minima
- monotone minima とは、monotone な $H \times W$ 行列に対しその各行の最小値を $O(H + W \log H)$ で求めるアルゴリズムである。
- Montgomery乗算
-
Montgomery 乗算とは、剰余環 $\mathbb{Z}/N\mathbb{Z}$ での乗算を高速に行うアルゴリズムである。
- input
- 剰余環の要素 $a, b \in \mathbb{Z}/N\mathbb{Z}$
- output
- 積 $ab$
- time complexity
- 設定に依存する
- Prim 法
- Prim 法とは、最小全域木を求めるアルゴリズムのひとつ。
- Rabin-Karp 法
- Rabin-Karp 法とは、複数のパターン文字列をまとめて扱える乱択の文字列検索アルゴリズムのひとつ。$k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ のそれぞれについて $\Theta(\sum \vert P_i \vert)$ などをかけてハッシュ値を求めておくことで、与えられたテキスト文字列 $T$ に対し平均 $O(\vert T \vert)$ などでこれらの検索ができる。ハッシュ関数は固定ではないが、ローリングハッシュが使われることが多い。
- SMAWK algorithm (totally monotone minima; TM minima)
- SMAWK algorithm とは、totally monotone な $H \times W$ 行列に対しその各行の最小値を $O(H + W)$ で求めるアルゴリズムである。
- Shortest Path Faster Algorithm (SPFA)
- Shortest Path Faster Algorithm (SPFA) とは、単一始点最短経路問題を解くアルゴリズムのひとつ。Bellman-Ford 法をキューを使って定数倍高速化したものであり、優先度付きキューでなく普通のキューを使う Dijkstra 法のようなものでもある。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。
- Warshall-Floyd 法
- Warshall-Floyd 法とは、全点対間最短経路問題を解くアルゴリズムのひとつ。負閉路が存在するなら検出できる。定数倍の軽い $O(\vert V \vert ^ 3)$ で動く。
- Yen's algorithm
-
Yen's algorithm とは、与えられたグラフ $G$ の $s-t$ 単純路であって $K$ 番目に短いものを $O(K V (E + V) \log V)$ で求めるアルゴリズムである。
- input
- 有向あるいは無向グラフ $G$ とその頂点 $s, t$ および自然数 $K$
- output
- $G$ の $s-t$ 単純路であって $K$ 番目に短いもの
- time complexity
- $O(K V (E + V) \log V)$
- Z algorithm
- Z algorithm とは、与えられた文字列 $S$ に対して、文字列 $S$ の $i$ 文字目以降の文字列 $S\lbrack i \colon \rbrack = (S _ i, S _ {i + 1}, \dots, S _ {\vert S \vert - 1})$ を考えたときの、すべての $i$ について「$S$ と $S\lbrack i \colon \rbrack$ の最長共通接頭辞の長さ」をまとめて $O(\vert S \vert)$ で求めるアルゴリズムのひとつ。
- chokudai サーチ
- chokudai サーチはグラフ探索アルゴリズムのひとつである。ビームサーチを変形したもので、それ以前の実行ですでに探索した頂点を無視しながら、保持する頂点数 $K$ が小さいビームサーチを繰り返し実行する。これには、定数 $K$ の調整を省略する効果と、似通った頂点ばかりを探索することを防ぐ効果がある。
- imos 法
- imos 法とは、配列の区間に対する一様なたくさんの操作をまとめて高速に処理するための手法のひとつ。先に操作の結果として起こる差分だけを書き込んでおき、後からまとめて累積和をとることにより操作を全体に作用させる。
- rerooting (全方位木DP)
- rerooting とは、根付きでない木 $T$ と根付き木の畳み込み $f$ (いわゆる木 DP) が与えられたとき、それぞれの頂点 $r \in T$ に対しそれを根とした根付き木 $T_r$ に対する畳み込み結果 $f(T_r)$ を $O(N)$ ですべて求めるアルゴリズムである。全方位木 DP とも呼ばれる。
- weighted-union heuristic (マージテク; デマテク)
- weighted-union heuristic とは、ふたつの集まりの間で要素を移動させてひとつにまとめる操作を繰り返す際に、常に要素が少ない方から多い方へと移すようにすると計算量が落ちるというテクである。具体的には、大きさ $a$ のものを大きさ $b$ のものへと $O(a)$ かけてマージし (中身を移し) て大きさ $a + b$ のものを作るという操作を使って、大きさの合計が $n$ であるようないくつかのものをひとつにマージしてまとめたいというような状況において、合計の計算量 $O(n \log n)$ でこれが可能である。データ構造をマージする一般的なテクとも呼ばれる。
- しゃくとり法
- しゃくとり法とは、ふたつの添字などを交互に動かして列を走査する手法のこと。
- ダブリング
- ダブリングとは、前処理をしておくことによって操作を複数回繰り返した結果を高速に求めるアルゴリズムのひとつ。事前に固定された関数 $f : N \to N$ に対して、関数 $f^0, f^1, f^2, f^4, f^8, \dots, f^{2^{\lfloor \log K \rfloor}}$ を繰り返し二乗法のようにして $O(N \log K)$ で事前に求めておく。すると、クエリとして与えられた $x \in N$ と $K$ 以下の自然数 $k$ に対して、$f^k(x)$ を $O(\log k)$ で求めることができる。これがダブリングである。ただし $N$ とは集合 $\lbrace 0, 1, 2, \dots, N - 1 \rbrace$ のことであり $f^k : N \to N$ は関数 $f^k(x) = \underbrace{f(f(\dots f(} _ {k ~\text{times}} x) \dots))$ のことである。
- ビームサーチ
- ビームサーチはグラフ探索アルゴリズムのひとつである。与えられたグラフ (たいてい DAG) を初期状態となる頂点群から幅優先探索と同様に探索していくが、定数 $K$ と頂点に対する評価関数 $\varphi : V \to \mathbb{R}$ をあらかじめ固定しておき、各深さごとにその評価関数による評価値が高い順に $K$ 個のみを保持してそれ以外の頂点は無視する。$K = 1$ のときは貪欲法と一致する。焼きなまし法と並んで、ヒューリスティックコンテストで頻繁に利用されるアルゴリズムである。
- 中国剰余定理 (Chinese remainder theorem; CRT; 中国人剰余定理)
- 中国剰余定理とは、任意の互いに素な正整数 $m, n$ に対して、剰余環 $\mathbb{Z}/m n \mathbb{Z}$ と剰余環の直積環 $(\mathbb{Z}/m \mathbb{Z}) \times (\mathbb{Z}/n \mathbb{Z})$ とが $\phi(x) = (x \bmod m, x \bmod n)$ で定まる写像 $\phi : \mathbb{Z}/m n \mathbb{Z} \to (\mathbb{Z}/m \mathbb{Z}) \times (\mathbb{Z}/n \mathbb{Z})$ によって環同型である、という定理のこと。あるいは同じことだが、任意の互いに素な正整数 $m, n$ および任意の整数 $a, b$ に対して、ある整数 $x$ が $m n$ を法として一意に存在して、$x \equiv a \pmod{m}$ かつ $x \equiv b \pmod{n}$ を満たす、という定理のこと。
- 二分探索 (bisection)
-
二分探索とは、ソート済みの列に対する探索アルゴリズムのひとつ。探索すべき区間の中央の要素を調べることで探索すべき区間の長さを半々にし、区間の長さ $N$ に対し $O(\log N)$ で位置を特定する。
- input
- 長さ $N$ のソート済みの列 $a$ と検索対象の要素 $b$
- output
- $b$ が含まれる位置 $i$。あるいは、$b$ を挿入してもソート済みのまま保たれるような区間 $\lbrack l, r)$
- time complexity
- $O(\log N)$ など
- 再帰下降構文解析 (recursive descent parsing)
- 再帰下降構文解析とは、その言語の構文規則に沿った相互再帰的な手続きから構成されるトップダウンな構文解析アルゴリズムのこと。競技プログラミングにおいて要求される構文解析はたいてい再帰下降構文解析で実装できる。
- 動的計画法 (dynamic programming; DP)
- 動的計画法とは、アルゴリズムの分類のひとつ。対象となる問題を複数の部分問題に分割して、部分問題の答えを記録しながらそのすべてを解くという形のアルゴリズムの総称である。動的計画法に分類されるようなアルゴリズムの実装方法の典型例として、配列をループで埋めていく実装や、メモ化を伴なう再帰による実装がある。
- 包除原理
- 包除原理とは、有限集合 $A, B$ について成り立つ $\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert$ という等式のこと。つまり、有限集合 $A, B$ の和集合 $A \cup B$ の要素数を求めるには、$A$ の要素数と $B$ の要素数の和から共通部分 $A \cap B$ の要素数を引けばよいという事実のことである。
- 半分全列挙
-
半分全列挙とは、組合せについて処理するときに使えるテクニックのひとつ。すべての要素を考えたときの組合せの全体は列挙するには多すぎるが、半分程度の数の要素に制限して考えたときの組合せであれば列挙できる、という場合に利用可能である。要素の全体をそれぞれ半分程度の大きさのふたつのグループに分け、それぞれのグループについて組合せを全列挙し、それらふたつの結果を組み合わせて全体に対する結果を得る。そのまま全列挙したときの計算量が $O(f(N))$ であるとき、半分全列挙を行ったときの計算量はたとえば $O(\sqrt{f(N)})$ や $O(\sqrt{f(N)} \log f(N))$ などになる。これを利用するアルゴリズムの代表的なものに baby-step giant-step がある。
- time complexity
- たとえば $O(n)$ のものが $O(\sqrt{n} \log n)$ になる
- 山登り法
- 山登り法はグラフ探索アルゴリズムのひとつである。与えられたグラフ上を初期状態となる頂点から初めてランダムウォークのように探索していくが、評価関数 $\varphi : V \to \mathbb{R}$ をあらかじめ固定しておき、評価値が改善する場合のみ遷移をするようにする。貪欲法の一種である。
- 幅優先探索 (breadth-first search; BFS)
- 幅優先探索とは、グラフや木構造の上の探索に用いられるアルゴリズムのひとつ。
- 平方分割
- 平方分割とは、長さ $N$ の列を長さ $O(\sqrt{N})$ の列 $O(\sqrt{N})$ 個に分割して処理する手法のこと。
- 座標圧縮 (座圧)
-
座標圧縮とは、与えられた長さ $N$ の整数列 $a$ から、長さ $N$ の自然数列 $b$ であって要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるような $b$ を作ること。ただし「要素の順序関係が同じ」とは、任意の $i, j$ に対し $a_i \le a_j \leftrightarrow b_i \le b_j$ を満たすことを言う。このような $b$ は常に一意に存在し、単純な方法により $O(N \log N)$ で構成できる。
- input
- 長さ $N$ の整数列 $a$
- output
- 長さ $N$ の自然数列 $b$ であって、要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるもの
- time complexity
- $O(N \log N)$
- 強連結成分分解
- 有向グラフ $G = (V, E)$ の強連結成分 $C \subset V$ は、全ての $(u, v) \in C^2$ について $u$ から $v$ へ到達可能な極大集合である。$G$ の全ての強連結成分は $V$ の分割になり、これを強連結成分分解と呼ぶ。空間計算量、時間計算量ともに $O(\lvert V \rvert + \lvert E \rvert)$ で構成することができる。
- 数論変換 (number-theoretical transform; NTT; 高速数論変換; fast modulo transform; FMT; 高速剰余変換; 整数環FFT)
- 数論変換とは、特定の素数 $p$ による剰余環 $\mathbb{Z}/p\mathbb{Z}$ の上で行われる離散Fourier変換と同様の変換のこと、あるいはこの変換を高速Fourier変換と同様に $O(n \log n)$ で行うアルゴリズムのことである。
- 深さ優先探索 (depth-first search; DFS)
- 深さ優先探索とは、グラフや木構造の上の探索に用いられるアルゴリズムのひとつ。
- 焼きなまし法
- 焼きなまし法はグラフ探索アルゴリズムのひとつである。山登り法を改良したものであり、評価値が悪化する場合であっても、評価値の変化量と実行開始からの経過時刻などの関数として定まる確率に従ってランダムにそのような遷移を行う。これには局所最適解から抜け出す効果がある。ビームサーチと並んで、ヒューリスティックコンテストで頻繁に利用されるアルゴリズムである。
- 累積和
-
累積和とは、ある数列の接頭辞の総和たちを要素とする数列のこと。長さ $N$ の数列 $a = (a_0, a_1, \dots, a _ {N - 1})$ に対する累積和とは $b_i = \sum _ {j \lt i} a_i$ であるような長さ $N + 1$ の数列 $b$ である。数列の要素が群の要素であるときには区間 $\lbrack l, r)$ の総和 $\sum _ {i \in \lbrack l, r)} a_i = b_r - b_l$ を $O(1)$ で計算することなどに用いることができる。
- input
- 長さ $N$ の数列 $a$
- output
- 長さ $N + 1$ の数列 $b$ (ただし $b_i = \sum _ {j \lt i} a_i$)
- time complexity
- 構築に $O(N)$ で利用に $O(1)$
- space complexity
- $O(N)$
- 繰り返し二乗法
-
繰り返し二乗法とは、与えられた数 $a$ と自然数 $n$ に対し累乗 $a^n$ を $O(\log n)$ 回の乗算で求めるアルゴリズムのひとつ。$1 = a^0, a = a^1, a^2 = a \cdot a, a^4 = a^2 \cdot a^2, a^8 = a^4 \cdot a^4, \dots$ を計算し、これらを適切に掛け合わせることで、合計 $O(\log n)$ 回の乗算で $a^n$ が求まる。競技プログラミングにおいては行列などに対してもよく用いられる。
- input
- 数 $a$ および自然数 $n$
- output
- 累乗 $a^n$
- time complexity
- $O(\log n)$
- 重心分解 (centroid decomposition)
- 重心分解とは、木を分解する手法のひとつである。木からその重心を削除することを再帰的に行う。重心の削除のたびに木の大きさが半分以下になる。分解の過程に沿って重心だった頂点の集合に木構造を入れたとき、元々の木の頂点数を $n$ とすると分解されてできた木の高さが $O(\log n)$ になることを特徴とする。
- 重軽分解 (heavy light decomposition; HL-decomposition; HLD)
- 重軽分解とは、根付き木をパスの集合へ分解するテクニックのひとつである。根から始まる最も長いパスをひとつ選んで削除することを再帰的に行う。元々の根付き木上の親子関係によって分解されたパスの集合に木構造を入れたとき、元々の木の高さを $h$ とすると分解されてできた木の高さが $O(\log h)$ になることを特徴とする。
- 高速 Fourier 変換 (fast Fourier transform; FFT)
-
高速 Fourier 変換とは、離散 Fourier 変換を $O(n \log n)$ で行うアルゴリズムである。高速な多項式乗算の実装などに用いられる。
- time complexity
- $O(n \log n)$
- 高速 Kitamasa 法
-
高速 Kitamasa 法とは、$k + 1$ 項間の線型漸化式で定まる数列の第 $N$ 項を $O(k \log k \log N)$ で求めるアルゴリズムである。Kitamasa 法とは異なる。
- input
- $k + 1$ 項間の線型漸化式で定まる数列 $a$ の漸化式および初めの $k$ 項 $(a_0, a_1, \dots, a _ {k-1})$ および自然数 $N$
- output
- 数列 $a$ の第 $N$ 項 $a_N$
- time complexity
- $O(k \log k \log N)$
- 高速 zeta 変換
-
高速 zeta 変換とは、$n$ 要素の集合 $X$ の部分集合から可換 monoid $M$ への関数 $f : \mathcal{P}(X) \to M$ が与えられたとき、関数 $g(s) = \sum _ {s \subseteq T} f(T)$ の全体を $O(n 2^n)$ で求めるアルゴリズムである。累積和の $n$ 次元への一般化と理解できる。
- input
- $n$ 要素の集合 $X$ の部分集合から可換 monoid $M$ への関数 $f : \mathcal{P}(X) \to M$ のグラフ
- output
- 関数 $g(s) = \sum _ {s \subseteq T} f(T)$ のグラフ
- time complexity
- $O(n 2^n)$