- 2020.04.18
- C#, SparseTable, アルゴリズム, データ構造,
SparseTable の実装と解説 [C#]
Sparse Table とは Sparse Table とは、静的なデータに対して、範囲最小クエリ(RMQ)に答えることができるデータ構造です。 RMQ に答えることができるデータ構造に Segment Tree がありますが、データの変更に対応できるかどうかという点で異なります。Sparse Table はデータの変更はできない代わりに、前計算を行った上でRMQに O(1) で答えることが可能 […]