一维前缀和

对于一维数列，可以快速静态查询区间 $[l,r]$ 的和。已知数列：$a_1,a_2,a_3,a_4,a_5...a_{n-1},a_n$，引入前缀和数列：$s_i=a_1+a_2+a_3+...+a_i=\sum _{k=1}^i{a}_k=s_{i-1}+a_i$。 此时，我们查询区间 $[x,y]$ 内的元素和：$ans=s_y-s_{x-1}$。 时间复杂度为 $O(1)$。

构造前缀和数组：

int s[n], a[n];

for(int i = 1; i <= n; i++) {
	cin >> a[i];
	s[i] = a[i] + s[i - 1]; // 当i = 1时 s[i - 1] = 0
}

• 注意这里我们的设置起始下标为 $1$，是为了节省代码量

模板例题

洛谷 P8218. 求区间和

给定一个序列 $n$ 个数，现有 $m$ 组查询，每组查询给定一个区间 $x$、$y$，输出每组查询的区间和。

样例输入：

5 3
2 1 3 6 4
1 2
1 3
2 4

样例输出：

3
6
10

变式例题

已知两个正整数 $a$ 和 $b$，求在 $a$ 到 $b$（包括 $a$、$b$，$1\le a<b\le 1000000$）中的任意两个整数 $x$ 和 $y$ $(x<=y)$之间所有整数的十进制表示中 $1$ 出现的次数之和，有 $n(1\le n\le 100000)$ 次询问。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int s[N];

int main() {
	int a, b; cin >> a >> b;

	for (int i = a; i <= b; i++) {
		int t = i, c = 0;
		while (t) {
			if (t % 10 == 1) c++;
			t /= 10;
		}
		s[i] = s[i - 1] + c;
	}

	int q; cin >> q;
	while (q--) {
		int x, y; cin >> x >> y;
		cout << s[y] - s[x - 1] << endl;
	}


	return 0;
}

洛谷：P1115 最大子段和

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int s[N], a[N];

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}

	int minn = min(0, s[1]);            // 首位可能是负数，则初始化为0
	int ans = -1e9;
	for (int i = 2; i <= n; i++) {
		ans = max(ans, s[i] - minn);    // 当前答案和新的子序列和比较
		minn = min(minn, s[i]);         // i之前的所有子序列和的最小值
	}

	cout << ans << endl;

	return 0;
}

二维前缀和

二维前缀和：$s_{ij}=\sum _{x=1}^i\sum _{y=1}^j{a}_{ij}$

已知数列$a$如何构造前缀和数列 $s$? $s_{ij}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}$

int s[n][m], a[n][m];

for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= m; j++) {
		cin >> a[i][j];
		s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
	}
}

此时查询子矩阵 $[(x_1,y_1),(x_2,y_2)]$ 的所有元素之和为：$ans=s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}$

模板例题：子矩阵的和

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个询问，每个询问包含四个整数 $x_1、y_1、x_2、y_2$，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

样例输入：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

样例输出：

17
27
21

参考代码：

#include <iostream>
using namespace std;


const int N = 1010;
int s[N][N], a[N][N], n, m, q;

int main() {
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    while(q --) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 -1] + s[x1 - 1][y1 - 1] << endl;
    }

    return 0;
}

方格稿纸

小猪在小学中认识了很多的字，终于会写一点作文了。某天小猪买了一张 $n$ 行 $m$ 列方格稿纸来写作文，小猪的邻居小小猪来小猪家玩，用黑墨水笔把小猪新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色。小猪不能责怪小小猪，但是作文写不成了，他觉得很无聊，就开始数里面有多少魔幻方阵。如果稿纸中一个 $k\times k$ 的正方形区域满足以下两个条件，那么它就是魔幻方阵：

1. 黑白格子的数量差不能超过 $1$。
2. $k$ 不能小于 $2$ 。 现在请你帮小猪求出他被染色的稿纸里面有多少个魔幻方阵。

样例输入：1 为黑色，0 为白色。

5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1

样例输出：

9

参考代码：

#include<cmath>
#include<iostream>
using namespace std;

int n, m, a[310][310], s[310][310], ans = 0;
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
		}

	for(int k = 2; k <= n && k <= m; k++)
		for(int i = 1; i <= n - k + 1; i++)
			for(int j = 1; j <= m - k + 1; j++) {
				int x = i + k - 1, y = j + k - 1;
				int bl = s[x][y] - s[i-1][y] - s[x][j-1] + s[i-1][j-1];
				int wh = k * k - bl;
				if(abs(bl - wh) <= 1)
					ans++;
			}

	cout << s;
	return 0;
}