靜態區間的另一種取捨
線段樹能支援更新;若陣列固定,預處理則可以用兩個儲存值回答最小值查詢。我們先推導表格及假設,再比較成本。
設 為不變陣列,含 個來自全序集合的值。查詢使用包含端點的索引 。每次比較和陣列存取計為常數時間,並假設表格索引與預先計算的對數值可放入機器的字長模型。
定義 2.1.1
(稀疏表的表項)
對每個滿足 的 ,及有效起點 ,定義
第 行恰有 個有效項。不儲存超出陣列的區間。
建立不變量
定理 2.1.2
(二的冪長度區間)
以 建表,對 使用
每個有效表項便等於所述區間的最小值。
證明
(對行號作歸納)
基礎行儲存每個長度為一的區間。有效的長度 區間,在上述起點分為兩個互不相交、長度為 的區間。因整段有效,兩項都存在。歸納假設表示它們儲存兩個最小值,取其較小者即得並集的最小值。∎
建表有 行,每行至多 項:時間和儲存量為 。可用 、對 令 ,在 時間建立 的 表。
用重疊區塊回答查詢
定理 2.1.3
(雙區塊查詢)
設 ,,,。則 與 都存在,並且 。
證明
(兩個覆蓋區塊)
對查詢令 、、,則 。長度為 的區間 和 都位於 內,且覆蓋整段,可能有重疊。因此
同時位於兩個區塊的索引會被考慮兩次,但 ,所以最小值不變。當 時兩個區塊相同,這同樣有效。
證明透視
使兩個區塊有效的兩個不等式
一切取決於兩個不等式。區塊落在 內,是因為 ,這也說明兩個儲存項都存在,且不含外部元素。區塊能覆蓋 ,是因為 :右區塊起點 ,不晚於左區塊的最後一個索引,所以沒有索引被漏掉。 取小一些就會留下空隙,取大一些就會有區塊伸出查詢範圍; 是同時滿足兩者的唯一選擇。冪等性只用於第二個不等式所保證的非空重疊。
使用預先計算的對數表,查詢只需兩次讀取和一次比較,在所述模型下為 。此保證用於靜態陣列;賦值可能使許多表項失效。重建整表是一個簡單有效的處理方法,而線段樹專為不必重建地處理單點賦值而設。
常見錯誤
(把對數向上取整)
取 會使 ,除非 是二的冪,否則 。當 時區塊長度會是 ,比查詢還長,區塊便包含 以外的元素,而且該表項未必存在。必須向下取整,因為每個區塊都得落在查詢範圍之內。
常見錯誤
(第二個區塊的起點差一)
第二個區塊的起點是 ,而不是 。在下面的六個值例子中,查詢 的 ;若從 開始,就重複了區塊 ,回傳 ,漏掉索引 的值 。
例題 2.1.4
(六個值的陣列)
取 。第零行是原陣列,第一行為 ,第二行為 。查詢 長度為五,。左區塊 的最小值是 ,右區塊 的最小值是 ,所以返回 。兩者重疊的 對最小值無害。
例題 2.1.5
(恰好是一個區塊的查詢)
再用 。查詢 的 、、,兩個區塊都是 :公式為 ,即 與 的最小值。單點查詢 的 、、,公式為 。兩種情形中兩個區塊都重合,冪等性使儲存的值原樣回傳。
例題 2.1.6
(逐行倍增建表並回答一個查詢)
設 ,故 。第一行有七項:。第二行合併相距二的兩項:、、、、,得 。第三行只有一項 。查詢 的 、、;兩個區塊是 和 ,儲存的最小值為 與 。答案是 ,與直接取 的最小值一致。
反例模式
過期的表格
為六個值的陣列 建立表格後,將 由 改為 ,卻不更新表格。舊查詢仍返回 ,但 的新最小值為 。不變量適用於建表時的陣列;賦值後必須更新或重建儲存數據。
結合律與冪等性,分別支持哪一步?
定義 2.1.7
(有關的代數性質)
值域上的二元運算 滿足結合律,表示
冪等性則表示 。區間聚合依原本由左至右次序合併元素。
最小值具有兩項性質。最大值、正整數最大公因數,以及通常值域上的逐位 AND、OR 亦然。加法有結合律,但不冪等。
命題 2.1.8
(重疊區塊是安全的)
設 滿足結合律與冪等性。設被查詢的序列是連續各段 的串接,其中 非空;並以 同時表示各段的聚合值,外側某段為空時省略它。若一個儲存區塊聚合 ,另一個聚合 ,則 。
證明
(先重新分組,再吸收重疊)
把查詢分成連續三段 ,其中 是非空重疊。第一塊聚合 ,第二塊聚合 。以下字母表示各段聚合值。利用結合律,
第二步以冪等性消去重複的重疊聚合值。若外側某段為空,略去它即可; 始終非空。兩塊完全重合時,就是 。
證明透視
每個假設在哪一步發揮作用
證明有兩個動作。第一,結合律把四個因子 重新分組,而不移動其中任何一個。第二,冪等性把 合併;只有這一步用到它,而且它作用於重疊部分的聚合值,並非作用於 或 的單個元素。去掉任一假設都會破壞不同的一步,這個區塊之後的兩個反例就是明證:加法在第二個動作失效,平均運算則在第一個動作失效。
不同段的順序從沒有改變,所以不需交換律。結合律支持區塊分組,冪等性移除重複,兩項責任不可混淆。
兩個假設可以分別去掉,而每一種去法都會給出具體的錯誤答案。
反例模式
對區塊和使用同一公式,會重複計算重疊
取 [3, 1, 4, 1, 5, 9, 2],查詢 [1, 5]。長度五,兩塊為 [1, 4] 及 [2, 5],和分別是 11、19,相加得到 30。
真正區間和為 20。重疊 [2, 4] 的和是 10,計了兩次。加法容許重新分組,卻不能消除重複數據。即使查詢恰是一個冪次區塊,把同一區塊和加兩次仍會倍增。
反過來的失敗同樣真實:冪等性無法彌補缺少的分組性質。
反例模式
只有冪等性,仍不足以支持任意聚合
冪等,但沒有結合律:,而 。
陣列 [0, 0, 6] 的兩個長二區塊平均值為零及三,再平均得到 ,真正整段平均卻為二。若區塊分組本身缺少所需性質,不能只憑冪等性便套用重疊查詢。
對有結合律但不冪等的運算,普通稀疏表仍可用不重疊分解回答。例如長十三可依次切成八、四、一。二元展開最多有 塊,所以此方法需 次合併。沒有交換律時須保留由左至右次序;沒有單位元時可由第一塊初始化累積值。這是另一個有效方法,沒有宣稱重疊公式仍然成立。求和若有減法,前綴和亦提供更簡單方案。
使用整數對數的完整實作
類別保存非空輸入序列的建立時快照,各行只含有效起點。預先計算整數對數表,查詢時不使用浮點對數。值必須具有全序,例子使用整數。
class SparseMin:
def __init__(self, values):
base = list(values)
if not base:
raise ValueError("sparse table requires a nonempty array")
self.n = len(base)
self.logs = [0] * (self.n + 1)
for length in range(2, self.n + 1):
self.logs[length] = self.logs[length // 2] + 1
self.table = [base]
span = 2
while span <= self.n:
half = span // 2
previous = self.table[-1]
row = [min(previous[i], previous[i + half])
for i in range(self.n - span + 1)]
self.table.append(row)
span *= 2
def query(self, left, right):
if not 0 <= left <= right < self.n:
raise IndexError("query must be a nonempty in-bounds interval")
k = self.logs[right - left + 1]
span = 1 << k
return min(self.table[k][left],
self.table[k][right - span + 1])
兩個查詢項目都存在,因所選區塊完全在有效查詢內。單元素查詢使用第零行,同一個值合併兩次。例子的 SparseMin(values).query(1, 5) 傳回一。前處理及儲存為 ;在索引及值運算為常數時間的標準模型中,每次查詢為 。
行數為對數,不代表更新也只需對數時間
改動位置 ,同一行也可能有多塊受影響。長度 時,每個有效起點 都可能要重算,至多有 個。各層相加,潛在受影響項目少於 ,但這是線性而非對數界。
對明確儲存的表,最壞確實是線性。設 為二的冪,零起始位置 ,全部值原本為一。把該點改為零。在長 的行,起點 的全部 塊都含該點,最小值全部改變。
因此,只更新受影響項目也可需 ;重建全部行則為 。本類別提供靜態查詢,沒有更新方法。頻繁更新需選擇配合該介面的結構,例如本課程的線段樹主題。
想傳回最左位置,就要儲存足夠資訊
若查詢需要最小值的位置,儲存 並以字典序比較:先比值,值相同再比索引。此二元組最小運算仍具結合律及冪等性,所以全部證明仍成立。
對 [4, 1, 3, 1, 2] 的 [0, 4],結果為 ,選最左最小值,而非索引三的相等值。同一類別可接收 [(value, index) for index, value in enumerate(values)]。若只儲存最小值,位置資訊早已被丟掉。
習題
快速檢查
(對 ,建立最小值表的第零、一、二行。)
第 行合併第 行中相距 的兩項。
解答 · 答案
各行為 、 和 。
快速檢查
(用該表回答查詢 ,並指出查詢的兩個區塊。)
先算 ,再算 與 。
解答 · 答案
長度為三,故 。區塊 和 的最小值為 和 ,答案是 。
快速檢查
(為何長度恰為 的區間 可以使用同一區塊兩次查詢?)
當 時,兩個區塊是甚麼?
解答 · 答案
兩個區塊都等於整段,且 。
快速檢查
(設 。表有多少行?最後一行有多少項?建表、儲存和查詢的界各是多少?)
滿足 的最大 決定最後一行。
解答 · 答案
因為 ,各行為 ,共 行。最後一行有 項。建表和儲存為 ;預先計算對數表並假設存取與比較為常數時間時,查詢為 。
延伸閱讀
Algorithms for Competitive Programming:Sparse Table 討論二的冪長度區間表。