算法与数据结构--前缀和

一维前缀和适用于计算某个一维数列某个数到某个数之间的累加和（或者乘积，又或者异或和）之类的。

比如计算某个一维度数列从i到j之间元素的和。最开始的想法就是从i遍历到j，将这之间的元素相加。但是当查询次数很多时候，有没有更方便的方法呢？

我们可以在输入的时候计算一下前缀和，也就是第1项的和，第1和2项的和，第1和2和3项的和。。。然后当计算从i到j之间元素的和时候，我们只需要将第1项到第j项的和减去第1项到第i-1项的和就可以了，这样每次查询的时间复杂度就从O（n）降到了O（1）。当查询的次数很多的时候，时间提升的特别明显。

#include <iostream>
using namespace std;int main() {int n;cout << "请输入数列的长度n: ";cin >> n;int nums[n];int prefixSum[n];cout << "请输入" << n << "个整数作为数列: ";for (int i = 0; i < n; ++i) {cin >> nums[i];if(i==0)prefixSum[0]=nums[0];elseprefixSum[i]=nums[i]+prefixSum[i-1]; }int queries;cout << "请输入查询的次数: ";cin >> queries;for (int q = 0; q < queries; ++q) {int left, right;cout << "请输入查询的区间左右边界i和j: ";cin >> left >> right;// 查询区间累加和int sum = prefixSum[right] - prefixSum[left - 1];cout << "区间(" << left << ", " << right << ") 的累加和为: " << sum << endl;}return 0;
}