差分
このページの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 | ||
---|---|---|---|
行 64: | 行 64: | ||
- | ここで、区間の最小値を求めるクエリが発生する。以下の2つがよく使われている? | + | ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 |
+ | * 平方分割 | ||
* セグメント木 | * セグメント木 | ||
* Sparce Table | * Sparce Table | ||
+ | |||