基础算法_前缀和与差分

前缀和

题目描述： 求一段整数序列中下标从l到r之间的所有整数的和

算法分析：

朴素算法

• 算法思路：: 从l到r遍历
• 时间复杂度：O(n)

前缀和算法

• 建立数组SN, s[i]存储的是从1到i的所有元素的和
• ans = s[r] - s[l - 1]
• 时间复杂度：O(1)

一维前缀和

构造s[N]数组的两种方式

void build1() {
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i);
        s[i] = s[i - 1] + a[i];
    }
}

void build2() {
    for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
    for(int i = 1; i <= n; i++) s[i] += s[i - 1];
}

二维前缀和 : 求子矩阵的和

• 建立s[N][N], s[i][j]表示从第i行第j列到第1行1列所构成的矩形内所有元素之和

i/j	1	2	3
1	a[1][1]	a[1][2]	a[1][3]
2	a[2][1]	a[2][2]	a[2][3]

• 例如： s[2][2] = a[1][1] + a[1][2] + a[2][1] + a[2][2]

• 如何求子矩阵的和

• 例如 求给定 四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标所构成的子矩阵中所有数的和

• 样例： (2,2) (6,5)

i/j | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|---|
1 | a[1][1] | a[1][2] | a[1][3] | a[1][4] | a[1][5] |
2 | a[2][1] | a[2][2] | a[2][3] | a[2][4] | a[2][5] |
3 | a[3][1] | a[3][2] |a[3][3] |a[3][4] | a[3][5] |
4 | a[4][1] | a[4][2] |a[4][3] |a[4][4] | a[4][5] |
5 | a[5][1] | a[5][2] |a[5][3] | a[5][4] | a[5][5] |
6 | a[6][1] | a[6][2] | a[6][3] | a[6][4] | a[6][5] |

i/j | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|---|
1 | a[1][1] | a[1][2] | a[1][3] | a[1][4] | a[1][5] |
2 | a[2][1] | a[2][2] | a[2][3] | a[2][4] | a[2][5] |
3 | a[3][1] | a[3][2] |a[3][3] |a[3][4] | a[3][5] |
4 | a[4][1] | a[4][2] |a[4][3] |a[4][4] | a[4][5] |
5 | a[5][1] | a[5][2] |a[5][3] | a[5][4] | a[5][5] |
6 | a[6][1] | a[6][2] | a[6][3] | a[6][4] | a[6][5] |

• 从图上看， s[x1 - 1][y1 - 1] 重复减了一次
• ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

代码模板

void build() {
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> 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];
}

void solve() {
    int x1,y1,x2,y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    printf("%d
", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

差分

题目描述 ：输入一个长度为n的整数序列。，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。

一维差分

思路

• 将给定的序列看成是某个序列的前缀和序列s[N]，然后通过构造的方式确定该序列a[N]，记作差分序列
• 如果要在序列中[l, r]之间每个数加上c, 可以转化成为——在其差分序列a[N]的a[l] + c,再在a[r + 1] - c即可。
• 差分序列a[N]的a[l] + c， 结果可使s[l]之后的所有的元素都加上c, 而题目要求仅在区间[l, r]加上c, 只需在a[r + 1] - c即可。

代码模板

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

构造差分序列

方案一 ： 可从定义出发，a[i] = s[i] - s[i - 1]

void build1() {
    for(int i = 1; i <= n; i++) scanf("%d", &s[i);
    for(int i = 1; i <= n; i++) a[i] = s[i] - s[i - 1];
}

方案二： 初始将差分序列全部设为零， 对于每个元素可看成在该位置上插入某个数

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

void build2() {
    for(int i = 1; i <= n; i++) {
    scanf("%d", &s[i);
    insert(i, i, s[i]);
}

二维差分：

思路分析：

• 给定左上角坐标(x1, y1), 右下角坐标(x2, y2)
• 如图为例， x1 = 3, y1 = 3, x2 = 6, y2 = 6, 要对以这两个点为对角的矩阵进行操作

• 首先， 对差分矩阵中a[x1][x1] + c, 则对于前缀和矩阵s[N][N]产生的效果如图

• 然后， 再将差分矩阵a[x2 + 1][y2] - c,则对于前缀和矩阵s[N][N]产生的效果如图

• 再将差分矩阵a[x1][y2 + 1] - c,则对于前缀和矩阵s[N][N]产生的效果如图

• 从图中可以看出，右下角的矩阵重复计算了两次，在加回来，即a[x2 + 1][y2 + 1] + c
• 效果如图

代码模板：

inline 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;
}

差分矩阵的构造方式：

inline 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;
}

// n 行 m 列
void build3(int n, int m) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &s[i][j]);
            insert(i, j, i, j, s[i][j]);
        }
    }
}