$\Huge\color{orchid}{点击此处获取更多干货}$

前缀和

虽然计算机考研专业课没有明确涉及前缀和算法，但是考研数学中可以看到一点前缀和思想的影子，比如概率论中，离散型随机变量$X$的概率分布函数定义式为：
$$F_X(x)=P(X\le x) = {\sum_{i=x_0}^{x}}P(X=i) ,x_0为X可能取值的最小值$$
上述公式中，分布函数的求法就是对于每个确定的$x$，从最小值$x_0$开始，将每个不大于$x$的值对应的概率全部累加起来，由此还可以得出$P(a<X\le b)=F_X(b)-F_X(a)$。

序列的前缀指的是包含序列头端元素在内的一段连续子序列，前缀和则是前缀序列中所有元素的和，因此在求序列中间一段的元素和时，就可以记录一下不同元素作为尾端时，分别的前缀和，然后用上述求区间概率的方法，将这一段尾端对应的前缀和减去头端前一个元素对应的前缀和，就可以得到这一段内的元素和，如果还有困惑的话，下图可以形象说明一切：

C++ 代码

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

vector<int> preSum = { 0 };//位序0的前缀和默认为0

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q, x;
    cin >> n >> q;
    while(n--) {
        cin >> x;
        //每一个元素x处的前缀和只和它前一个位置的前缀和有关，即为前一个位置的前缀和加上x本身
        preSum.push_back(preSum.back() + x);//preSum表的末尾元素就相当于x前一个位置的前缀和
    }
    int l, r;
    while(q--) {
        cin >> l >> r;
        //r处前缀和与(l-1)处前缀和的差，就是该段内元素的和
        cout << preSum[r] - preSum[l - 1] << endl;
    }
    return 0;
}