当前位置：首页 > news >正文

【一维前缀和+差分】

news 2025/7/15 9:33:33

一、一维前缀和

1.1 定义

给定一个数组 a[1..n]，其前缀和数组 pre[1..n] 定义为：

$\dots + a[i]$

即 pre[i] 表示原数组从第 1 项到第 i 项的和。

1.2 构建

int a[N], pre[N];
for (int i = 1; i <= n; i++) 
{pre[i] = pre[i - 1] + a[i];
}

1.3 区间求和

使用前缀和可以在 $O (1)$ 时间内求任意区间 $[l, r]$ 的和：

$s u m = p re [r] - p re [l - 1]$

1.4 应用场景

快速计算区间和
优化暴力 $O(n^2)$ 的区间统计问题为 $O (n)$

1.5 示例

// 输入一个数组，求多个区间 [l, r] 的和
int a[N], pre[N];
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];while (q--) 
{int l, r;cin >> l >> r;cout << pre[r] - pre[l - 1] << '\n';
}

二、一维差分数组

2.1 定义

对于原数组 a[1..n]，其差分数组 diff[1..n] 定义为：

$1]\ \ (i \geq 2),\ \ diff[1] = a[1]$

通过差分数组可以快速实现对一个区间 $[l, r]$ 的所有值同时加上一个数 $d$ 。

2.2 构建

int a[N], diff[N];
diff[1] = a[1];
for (int i = 2; i <= n; i++) 
{diff[i] = a[i] - a[i - 1];
}

2.3 区间加法操作

若想对区间 $[l, r]$ 所有数加上 $d$ ，只需：

diff[l] += d;
diff[r + 1] -= d;

原理在于：差分数组记录的是“增量”，只需要在区间起点加一个数、在区间终点的下一位减去这个数，就能确保中间所有位置都累加这个值。

然后通过前缀和还原整个数组：

a[1] = diff[1];
for (int i = 2; i <= n; i++) 
{a[i] = a[i - 1] + diff[i];
}

2.4 区间减法操作

若想对区间 $[l, r]$ 所有数减去 $d$ ，也可以使用差分数组：

diff[l] -= d;
diff[r + 1] += d;

原理类似：差分数组记录的是“增量”，如果我们想对一个区间 $[l, r]$ 的所有元素减去 $d$ ，只需要在区间起点加上 $- d$ ，在区间终点的下一位加上 $+ d$ ，就能确保整个区间内的值都减少 $d$ ，而其他位置不受影响。这与区间加法操作完全对称，只是将 $d$ 替换为 $- d$ 。

2.5 应用场景

多次区间加操作（比树状数组/线段树更快）
多次构造某种“影响”或“变化”的模型（如教室占用、涨价、染色）

2.6 示例

// 初始数组为 0，对多个区间加值，输出最终数组
int diff[N] = {0};
cin >> n >> m; // n 个元素，m 次操作
for (int i = 1; i <= m; i++) 
{int l, r, d;cin >> l >> r >> d;diff[l] += d;diff[r + 1] -= d;
}// 还原结果数组
int a[N];
a[0] = 0;
for (int i = 1; i <= n; i++) 
{a[i] = a[i - 1] + diff[i];cout << a[i] << ' ';
}