以下の内容はhttps://blog.hamayanhamayan.com/entry/2018/01/03/035508より取得しました。
Sparse Table
- 普通のSparse Table
- 結合則と冪等性が成り立つ操作ならば構築O(NlogN),クエリO(1)でできるデータ構造
- 結合則: 順序逆にしても結果が同じ
- 冪等性: 1回やっても複数回やっても結果が同じになる(maxとかはそう)
- セグメントツリーとは異なり更新はできない
- 解説
- Disjoint Sparse Table
- 結合則が成り立つ操作ならば構築O(NlogN),クエリO(1)でできるデータ構造
- 解説
- 2D Sparse Table
- 構築O(NMlogNlogM),クエリO(1)でできる 出典
問題（微妙な問題しかないです）
- 普通のSparse Table
- 2D Sparse Table
- Disjoint Sparse Table
以上の内容はhttps://blog.hamayanhamayan.com/entry/2018/01/03/035508より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14
