前缀和思想

发表于 分类于 ，

前缀和的定义:

对于一个数组 a [i], 定义一个数组 sum [i], 其中 sum [0]=0, sum [i]=(a [1]+a [2]+…+a [i]), 则 sum 称为 a 的前缀和

前缀和的作用:

对于无修改数组的查询区间和，可以在边读入数据时边处理前缀和， 然后在 O(1) 的时间下回答每个询问，预处理 O (n). 具体做法就是求出前缀和后对于询问 [l,r] 的区间和直接计算 sum [r]-sum [l-1]. 

1
2
3
4
5
6
7
8
9
10
11
12
int n,m;
int a[],sum[];
for(int i(1);i<=n;++i)
{
    scanf("%d",a+i);
    sum[i]=sum[i-1]+a[i];
}
while(m--)
{
    int l,r;
    cout << sum[r]-sum[l-1];
}
但前缀和主要是一种思想， 对于符合区间减法的查询在 O (n) 的预处理后可在 O (1) 下回答

下面拿今天做的题目举个例子:

给出一个只包含 0 和 1 的字符串，可以将某一位上的数取反 (即 0 变成 1, 1 变成 0), 要使得最后得到的串中所有 0 都在 1 的前面， 至少要几次取反？

样例：输入：010001 输出：1

可以考虑枚举最后得到串中 0 串的长度，在这个长度前面的所有 1 变成 0, 后面的所有 0 变成 1, 每次更新最少改变次数

用前缀和预处理串中某个位置 i 之前的 0/1 的个数 , 记为 S0 和 S1, 则 0 串长度为 i 的改变次数为 S1 [i]+S0 [n]-S0 [i-1](0<=i<=n)

时间复杂度 O (n), 原数据范围为 n<=1e5, 完全可过

从暴力枚举 0/1 个数的 O (n^2) 到 O (n) 是个不小的优化， 所以说前缀和思想是个很有用的优化思路

二维前缀和

相比于一维的前缀和，二维前缀和多了一维，处理起来稍微麻烦一点

对于一个二维数组 a [i][j], 设 sum [i][j]=(a [1][1]+a [1][2]+…+a [1][j]+a [2][1]+…+a [2][j]+…+a [i][j]), 则 sum [i][j] 为 a [i][j] 的二维前缀和

可以根据容斥原理来处理二维前缀和

对于 sum [i][j], 有 sum [i][j]=sum [i-1][j]+sum [i][j-1]-sum [i-1][j-1]

二维区间和 w (x1,y1,x2,y2)=sum [x2][y2]-sum [x2][y1]-sum [x1][y2]+sum [x1][y1]