前缀和系列-概览

1. 前缀和和差分的本质：空间换时间
2. 前缀和：将原来序列的O（N)的累加操作转换为O(1)的相减操作
   3.差分：将原序列O（N）的区间操作（同时加或者同时减去）转换为差分序列上的O(1)的双端操作
3. 注意二维前缀和与二维差分

前缀和和差分，通过空间来换时间，一般用来优化时间复杂度，从$O(n^2)$到$O(n)$

//一维前缀和 —— 模板题 AcWing 795. 前缀和

int prefix_sum() {
    S[i] = a[1] + a[2] + ... a[i];
    a[l] + ... + a[r] = S[r] - S[l - 1];
}

//二维前缀和 —— 模板题 AcWing 796. 子矩阵的和

int 2d_preifx_sum()
{
    S[i, j] = 第i行j列格子左上部分所有元素的和
    //以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
    S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
}

//一维差分 —— 模板题 AcWing 797. 差分
给区间[l, r]中的每个数加上c：

B[l] += c, B[r + 1] -= c

//二维差分 —— 模板题 AcWing 798. 差分矩阵
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

题目分类	题目名称	考察点	其他说明
前缀和系列	不使用除法的特殊累乘	前缀和、定序技巧