前缀和系列-概览

前缀和和差分，通过空间来换时间，一般用来优化时间复杂度，从$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

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