← 返回首頁
Prefix Sum 前綴和 & 差分陣列
前綴和
差分陣列
陣列：
Build 建立前綴和
查詢 [L, R]：
L:
R:
Query 查詢區間和
陣列長度：
Init 初始化
區間 [L, R] += val：
L:
R:
val:
Add 區間加值
Restore 還原陣列
前綴和 - 建立動畫
前綴和 vs 差分陣列
前綴和：
O(n) 預處理，O(1) 區間查詢
差分陣列：
O(1) 區間更新，O(n) 還原
互為逆運算：
差分陣列的前綴和 = 原始陣列