【演算法】前綴和（Prefix Sum）

簡介

前綴和可記錄 0~n 的總和，在求區間和或者要使用差分轉原數列時會用到。

應用

區間和、差分陣列轉原陣列時

原理：前綴和

index	0	1	2	3	4	5
原 Array	1	2	3	-5	7	-3
前綴和 sum	1	3	6	1	8	5

這時區間和就運用到數學的和差公式：$\displaystyle\sum_{i=1}^{b}{x_i}-\displaystyle\sum_{i=1}^{a}{x_i}=S_b-S_a$

取 index 區間和 $[2, 4]$ 答案會是 sum[4] - sum[1]

快速總結：取 index 區間和 $[a, b]$ 公式就是 sum[b] - sum[a - 1]

所以在輸入陣列時，我們可以一起記下前綴和。

int n, q;
cin >> n >> q;
int arr[n];
int sum[n + 1] = {0};
for (int i = 0; i < n; i++) {
    cin >> arr[i];
    (i == 0) ? (sum[i + 1] = arr[i]) : (sum[i + 1] = arr[i] + sum[i]);
}

初始化完後，就可以直接計算詢問的區間和。

while (q--) {
    int a, b;
    cin >> a >> b;
    ll ans = sum[b] - sum[a - 1];
    cout << ans << "\n";
}

題目

• CSES Static Range Sum Queries