前缀和

一维前缀和

应用场景

  • 需要频繁访问子列和的场景

核心思想

  • 使用 s_{i} = p_{i} + s_{i - 1} 来初始化前缀和数组
  • 利用 s_{r} - s_{l - 1} (1 \leq l \leq r \leq n) 来访问子数组 p_{l..r} 的和

Code

{
    int * p = new int [n + 1];
    for (int i = 1; i <= n; i++)
        scanf("%d", p + i);

    // 预处理前缀和数组
    // 多开一位，方便处理s[1]
    int * s = new int [n + 1];
    s[0] = 0;
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + p[i];

    ...
    // 访问子列和，假定已定义 l, r
    std::cout << s[r] - s[l - 1];

    ...
    delete [] s;
    delete [] p;
}

时间复杂度

  • 预处理：O(n)
  • 每次访问：O(1)

练习

求区间和

二维前缀和

应用场景

  • 需要频繁访问子矩阵和的场景

核心思想

  • 使用 s_{i,\ j} = p_{i,\ j} + s_{i - 1,\ j} + s_{i,\ j - 1} - s_{i - 1,\ j - 1} 预处理前缀和
  • 使用 s_{x,\ y} - s_{x - a,\ y} - s_{x,\ y - b} + s_{x - a,\ y - b} 来访问以 (x,\ y) 为离坐标原点最远的顶点的 a \times b 子矩阵内的所有元素之和
  • 或使用 s_{x_{2},\ y_{2}} - s_{x_{1} - 1,\ y_{2}} - s_{x_{2},\ y_{1} - 1} + s_{x_{1} - 1,\ y_{1} - 1} 来访问分别以 (x_{1},\ y_{1}) 和 (x_{2},\ y_{2}) 为最靠近和最远离原点的子矩阵内所有元素之和

Code

{
    int **p = new int * [n + 1];
    for (int i = 0; i <= n; i++)
        p[i] = new int [m + 1];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", p[i] + j);
    
    int **s = new int * [n + 1];
    for (int i = 0; i <= n; i++)
        s[i] = new int [m + 1];
    
    // 使 s[0][i] s[i][0] 都为零，方便后续处理
    for (int i = 0; i <= n; i++)
        s[i][0] = 0;
    for (int i = 0; i <= m; i++)
        s[0][i] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = p[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    ...
    // 访问子矩阵和
    // 这里使用 i, j 是为了表明数据范围，实际用特定的坐标(x, y)代替
    // 这里要注意循环的起始位置
    for (int i = a; i <= n; i++)
        for (int j = b; j <= m; j++)
            std::cout << s[i][j] - s[i - a][j] - s[i][j - b] + s[i - a][j - b] << ' ';
    
    /*
    std::cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << std::endl;
    */

    ...
    // 释放使用的数组的内存
    for (int i = 0; i <= n; i++)
        delete [] s[i];
    delete [] s;
    for (int i = 0; i <= n; i++)
        delete [] p[i];
    delete [] p;
}

时间复杂度

  • 预处理：O(n \times m)
  • 每次访问：O(1)

练习

领地选择

差分

一维差分

应用场景

  • 需要将数组内某个范围内的数加上同一个数（可以是负数）

核心思想

  • 前缀和的逆运算
  • 通常使用 d_{i} = p_{i} - p_{i - 1} 构造差分数组
  • 使用 d_{l} + x 和 d_{r + 1} - x 来实现 [l,\ r] 内 p_{i} 全体加上 x
  • 再通过前缀和还原数组 p_{n}

Code

{
    int * p = new int [n + 1];
    int * d = new int [n + 1];
    p[0] = 0, d[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", p + i);
        d[i] = p[i] - p[i - 1];
    }

    ...
    d[l] += x;
    if (r + 1 <= n) d[r + 1] -= x;

    ...
    for (int i = 1; i <= n; i++)
        p[i] = d[i] + p[i - 1];
    
    ...
    delete [] d;
    delete [] p;
}

时间复杂度

  • 预处理：O(n)
  • 每次操作：O(1)
  • 还原：O(n)

练习

语文成绩

二维差分

适用场景

  • 将二维矩阵内的一个子矩阵中的所有元素加上同一个数

核心思想

  • 二维前缀和的逆运算
  • 通常使用 d_{i,\ j} = p_{i,\ j} - p_{i - 1,\ j} - p_{i,\ j - 1} + p_{i - 1,\ j - 1} 来构造二维差分数组
  • 使用 d_{x,\ y} + k、d_{x + a,\ y + b} + k、d_{x + a,\ y} - k 以及 d_{x,\ y + b} - k 来实现以 (x,\ y) 为最靠近原点的顶点的 a \times b 子矩阵中的所有元素加上 k
  • 或使用 d_{x_{1},\ y_{1}} + k、d_{x_{2} + 1,\ y_{1}} - k、d_{x_{1},\ y_{2} + 1} - k 以及 d_{x_{2} + 1,\ y_{2} + 1} + k 来实现分别以 (x_{1},\ y_{1}) 和 (x_{2},\ y_{2}) 为最靠近和最远离原点的子矩阵中的所有元素加上 k
  • 通过二维前缀和可以还原数组 p_{i,\ j}

Code

{
    int ** p = new int * [n + 1];
    int ** d = new int * [n + 1];
    for (int i = 0; i <= n; i++)
    {
        p[i] = new int [m + 1];
        d[i] = new int [m + 1];
    }

    for (int i = 0; i <= n; i++)
    {
        p[i][0] = 0;
        d[i][0] = 0;
    }

    for (int i = 0; i <= m; i++)
    {
        p[0][i] = 0;
        d[0][i] = 0;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", p[i] + j);
            d[i][j] = p[i][j] - p[i - 1][j] - p[i][j - 1] + p[i - 1][j - 1];
        }
    }

    ...
    d[x][y] += k;
    if (x + a <= n) d[x + a][y] -= k;
    if (y + b <= m) d[x][y + b] -= k;
    if (x + a <= n && y + b <= m) d[x + a][y + b] += k;
    /*
    d[x1][y1] += k;
    if (x2 + 1 <= n) d[x2 + 1][y1] -= k;
    if (y2 + 1 <= m) d[x1][y2 + 1] -= k;
    if (x2 + 1 <= n && y2 + 1 <= m) d[x2 + 1][y2 + 1] += k;
    */

    ...
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            p[i][j] = d[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
    
    ...
    // 然后释放数组，内容和二维前缀和一样，此处略
}

时间复杂度

  • 预处理：O(n \times m)
  • 每次操作：O(1)
  • 还原：O(n \times m)

练习

地毯
地毯 加强版