前缀和

2023年10月30日 CS

前缀和

例题

输入一个长度为的整数序列，接下来再输入个询问，
每个询问输入一对, （左边界和右边界[, ]）

对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式

第一行包含两个整数和。
第二行包含个整数，表示整数数列。
接下来行，每行包含两个整数和，表示一个询问的区间范围。

输出格式

共行，每行输出一个询问的结果。
数据范围
1≤≤≤,
1≤,≤100000,
−1000≤数列中元素的值≤1000

输入样例：

输出样例：

1
2
3

3
6
10

前缀和数组

举个例子，假设现在有一数组int a[7] = {1,2,3,4,5,6,7}
第一位的前缀和就是a[0], 第二位的前缀和就是a[0] + a[1], 以此类推第n位的前缀和就是a[0] + a[1] + … + a[n-1]
由此可得一个前缀和数组int frontSUM = {0,1,3,6,10,15,21,28}
若此时要求某个区间内[x, y]值的和，那么这个和就等于frontSUM[y] - frontSUM[x - 1]
但由于x - 1可能为负值，因此将前缀和数组的第一位设为0

创建前缀和数组

引用上述案例的2 1 3 6 4
由于frontSUM[n] = frontSUM[n - 1] + an - 1
可得：

vector frontSUM(1,0);
for (int i = 1; i <= 5; i++) {
    int inputValue;
    cin >> inputValue;
    frontSUM.push_back(frontSUM[i - 1] + inputValue); 
}

测试代码：

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

int main() {
	vector<int> frontSUM(1,0);
	for (int i = 1; i <= 5; i++) {
		int inputValue;
		cin >> inputValue;
		frontSUM.push_back(frontSUM[i - 1] + inputValue); 
	}
	for (int i = 0; i < 6; i++) {
		cout << frontSUM[i] << " ";
	}
}

最终题解：

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

int main() {
	int numAccount = 0;
	cin >> numAccount;
	int areaAccount = 0;
	cin >> areaAccount;

	vector<int> frontSUM(1,0);
	for (int i = 1; i <= numAccount; i++) {
		int inputValue;
		cin >> inputValue;
		frontSUM.push_back(frontSUM[i - 1] + inputValue);
	}
	
	struct Area {
		int leftPoint;
		int rightPoint;
	};

	vector<Area> areaVector;
	for (int i = 0; i < areaAccount; i++) {
		Area areaTemporary;
		int inputValue;

		cin >> inputValue;
		areaTemporary.leftPoint = inputValue;

		cin >> inputValue;
		areaTemporary.rightPoint = inputValue;
		areaVector.push_back(areaTemporary);
	}

	for (int i = 0; i < areaAccount; i++) {
		cout << frontSUM[areaVector[i].rightPoint] - frontSUM[areaVector[i].leftPoint - 1] << endl;
	}

	return 0;

}

Categories

Archive

Recent Posts

前缀和

前缀和

例题