一维前缀和

// 注意i从1开始,s[0] = 0, a[0] = 0;
for ( int i =1; i<=n; i++ ) s[i] = s[i-1] + a[i];

s[1] = a[1];
s[2] = a[1] + a[2];
s[3] = a[1] + a[2] + a[3];
s[4] = a[1] + a[2] + a[3] + a[4];
...
s[n] = a[1] + a[2] + ...... + a[n-1] + a[n]

求a数组中[l, r] 区间上数的和:
s[r] - s[l-1];

前缀和维护最值

int w[N];
int lmin[N], lmax[N], rmin[N], rmax[N];


for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
// 维护左前缀的最小值，最大值所在的下标
lmin[1] = lmax[1] = 1;
for (int i = 2; i <= n; i ++ )
{
    lmin[i] = lmax[i] = i;
    if (w[lmin[i - 1]] < w[i]) lmin[i] = lmin[i - 1];
    if (w[lmax[i - 1]] > w[i]) lmax[i] = lmax[i - 1];
}
// 维护右后缀的最小值，最大值所在的下标
rmin[n] = rmax[n] = n;
for (int i = n - 1; i; i -- )
{
    rmin[i] = rmax[i] = i;
    if (w[rmin[i + 1]] < w[i]) rmin[i] = rmin[i + 1];
    if (w[rmax[i + 1]] > w[i]) rmax[i] = rmax[i + 1];
}

后缀和

for (int i = 1, j = n; i <= n; i ++, j--  )
{
    scanf("%d", &a[i]);
    // 逆向做一遍，求后缀和
    b[j] = a[i]; 
}

for ( int i = 1; i<=n; i++ ) s[i] = s[i-1] + b[i];

一维差分

// 注意i从1开始,b[0] = 0, a[0] = 0;
a是b的前缀和数组, b是a的差分数组
b用于让a的[l,r]区间上每一个数都加上一个c
void insert( int l, int r , int c ) {
    b[l] += c;
    b[r+1] -= c;
}
/*
初始化：
insert( i,i,a[i]);
b[i] = a[i] - a[i - 1];
插入操作：
insert( l ,r c );
由b还原a:
b[i] = a[i] - a[i-1];
b[1] = a[1];
b[2] = a[2] - a[1];
b[3] = a[3] - a[2];
...
b[n] = a[n] - a[n-1];
*/


for ( int i =1; i <= n; i++ ) b[i] += b[i-1];

b[1] = b[0] = 0;
b[2] = b[2] + b[1] = a[2] - a[1] + a[1] - 0 = a[2];
b[3] = b[3] + b[2]  = a[3] - a[2] + a[2];
...

二维前缀和

n × m的矩阵, i,j均从1开始

S[i, j] = 第i行j列格子 左上 部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
// 注意都是在x1, y1处-1;
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1 - 1]

初始化：
    for ( int i=1; i<=n; i++ ) 
      for ( int j=1; j<=m; j++ ) 
         s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];

// 预处理前缀和
// 读入时不需要再借助额外的数组，直接向s[i][j] 中读入
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
// 注意都是x2,y2处+1
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

插入函数：
void insert( int x1,int y1,int x2,int y2,int c ) {
    b[x1][y1] += c;
    b[x2+1][y1] -=c;
    b[x1][y2+1] -=c;
    b[x2+1][y2+1] += c; 
}
初始化：
for ( int i=1; i<=n; i++ ) 
        for ( int j=1; j<=m; j++ ) 
            insert( i,j,i,j,a[i][j] ); 
由b还原a：
    for ( int i=1; i<=n; i++ ) 
        for ( int j=1; j<=m; j++ ) 
            b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];