差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/28] – [EulerTour + RMQ] ikatakos | programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/28] – [EulerTour + RMQ] ikatakos | ||
|---|---|---|---|
| 行 33: | 行 33: | ||
| ==== EulerTour + RMQ ==== | ==== EulerTour + RMQ ==== | ||
| - | オイラーツアーで頂点を記録していく。また、その過程で以下の情報も記録していく。 | + | オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。 |
| * '' | * '' | ||
| - | * $i = 0 ～ 2(N-1)$ について、$i$ 番目に通りがかる頂点の（深さ, | + | * $i = 0 ～ 2(N-1)$ について、$i$ 番目に通りかかる頂点の（深さ, |
| * '' | * '' | ||
| * 頂点 $v$ の深さ | * 頂点 $v$ の深さ | ||
| 行 64: | 行 64: | ||
| - | ここで、区間の最小値を求めるクエリが発生する。以下の2つがよく使われている？ | + | ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 |
| + | * 平方分割 | ||
| * セグメント木 | * セグメント木 | ||
| * Sparce Table | * Sparce Table | ||
| + | |||
