前綴和
前綴和：陣列前 n 項的和。
用途：快速計算區間 [l, r] 的和。
時間複雜度：O(n) 降到 O(1)。
#include <iostream>
using namespace std;
int main(){
int n = 5;
int a[n] = {1, 2, 3, 4, 5};
int b[n];
b[0] = a[0];
for(int i=1; i<n; i++){
b[i] = b[i-1] + a[i];
}
// 1 3 6 10 15
int l = 1, r = 3;
cout << b[r] - b[l-1];
}差分
差分：陣列相鄰兩項的差值。
用途：快速在區間 [l, r] 加上一個數字 x。
時間複雜度：O(n) 降到 O(1)。
#include <iostream>
using namespace std;
int main() {
int n = 5;
int a[n] = {1, 2, 3, 4, 5};
int d[n];
d[0] = a[0];
for(int i = 1; i < n; i++){
d[i] = a[i] - a[i-1];
}
int l = 1, r = 3, x = 10;
d[l] += x; // 使得從 l 之後，都會加 x
d[r + 1] -= x; // 從 r + 1 之後，不應該繼續加 x，所以減回 x
// 1 11 1 1 -9
a[0] = d[0];
for(int i = 1; i < n; i++){
a[i] = a[i-1] + d[i];
}
for(int i = 0; i < n; i++){
cout << a[i] << ' ';
}
}