題幹與適用場景
請實作一個支援歷史版本的整數陣列結構。每次更新只修改一個位置，查詢可以指定任意舊版本的閉區間和。要求舊版本不可變，說明座標範圍、時間複雜度、空間複雜度、版本分叉與測試策略。
這是一道偏難的資料結構題，考察遞迴分治、結構共享、不可變更新、邊界處理與複雜度證明。題目假設陣列長度固定，更新是單點賦值，查詢是閉區間 [l, r] 求和。若需要區間加、刪除或合併版本，應先說明那是不同的擴充。
面試官考察點
面試官希望看到候選人先確認「持久化」代表舊根仍可查詢，而不是複製整棵樹。高品質實作會為更新路徑建立新節點，重用未受影響的子樹，並保存每個版本的根。還要說明半開或閉區間約定、空查詢、版本編號、負數、越界與空間上限。
回答前需要釐清的問題
- 陣列長度與座標是否固定？是否可以先做座標壓縮？
- 更新是賦值還是加法？是否允許同一位置重複更新？
- 查詢區間是閉區間還是半開區間？空區間返回什麼？
- 版本只能從最新版本追加，還是可以從任意舊版本分叉？
- 是否要求執行緒安全、持久化到磁碟或跨程序共享？
- 需要精確整數和，還是允許溢位檢測或大整數？
- 版本數量與總操作數上限是多少？
30 秒回答框架
「我會把每個版本表示為一棵不可變線段樹的根。單點更新沿根到葉複製 O(log n) 個節點，未經過的兄弟子樹直接共享；查詢從指定版本根遞迴，完全覆蓋時返回節點和。根陣列支援從任意舊版本分叉。建樹 O(n)，每次更新與查詢 O(log n)，總空間是初始節點加每次更新新增的 O(log n) 節點。我會用版本分叉、邊界、負數與隨機對照測試驗證實作。」
分步驟深入解答
先固定不變量：節點覆蓋明確閉區間 [lo, hi]，sum 等於該區間在目前版本的元素和；葉節點覆蓋一個位置；內部節點的和等於左右子節點之和；節點建立後不再修改。每個版本只保存一個根指標。
陣列下標若是 0..n-1，可用遞迴建樹。若輸入是稀疏的大整數座標，先收集可能座標並壓縮，再在壓縮索引上建樹；不要把巨大座標範圍直接展開成陣列。
以下偽代碼使用賦值更新與閉區間查詢：
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] 保存初始建樹結果。若從版本 base 更新位置 i，建立 roots[next] = set(roots[base], 0, n - 1, i, value)。因此版本圖是一棵根陣列指向的有向無環共享結構，而不是線性歷史鏈。版本分叉只需把任意舊根作為輸入，不應把更新強制綁定到最新版本。
邊界必須明確處理：n == 0 時不建立根；索引越界與 ql > qr 應返回結構化錯誤或依題目約定處理；查詢區間可先裁剪，但不能悄悄改變呼叫者錯誤。計算 mid 時避免 lo + hi 溢位，在固定整數範圍可寫成 lo + floor((hi - lo) / 2)。
初始建樹需要 O(n) 節點與 O(n) 時間。每次單點更新只複製一條根到葉路徑，因此新增 O(log n) 節點；查詢訪問 O(log n) 個規範區間，時間為 O(log n)。執行 u 次更新後總空間是 O(n + u log n)，而不是 O(nu)。若更新是區間賦值或區間加，仍可路徑複製，但延遲標記、節點合併與空間分析會改變。
節點不可變是正確性的核心。不要在更新時修改原節點的 sum 或子指標，否則舊版本會被污染。實作可以使用垃圾回收或引用計數；若需要手動釋放，必須知道每個版本根的生命週期，不能因刪除一個版本就遞迴釋放仍被其他版本共享的節點。
若只需要最新版本，普通線段樹更簡單。只有需要歷史查詢、回滾、分支實驗或時間旅行時，持久化帶來的空間成本才合理。若所有操作都是離線，也可以考慮離線前綴或掃描線；回答應把資料結構選擇與查詢模式連起來。
測試先用小陣列窮舉。每次更新後，用普通陣列複製出新版本，並對隨機版本、隨機區間比較線段樹結果。重點覆蓋從版本 0 分叉、連續更新同一位置、負數、單元素、全區間、單點、空區間、最左與最右邊界。再加入共享檢查：更新一個位置後，另一側子樹的物件身分應保持不變。
測試還要驗證版本不可變。保存每個舊版本的所有查詢結果，執行多次分叉更新後重新查詢；任何舊結果變化都表示節點被錯誤修改。對大規模操作統計節點數量，確認它接近初始 O(n) 加每次更新 O(log n)，避免意外複製整棵樹。
高品質示範回答
「我先假設陣列長度固定、更新是單點賦值、查詢是閉區間求和，而且版本可以從任意舊版本分叉。每個節點覆蓋 [lo, hi] 並保存區間和；節點建立後不再修改。roots[v] 保存版本 v 的根。
建樹時遞迴拆分區間。更新時沿根到目標葉複製路徑：目標方向建立新子節點，另一側直接重用舊指標，最後用兩個子節點的和建立新父節點。查詢從指定版本根出發，越界返回 0，完全覆蓋返回節點和，否則遞迴左右子區間。
建樹是 O(n) 時間與空間。每次更新新增 O(log n) 節點，查詢與更新都是 O(log n)；執行 u 次更新後總空間是 O(n + u log n)。舊根仍指向舊節點，所以任意舊版本都不會被新更新污染。若座標很大，先做座標壓縮；若需要區間更新，我會重新評估延遲標記與空間成本。
我會測試版本 0 分叉、連續更新同一點、負數、空區間與所有邊界，並用普通陣列作隨機對照。還會檢查未受影響子樹仍被共享，以及新版本更新後舊版本查詢結果保持不變。若只查詢最新值，我會選擇普通線段樹，只有歷史查詢與回滾需求才承擔持久化成本。」
常見錯誤
- 複製整棵樹 → 每次更新變成 O(n) 空間 → 只複製根到葉的路徑。
- 修改舊節點再保存新根 → 所有引用該節點的舊版本都會改變 → 節點建立後保持不可變。
- 把版本當線性鏈 → 不能從任意舊版本實驗或回滾 → 根陣列允許版本分叉。
- 忽略區間約定 → 閉區間與半開區間混用會造成邊界錯誤 → 在不變量與函式簽名中固定一種約定。
- 把大座標直接建樹 → 座標範圍遠大於實際點數會浪費空間 → 先做座標壓縮或使用動態節點。
- 聲稱空間是 O(n) → 忽略每次更新都會新增路徑節點 → 寫出 O(n + u log n) 的總空間。
- 刪除版本時遞迴釋放共享節點 → 其他版本可能仍引用這些節點 → 使用引用計數或垃圾回收策略。
追問及應對
追問 1：如果更新是區間加，結構還成立嗎？
可以路徑複製覆蓋更新區間訪問的節點，並複製相關路徑；若使用延遲標記，標記也必須屬於新節點，不能寫入共享節點。新增節點數量可能是 O(log n) 到 O(log n 加覆蓋節點數)，要根據實作給出邊界，不能直接沿用單點更新的空間結論。
追問 2：如何支援查詢兩個版本之間的差異？
同時遍歷兩個根。若兩個節點指標相同，該子樹沒有變化，可以直接跳過；否則繼續向下或按聚合值計算差異。若要報告所有變更位置，複雜度還取決於輸出數量。
追問 3：為什麼不直接複製陣列再做前綴和？
複製陣列每次更新是 O(n) 空間與時間。若版本少且陣列小，簡單方案可能更合適；持久化線段樹在大量版本、線上歷史查詢與局部更新下用 O(log n) 新增空間換取效能。
追問 4：版本根如何持久化到磁碟？
節點需要穩定 ID，子指標改為 ID，根表記錄版本到根 ID 的映射。寫入採用追加或寫時複製，並在提交根之前保證新節點已持久化。恢復時先校驗節點引用與根表，不能把記憶體位址直接序列化。
追問 5：如何證明舊版本不會被污染？
歸納每次更新：只有新節點被建立，任何舊節點的欄位不變；新樹只引用舊的未變子樹與新建的變更路徑。因此舊根可達的節點集合及其值保持不變。測試再用隨機分叉對照驗證這個不變量。