linear_lca
クラス · 線形前処理・定数時間クエリのLCA
struct linear_lca;
概要
線形前処理・定数時間クエリのLCA
Euler Tourと$\pm1$ RMQ用の線形Sparse Tableを利用する。
計算量
- 構築は頂点数を $n$ として $O(n)$、
lcaは $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
木gを根rとしてLCAを前計算する | $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
lca |
uとvのLCAを返す | $O(1)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator() |
uとvのLCAを返す | $O(1)$ |