前缀和算法

AcWing算法-前缀和

---

---

前言

一、什么是前缀和?

需要注意的是下标要从1开始，之前我们的数列数组大多都是从下标0开始，但是这里需要从1开始，理由下面会阐述。

二、三个关键问题

1.如何求前缀和

如果这样直接求前缀和的话时间复杂度是O(n)。

2.前缀和算法的作用

快速计算一段区间上的和，比如 [ l,r ].
我们先写出公式：

现在证明一下：

我们发现两式相减就是从[l,r]上的和。

3.解释一下下标问题

上面就提到前缀和算法的下标应该注意从1开始，在这里我说明一下这样处理的原因：
原因就是下标从1开始，这样S0=0，目的是为了处理边界。这句话不太好理解，我来举个例子帮助大家理解：

三、一维前缀和模板

S[i] = a[1] + a[2] + ... a[i] 
a[l] + ... + a[r] = S[r] - S[l - 1]
1
2

一维的板子很好记，就是要注意区间左边如果是闭区间，就要左端点-1，即 S[l - 1];

四、一维前缀和实战

代码如下：

#include 
#include
using namespace std;
const int N=1e5+10;
int a[N],sum[N];
int main()
{
    int n,m,x;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=x+sum[i-1];
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五、二维前缀和

1.什么是二维前缀和

我们先从数学的角度来说，一维可以理解为一条线，而二维就是一个平面，一位前缀和是在一个线段上所有的点的和，二维前缀和就是在某个特定平面内所有点的和，现在我用图来帮助大家理解：

二维前缀和要注意容斥原理，一定要小心别多减去某区域的和。

2.二维前缀和模板（子矩阵的和）

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
1
2
3

六、二维实战

#include 

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

总结

今天给大家分享了前缀和的一维和二维情况，同时对于不好理解的地方也进行了画图讲解，希望可以对大家有所帮助，如果有什么地方存在错误欢迎大家指正，我们明天见~