一维/二维前缀和

· · 个人记录

一维/二维 前缀和

一维前缀和干什么用？

一维前缀和，用于数组中求1 至 x 的和 (通常是多测,可循环利用),能够大大减少时间复杂度，从O(nm) 直降到O(n + m)（具体原因见后）。

可是，我们的前缀和怎么做到捏？我们可以推一下捏:

我们先定义一个数组 a, 里面的数（下标从 1 开始）分别为：1, 2, 3, 4, 我们遍历算一下，它们从1 ~ 4 的和分别是 1, 3, 6, 10 你品，发现么，第 1 ~ i 个数的所有和，就是1 ~ i - 1 的和 + a_{i} 。那么，思路就非常简单，我们用个数组 sum 来记录当前 1 ~ i 的和,然后递推就可以实现。

code: 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 1e7 + 5; // 成习惯了,真戒不掉QAQ 
int n, m, a[MAXN];    
ll sum[MAXN]; // 前缀记录数组 

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);  
    sum[0] = 0; // 全局变量,其实不写也行 
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i]; // 用递推的思想, 因为a[1]~a[i](sum[i])的和一定是a[1]~a[i - 1]的和(sum[i - 1]) + a[i]
    while (m--) {   // 看个人写法吧 
        int x; 
        scanf("%d", &x);
        printf("%lld\n", sum[x]);
    }
    return 0;
}

维前缀和还有一个作用，就是可以求区间和。怎么求捏？

我们可以发现，从 a_l 到 a_r 的值 = a_1 到 a_r 的值 - a_1 到 a_{l - 1} 的值!

那么，就非常简单了，我们可以先求一遍前缀和，然后每一次询问就输出 sum_{r} - sum_{l - 1}, ok!

code: 
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 1e7 + 5; // 成习惯了,真戒不掉QAQ
int n, m, a[MAXN];
ll sum[MAXN]; // 前缀记录数组

inline ll calc(int l, int r) {
    return sum[r] - sum[l - 1];
}

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sum[0] = 0; // 全局变量,其实不写也行
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i]; // 用递推的思想, 因为a[1]~a[i](sum[i])的和一定是a[1]~a[i - 1]的和(sum[i - 1]) + a[i]
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%lld\n", calc(l, r));
    }
    return 0;
}

其实，前缀和还有个很好用的东东：

差分！！！

假设，有这样一道题：

给一个数列 a_1,a_2,…,a_n 。

要求支持 q 个操作，每次会给一段区间 [l,r] 将 a_l,a_{l+1},…,a_r全都加上 1。

问最后整个数列会变成什么样。

数据范围 : 对于所有的数据，保证1≤n,q≤105,1≤a_i≤105,1≤l≤r≤n 。

(你是不是在想：这是干嘛，跟前缀和有关系？）

答案是：肯定的！！！！

我们这么想，我们先设定一个差分数组 c, 每一次操作把

没错, 求出了之间的差!!! $code: 
#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[100010];
int c[100010];
long long int s[100010];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        c[l] += 1, c[r + 1] -= 1;  // 在前端点 + 1, 没有了就 - 1
    }
    long long sum = 0;
    for (int j = 1; j <= n; j++) {
        sum += c[j];
        s[j] = sum;   // 做一次前缀和求差 
    }
    for (int i = 1; i <= n; i++) {
        s[i] += a[i];  // 加上差 
        printf("%lld ", s[i]);
    }
    return 0;
}

二维前缀和呢？

我们想要求出这样的和： 其实，求出这个，只需要用红色区和 + 绿色区和： 可是我们发现，这里需要用到容斥原理, 还要再减去重叠的紫色部分，就是被计算两次的部分。

核心就是：

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

核心代码已给出，其余代码与一维前缀和类似，因时间需要（估计也没人爱看一大串又臭又长的非核心代码），便不再赘述。