解題說明
Fancy Sequence
題目描述: 設計一個資料結構 Fancy,支援三種操作:append(val) 將 val 加入序列末尾、addAll(inc) 將序列中所有元素加上 inc、multAll(m) 將序列中所有元素乘以 m。getIndex(idx) 回傳索引 idx 處的值(模 10^9+7)。
解題思路: 如果每次 addAll 和 multAll 都遍歷所有元素,時間複雜度太高。使用延遲計算(lazy propagation):維護全局的乘法因子 mul 和加法因子 add。每次 append 時記錄當時的 (mul, add) 快照,查詢時透過當前全局變換與插入時的快照之間的差異推導出實際值。具體地,對於仿射變換 f(x) = mul*x + add,兩次變換的相對差異可透過模逆元計算。
C++ 解法
複雜度分析
時間複雜度:append 為 O(1),addAll 為 O(1),multAll 為 O(1),getIndex 為 O(log MOD)(模逆元計算)
空間複雜度:O(n) — 儲存 n 個元素及其插入時的快照
虛擬碼
1. Maintain global transform (mul, add): value x becomes mul*x + add 2. append(val): store val and snapshot of current (mul, add) 3. addAll(inc): add = add + inc 4. multAll(m): mul = mul * m; add = add * m 5. getIndex(idx): a. Get snapshot (oldMul, oldAdd) at insertion time b. Compute relative transform: relMul = mul * modInverse(oldMul) c. relAdd = (add - oldAdd * relMul) mod MOD d. Return (val * relMul + relAdd) mod MOD
其他解法
方法二:線段樹 + 延遲傳播 使用線段樹,addAll 和 multAll 作為延遲標記。每次操作 O(log n) 但支援區間查詢。在此題只需單點查詢,過於複雜。
方法三:矩陣表示仿射變換 將 (mul, add) 表示為 2x2 矩陣 [[mul, add], [0, 1]]。組合變換等價於矩陣乘法。概念清晰但實際效率與方法一相同。
延伸思考
- 如果需要支援 getSum(l, r) 查詢區間和,你會使用什麼資料結構?
- 模逆元的計算依賴於 MOD 是質數,如果 MOD 不是質數怎麼辦?
- 如何擴展此設計以支援更多操作(例如 xorAll)?