解題說明
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）？