算法基础-前缀和

前缀和

一、什么是前缀和？

一维前缀和：

有一个一维数组 $x$ 和该数组的一维前缀和数组 $y$ ，则 $x$ 和 $y$ 满足以下关系：

$y_0=x_0、y_1=x_0+x_1、y_2=x_0+x_1+x_2、……y_n=x_0+x_1+x_2+…+x_n$

二维前缀和：

有一个二维数组 $a$ 和该数组的二维前缀和数组 $b$ （其同样是个二维数组），则 $a$ 和 $b$ 满足以下关系：

$b_{0,0}=a_{0,0}、b_{0,1}=a_{0,0}+a_{0,1}、b_{1,0}=a_{0,0}+a_{1,0}、b_{1,1}=a_{0,0}+a_{0,1}+a_{1,0}+a_{1,1}……$

看公式可能有点懵，看底下的图更好理解。

右侧标注橙色的二维前缀和元素，其值是左侧的原二维数组中标注橙色的所有元素的和。

二、如何得到前缀和？

一维前缀和：

很容易就可以发现： $y_n=y_{n-1}+x_n$

代码实现如下：

for(int i=0;i<n;i++)
{
    if(i==0) y[i]=x[i];
    else y[i]=y[i-1]+x[i];
}

二维前缀和：

二维前缀和实际上就是一个矩阵内值的和，而矩阵又可以由两个行数或列数少一的子矩阵组合后，删去重合部分再加上右下角的值来构成，也就是以下式子：

$b_{x,y}=b_{x-1,y}+b_{x,y-1}-b_{x-1,y-1}+a_{x,y}$

代码实现如下：

for(int y=0;y<n;y++)//n行
    for(int x=0;x<m;x++)//m列
    {
        if(x==0&&y==0) b[y][x]=a[y][x];//左上角的值
        else if(x==0) b[y][x]=b[y-1][x]+a[y][x];//第一列
        else if(y==0) b[y][x]=b[y][x-1]+a[y][x];//第一行
        else b[y][x]=b[y-1][x]+b[y][x-1]-b[y-1][x-1]+a[y][x];
    }

三、前缀和有什么用？

3.1 说明

前缀和是一种预处理，用于降低查询时的时间复杂度。

举个例子：给定 $n$ 个整数，然后进行 $m$ 次询问，每次询问求一个区间内值的和。

如果用暴力写法，那每次询问都需要从区间左端点循环到区间右端点求和，时间复杂度较大。

这种时候就可以预先求出该数组的一维前缀和。

则 $ans=y[R]-y[L-1]$ ，其中 $L$ 和 $R$ 是给定的区间。每次询问可直接输出答案，这样时间复杂度就降到了 $O(N+M)$ 。

3.2 一些前缀和例题

3.2.1 成绩百分比改编自网易笔试题

班级中共有 $n$ 位同学，其编号为1~ $n$ 。考试中每位同学都取得了一定的成绩。
接下来进行 $m$ 次询问，每次询问给出一位同学的编号，求这位同学的成绩在班级中的百分比。
百分比求法：不超过这位同学成绩的班级人数（包括这位同学）/总人数×100%。
( $2<=m,n<=100000$ ，成绩 $a_i<=150$ )。