前缀和
令 \(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]\) 。
差分
令 \(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)\))