PythonでDisjoint Sparse Tableを書いたよ。 - Qiita

class DisjointSparseTable: """Disjoint Sparse Table リストに対して、事前構築O(NlogN)、区間演算O(1)でできます。 演算funcは、結合則を満たすものだけです。 結合則： func(a, b) == func(b, a) (順番は関係なし) Attributes: lst (list): 対象のリスト func (Callable[[int,int],int]): 演算 (xor, gcd, min, max, ...) Examples: >>> dst = DisjointSparseTable([9, 1, 6, 10, 2], min) >>> dst.prod(0, 4) 1 >>> dst.prod(2, 4) 2 >>> def xor(i, j): return i ^ j >>> dst = DisjointSp