2018-01-03 競技プログラミングにおけるSparse Table問題まとめ 競技プログラミング 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 CF361 Friends and Subsequences CODE FESTIVAL 2014 予選B 登山家 解説 KUPC2015 MODクエリ 解説 HR The Strange Function （区間gcd） 2D Sparse Table CF015 Map CodeChef Chef and Rectangle Array CF371 Animals and Puzzle 解説 解説2 AOJ School of Killfish Disjoint Sparse Table CC Product on the segment by modulo （総積）
