Sparse Table（稀疏表）
稀疏表預先儲存長度為 2 的冪次的區間資訊，適合陣列不變、需要反覆查詢的情況。以下兩個 Python 模板分別示範區間最大值與區間和；索引從 0 開始，查詢使用閉區間 [l, r]，並假設輸入非空且索引有效。
區間最大值查詢
st[i][j] 儲存從 j 開始、長度為 2**i 的區間最大值。建表時間與空間皆為 \(O(n\log n)\)；查詢以兩個可重疊的區間覆蓋目標範圍，時間為 \(O(1)\)。
class SparseTable:
def __init__(self, arr):
n = len(arr)
log2 = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
log2[i] = log2[i // 2] + 1
self.log2 = log2
st = [[0 for _ in range(n)] for _ in range(log2[n] + 1)]
for i in range(n):
st[0][i] = arr[i]
for i in range(1, log2[n] + 1):
for j in range(n - 2 ** i + 1):
st[i][j] = max(st[i - 1][j], st[i - 1][j + 2 ** (i - 1)])
self.st = st
def range_max_query(self, l, r):
range_length = r - l + 1
log2_l = self.log2[range_length]
return max(self.st[log2_l][l], self.st[log2_l][r - 2 ** log2_l + 1])
j + 2**(i - 1)，與上方圖示及程式一致。區間和查詢
區間和不能重複計算重疊部分，因此把查詢長度拆成二進位所對應的互不重疊區間。建表時間與空間仍為 \(O(n\log n)\)，每次查詢為 \(O(\log n)\)。
class SparseTable:
def __init__(self, arr):
n = len(arr)
log2 = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
log2[i] = log2[i // 2] + 1
self.log2 = log2
st = [[0 for _ in range(n)] for _ in range(log2[n] + 1)]
for i in range(n):
st[0][i] = arr[i]
for i in range(1, log2[n] + 1):
for j in range(n - 2 ** i + 1):
st[i][j] = st[i - 1][j] + st[i - 1][j + 2 ** (i - 1)]
self.st = st
def range_sum_query(self, l, r):
range_length = r - l + 1
s = 0
index = l
for i in range(range_length.bit_length()):
if range_length >> i & 1:
s += self.st[i][index]
index += 2 ** i
return s
區間和示意圖
