数据结构: 前缀和

Posted on Edited on In , Word count in article: 446 Reading time ≈ 2 mins.

一维前缀和

  • 对一个原数组a1 ∼ n，令$\begin{align}s_i=\sum_{k=1}^ia_k\end{align}$，即称s为a的前缀和数组

  • 不难发现有以下性质：

    • ${\rm len}(a)={\rm len}(s)$
    • 任意以a1为起始的子区间[a1,ai]，其元素和为si

  • 对于满足如下要求的运算：

    • 元素间运算满足结合律
    • 所有元素具有逆元，即满足消去律(可由运算结果及其中一个操作数得知另一个操作数)
    • 满足上述要求的区间信息包括加和、乘积、异或等

    令s0 = 0，则有sum(ai,aj) = sj − si − 1

  • 原地实现：

    1
    2
    3
    4
    5
    6
    int a[MAXN], t;
    for (int i = 1; i <= n; ++i) {
        cin >> t;
        a[i] += t;
        a[i + 1] = a[i];
    }

二维前缀和

  • 类似一维前缀和，对一个n行m列的二维数组，令$\begin{align}s_{ij}=\sum_{i=1}^n\sum_{j=1}^ma_{ij}\end{align}$，即称s为a的前缀和数组

  • 类似一维前缀和，结合容斥原理，对于特定的运算，任意一个子区间(左上角为aij，右下角为axy)的元素和为sxy + s(i−1)(j−1) − sx(j−1) − s(i−1)y，其中s0· = s·0 = 0

  • 原地实现：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int a[MAXN][MAXM], t;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> t;
            a[i][j] += t;
            a[i][j + 1] += a[i][j] - a[i - 1][j]; // 容斥
            a[i + 1][j] = a[i][j];
        }
    }

    也可以不依赖容斥，像扫地一样实现(虽然高维前缀和不实用，但这种方法能比较清晰地算出高维前缀和)：

    ```c++ for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> t; a[i][j] += t; a[i][j + 1] = a[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { a[i + 1][j] += a[i][j]; } }