前缀和&差分总结

[happyvictorwu]

前缀和 & 差分

前缀和

模板

一维

• s[i] 表示前i个数[0, i)的累加和。 下标从1开始。 (s[0] == 0) dp的边界， 可以少些判断
• 前缀和数组s下标从1开始， 原数组nums下标从0开始

// s[0] = 0
for (int i = 1; i <= n; i++) {
    s[i] = s[i-1] + nums[i-1];
}

// l, r是指原数组下标区间
// s[r+1]: [0, r]       0, 1, ..., l-1 , l, ..., r
// s[l]  : [0, l-1]     0, 1, ..., l-1 , 
// 相减                       [l, r]的和 ：l, ..., r                 
int l_to_r_sum = s[r+1] - s[l];

二维

// s下标从1开始（第0行和第0列都置成0）， mat下标从0开始

// 算前缀和
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] + mat[i-1][j-1];
    }
}

// (x1, y1) 为左上角， (x2, y2)为右上角. 坐标对应原数组下标。 下标偏移了1
int sum = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1];

差分

模板

一维

• 所求数组s（下标从0开始）为一个数组的前缀和数组， 处前把其变成下标从1开始，让s[0] == 0
• 求出原数组nums
• 把原数组还原成s数组， 根据题目需要是否把s数组改回成下标从0开始

// 让s[0] == 0
for (int i = 1; i <= n; i++) {
    nums[i-1] = s[i] - s[i-1];   // 前缀和的逆运算 s[i] = s[i-1] + nums[i-1]
}

// 区间[l, r]增加一个数c ， l, r是从0开始的下标


nums[l] += c;   //等价对应s数组 l... r, r+1, ..., n-1 全部增加了c
nums[r+1] -= c; //等价对应s数组         r+1, ..., n-1 全部减少c
                // s数组 [l, r] 增加了c


for (int i = 1; i <= n; i++) {
    s[i] = s[i-1] + nums[i-1]
}
// 再把s数字变成以0为下标
// remove first item in array of s

二维

// s原数组变成下标从1开始， 原来从0开始，（第0行和第0列都置成0）

// 算差分数组mat， 下标从0开始， 但是mat数组也要开多一维
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        mat[i-1][j-1] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1];
    }
}

mat[x1][y1] += c;
mat[x2+1][y1] -= c;
mat[x1][y2+1] -= c;
mat[x2+1][y2+1] += c;  // 可能越界， 所以要开多一维，最后一行和最后一列都为0

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] + mat[i-1][j-1];
    }
}

// 还原s数组从0坐标开始