信息奥赛｜前缀和与差分

知识点概览 🚀

• 一维前缀和
• 二维前缀和
• 一维差分
• 二维差分

---

知识点详解 🎥

学习素材

编号	内容	链接	平台	创作者	推荐指数
1	算法基础课——前缀和与差分	链接1	Acwing	大雪菜	🌟🌟🌟🌟🌟

推荐学习路线

观看 y总の视频，了解 前缀和与差分 的算法思想。

代码模版

AcWing：https://www.acwing.com/blog/content/277/

• 一维前缀和

// 计算一维前缀和数组
for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + a[i];
}

// 输出区间[l,r]的部分和
cout << s[r] - s[l - 1] << endl;

• 二维前缀和（推荐画图推导）

// 计算二维前缀和数组
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] + a[i][j];
    }
}

// 输出以(x1,y1)为左上顶点、(x2,y2)为右下顶点的部分和
int psum = s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1] + s[x_1 - 1][y_1 - 1];
cout << psum << endl;

• 一维差分

// 初始化差分数组b
for (int i = 1; i <= n; i++) {
    cin >> tmp;
    // 设读入1 4 8 3 2，则对应的差分数组b在此阶段被初始化为1 3 4 -5 -1
    b[i] += tmp, b[i + 1] -= tmp;  // 核心操作
}

// 读入m次操作，每次操作使区间[l, r]中的每一个元素+c
for (int i = 1; i <= m; i++)
  cin >> c >> l >> r;
  b[l] += c, b[r + 1] -= c;  // 核心操作

// 对差分数组b求一次前缀和，还原数组
for (int i = 1; i <= x; i++) // i从1开始
  b[i] += b[i - 1]

• 二维差分（推荐画图推导）

// 修改一次二维差分数组（左上 [x_1,y_1]，右下 [x_2,y_2] ) 
void update(int x_1, int y_1, int x_2, int y_2, int c) {
    b[x_1][y_1] += c;
    b[x_1][y_2 + 1] -= c;
    b[x_2 + 1][y_1] -= c;
    b[x_2 + 1][y_2 + 1] += c;
}

---

刷题题单 🧑🏻‍💻

刷题题单与相应题解请见博客：信息奥赛题单｜前缀和差分🔗

如链接失效，可以在文章末尾选择上一篇博客 或 在搜索界面搜索关键词「前缀和差分」即可。

参考资料 📚

• AcWing算法基础课 - https://www.acwing.com/activity/content/11/
• AcWing代码模版 - https://www.acwing.com/blog/content/277/