SparseTable
1. Sparse Table
(1) 概要
数列（リスト）に対して，指定区間における最小値／最大値等の演算を求めるクエリにO(1)で解答するためのデータ構造
データ構造の作成には，O(NlogN)必要
前提：数が不変（変化する場合は，セグメント木を使う）
可能な演算例：最小値，最大値，最大公約数，最小公倍数
不可能な演算例：四則演算
参考：https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table
(2) 実装例（コンテスト問題未検証）
code:python
# 区間最小値．参考ページを基に，numpyが使えない環境でも動作するように変更
# 参考：https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table
class SparseTable:
def __init__(self, a):
n = len(a)
max_k = n.bit_length() - 1 # 幅が2^0, 2^1, 2^2, ..., 2^{max_k}の区間を作る
INF = float('inf')
table = [INF * n for _ in range(max_k + 1)] # tableki: 幅2^kのi番目の区間における最小値
table0 = a # 幅1の区間の最小値は，元の値そのもの
last_width = 1
for k in range(1, max_k + 1):
width = 1 << k # 区間幅
for i in range(n - width + 1):
# 現在の区間の最小値 = min(区間の前半分の最小値，区間の後半分の最小値)
tableki = min(tablek-1i, tablek-1i + last_width)
last_width = width
self.table = table
def query(self, l, r):
""" min value of l, r """
width = r - l + 1 # 区間幅
if width == 1:
return self.table0l
k = width.bit_length() - 1
width = 1 << k # tableで使用する区間幅．区間幅を超えない最大の2のべき乗
# 左端から幅2^kを取った区間と，右端から幅2^kを取った区間の最小値
return min(self.tablekl, self.tablekr - width + 1)
a = 1, 4, 8, 5, 9, 2, 3
st = SparseTable(a)
print(st.query(0, 2)) # a0～a2の最小値 ... 1
print(st.query(1, 3)) # a1～a3の最小値 ... 4
print(st.query(1, 6)) # a1～a6の最小値 ... 2
print(st.query(6, 6)) # a6～a6の最小値 ... 3
#SparseTable #データ構造