前缀和思想

发表于 | 分类于 ，

前缀和的定义:

对于一个数组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]