33DAI：批量导入三三文档

2026-05-20T18:24:00Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第67行：		第67行：
	[[Category:进阶算法]]		[[Category:进阶算法]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:14Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 前缀和 ==

前缀和用于快速求'''区间和'''，预处理 <math>O(n)</math>，查询 <math>O(1)</math>。

=== 一维前缀和 ===

定义 <math>pre[i] = a[1] + a[2] + \cdots + a[i]</math>

区间 <math>[l, r]</math> 的和 = <math>pre[r] - pre[l-1]</math>

<syntaxhighlight lang="cpp">
vector<int> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];

// 查询 [l, r] 的和
int sum = pre[r] - pre[l - 1];
</syntaxhighlight>

=== 二维前缀和 ===

定义 <math>pre[i][j]</math> 为从 <math>(1,1)</math> 到 <math>(i,j)</math> 的矩阵和。

<syntaxhighlight lang="cpp">
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];

// 查询子矩阵 (x1,y1) 到 (x2,y2) 的和
int sum = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
</syntaxhighlight>

== 差分 ==

差分是前缀和的'''逆运算'''，用于快速进行区间修改。

=== 一维差分 ===

区间 <math>[l, r]</math> 加 <math>k</math>：

<syntaxhighlight lang="cpp">
int diff[MAXN];

// 区间 [l, r] 加 k
diff[l] += k;
diff[r + 1] -= k;

// 最后求前缀和得到最终结果
for (int i = 1; i <= n; i++)
diff[i] += diff[i - 1];
</syntaxhighlight>

=== 二维差分 ===

子矩阵 <math>(x1,y1)</math> 到 <math>(x2,y2)</math> 加 <math>k</math>：

<syntaxhighlight lang="cpp">
diff[x1][y1] += k;
diff[x2 + 1][y1] -= k;
diff[x1][y2 + 1] -= k;
diff[x2 + 1][y2 + 1] += k;

// 最后求二维前缀和得到最终结果
</syntaxhighlight>

[[Category:进阶算法]]
[[Category:三三文档]]

09-进阶算法/01-前缀和与差分 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档