算法笔记01 前缀和与差分

资料

题目

前缀和算法

前缀和可以简单理解为「数列的前n项的和」,是一种重要的预处理方式,能大大降低查询的时间复杂度。

定义一个数组 $a_i$ 为任意数字组成的集合,存储其前n项和 $O(n)$

$$
P_i=\sum_{j=1}^ia_i=P_{1-1}+a_i
$$

对前n项和的求和运算拥有可加/减性。

$$
sum[1,k]+sum[k+1,n]=sum[1-n]
$$

所以可以通过这个性质,一次计算 l-r 闭区间的数字之和。

$$
ans=sum[l,r]=sum[1,r]-sum[1,l-1]=P_r-P_l
$$

const int N = 1e5 + 9;
int n, q, l, r, map[N];
ll prefix[N]; // 存储前缀和 

// https://oj.eriktse.com/problem.php?id=1049
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> map[i]; // 先随便存一下数字
    for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + map[i]; // 存储前缀和

    cin >> q; // q次询问
    while (q--) {
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl; 
        // 一次计算,输出 l、r 闭区间范围的和
    }
}

差分算法

差分是一种和前缀和相对的策略,可以当做是求和的逆运算。

💡 差分数组是静态的,因此不能解一边循环一边修改的问题,只有修改完成后,使用复杂度 $O(1)$ 进行询问。

差分数组 diff[N]:良好的修改性质,可以对一个范围进行修改。

$$
d_i=\begin{cases}
a_i-a_{i-1}\,&i\in[2,n] \
a_1\,&i=1
\end{cases}
$$

借此进行修改后,通过前缀和还原 $a_i$ 实现数组 $a_i$ 的特定区间修改。

  • 通过前缀和还原出 $a_i$

$$
\sum_{j=1}^id_j=d_1+d_2+d_3+\cdots+d_i=(\bcancel{a_1}-a_0)+(\bcancel{a_2}-\bcancel{a_1})+(\bcancel{a_3}-\bcancel{a_2})+\cdots+(\bcancel{a_{i-1}}-\bcancel{a_{i-2}})+(a_{i}-\bcancel{a_{i-1}})=0+a_i=a_i
$$

  • 后缀区间修改
    • 对 $d_l+x$ 则会造成 $a_{l+1}+x,a_{l+2}+x,\cdots,a_n+x$
    • 再对 $d_{r+1}-x$ 则会造成 $a_{r+1}-x,a_{r+2}-x,\cdots,a_n-x$
    • 从事实现将数组 $a_i$ 中 [l-r] 区间内的元素进行 +x 操作

修改+询问的整体流程:输入数组 $a_i$ → 定义差分数组 $d_i=a_i-a_{i-1}$ → 对 $d_i$ 进行修改 → 对 $d_i$ 使用前缀和 → 还原 $a_i$ → 在进行求和询问。

const int N = 1e5 + 9;
ll n, map[N], diff[N], prefix[N];

// https://oj.eriktse.com/problem.php?id=1050
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> map[i];
    for (int i = 1; i <= n; ++i) diff[i] = map[i] - map[i - 1]; // 求差分数组

    int m;
    cin >> m;
    while (m--) { // m次修改操作
        int l, r, x;
        cin >> l >> r >> x;

        // 后缀区间修改 给 [l,r] 进行 +x 修改
        diff[l] += x; // 修改 [l,n] +x
        diff[r + 1] -= x; // 修改 [r+1,n] -x
    }

    for (int i = 1; i <= n; ++i) map[i] = map[i - 1] + diff[i]; 
    // 通过给修改后的 差分数组求 前缀和,还原修改后的数组map

    for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + map[i]; 
    // 再次求前缀和

    int q;
    cin >> q;
    while (q--) { // q次询问
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
}

二维前缀和

定义一个矩阵为二维数组 $a[i,j]$ ,定义二维前缀和数组 $prefix[i][j]$ 为从 $[1,1]$ 到 $[i,j]$ 对角线,所呈现的范围内的数字和

首先通过下述方式存储前缀和数组:

$$
prefix[i,j]=\sum_{t_i=1}^i\sum_{t_j=1}^ia_{i,j}=P[i-1][j]+P[i][j-1]-P[i-1]P[j-1]+a[i][j]
$$

然后再运算出矩阵 $i,j$ 范围内的数字之和:

$$
ans=P[x_2][y_2]-P[x_2][y_1-1]-P[x_1-1][y_2]+P[x_1-1][y_1-1]
$$

const int N = 1e3 + 9;
int n, m, q;
ll map[N][N], prefix[N][N];

// https://oj.eriktse.com/problem.php?id=1060
void solve() {
    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> map[i][j]; // 将矩阵存储到二维数组
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 存储二维前缀和数组
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + map[i][j];
        }
    }

    while (q--) { // q次询问
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1] << endl;
    }
}

二维差分

  1. 无需计算出差分数组,都将其默认为0
  2. 待补充
const int N = 1e3 + 9;
int n, m, q, map[N][N], diff[N][N];

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> map[i][j]; // 二维数组存一下
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            diff[i][j] += map[i][j];
            diff[i][j + 1] -= map[i][j];
            diff[i + 1][j] -= map[i][j];
            diff[i + 1][j + 1] += map[i][j];
        }
    }

    while (q--) { // q次添加操作
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;

        diff[x1][y1] += c;
        diff[x1][y2 + 1] -= c;
        diff[x2 + 1][y1] -= c;
        diff[x2 + 1][y2 + 1] += c;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            map[i][j] = map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1] + diff[i][j];
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
}

附:例题贪心求最长子段和

评论

  1. retr0
    Windows
    1 月前
    2024-4-21 10:47:28

    开始学算法了熬,昕明

  2. 人工智障
    Windows
    1 月前
    2024-4-27 13:48:17

    orz

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇