スパーステーブル

長さ $2^k$ の区間の結果を前計算しておき、区間を重なりを許す 2 つの区間に分けて答えます。そのため演算は、同じ要素を何度まとめても結果が変わらないもの（min, max, gcd, bitwise or / and など）に限ります。値の更新はできません。

• SparseTable(a, op): 列 $a$ と演算 op（既定は min）から前計算。 $O(N \log N)$
• prod(l, r): op(a[l], ..., a[r - 1])（ $l < r$）。 $O(1)$

コード

class SparseTable:
    def __init__(self, a, op=min):
        # op は min, max, gcd のように、同じ要素を何度まとめても結果が変わらない演算
        self.op = op
        self.table = [list(a)]
        k = 1
        while 2 * k <= len(a):
            prev = self.table[-1]
            self.table.append([op(prev[i], prev[i + k]) for i in range(len(prev) - k)])
            k *= 2

    def prod(self, l, r):
        # op(a[l], ..., a[r - 1])（l < r）
        k = (r - l).bit_length() - 1
        t = self.table[k]
        return self.op(t[l], t[r - (1 << k)])