一坑未平，一坑又起
前缀和，顾名思义，就是前$n$项和。
不过具体含义得具体分析。

一、前缀和

1.一维前缀和

一维前缀和是最基本的情况。

int a[N],s[N];//a是原数组，s是前缀和
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i];//由于全局变量a[0]==0,因此s[1]==a[1]
}
int query(int l,int r)//查询
{
    return s[r]-s[l-1];
}

2.二维前缀和

二维矩阵的前缀和是二维矩阵左上方的所有元素的和。
若令矩阵$A$中$A_{xy}$的前缀和为$S_{xy}$，则：

$S_{xy}=\sum\limits_{1 \leq i \leq x \land 1 \leq j \leq y}a_{ij}$

二维前缀和的计算用到了容斥原理。

以下参考了yxc的代码

int a[N][N],s[N][N];
void init()
{
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
int query(int x1,int y1,int x2,int y2)//不妨设x1 <= x2 , y1 <= y2
{
    return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}

所以说yxc的课你买不了吃亏买不了上当

3.三维前缀和

待填坑

4.$k$阶一维前缀和

其实维度再高的话就没什么意义了，因为数组能开的空间有限。

二、差分

1.一维差分

int a[N],b[N];//b是a的差分数组，等价于a是b的前缀和数组
void modify(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
void init()//初始化的本质是对单点进行修改
{
    for(int i=1;i<=n;++i)modify(i,i,a[i]);
}
void query()
{
    for(int i=1;i<=n;++i)a[i]=b[i]+a[i-1];
}