前缀和与差分

前缀和

令 \(s[i] = a[1] + a[2] + ... + a[i]\) ，此时的 \(s\) 数组就为 \(a\) 数组的前缀和。

实现：
每个 \(s[i]\) 都可由 \(s[i - 1] + a[i]\) 转换来，顺序处理即可。

代码：

for(int i = 1; i <= n; ++ i){
	s[i] = s[i - 1] + a[i];
}

应用：
常用于求区间和。即 \(a[l] + a[l + 1] ... + a[r] = s[r] - s[l - 1]\) 。

习题：
LOT-A Journey to Mars

差分

令 \(b[i] = a[i] - a[i - 1]\) ，此时的 \(b\) 数组就为 \(a\) 数组的差分数组。因为有 \(b[1] + b[2] + ... + b[i] = a[i]\) ，即 \(a\) 数组为 \(b\) 数组的前缀和。

代码：

for(int i = 1; i <= n; ++ i){
	b[i] = a[i] - a[i - 1];
}

应用：
用于进行快速的区间加。即若将 \(a\) 数组的 \(l - r\) 项同时加上 \(k\) ，等同于 \(b[l] += k\) 且 \(b[r + 1] -= k\) 。最后将 \(b\) 数组进行前缀和得出的即为要求的 \(a\) 数组。

习题：
语文成绩

前缀和于差分

在区间加问题中，前缀和做法为修改 \(O(n)\) ，查询 \(O(1)\) ；而差分做法为修改 \(O(1)\) ，查询 \(O(n)\) 。
可按题目要求在两种做法中进行选择。
折中算法：树状数组（修改 \(O(logn)\) ，查询 \(O(logn)\)）