Disjoint Sparse Table
(data-structure/disjoint_sparse_table.hpp)
Description
Disjoint sparse table は,モノイド $(T, \cdot, e)$ の静的な列の区間積を高速に計算するデータ構造である.Sparse table と違って二項演算 $\cdot$ に冪等性を要求しない.
空間計算量: $O(n \log n)$
Operations
-
DisjointSparseTable(vector<T> v)
-
v
の要素から disjoint sparse table を構築する
- 時間計算量: $O(n \log n)$
-
T fold(int l, int r)
- 区間 $[l, r)$ の値を fold する
- 時間計算量: $O(1)$
Reference
Required by
Verified with
Code
Back to top page