前缀和:修订间差异

来自吾萌百科
无编辑摘要
(// Edit via Wikiplus)
 
(未显示1个用户的11个中间版本)
第1行: 第1行:
对于一个给定的数组A,它的前缀和数列S是能通过递推能求出的基本信息之一:<math>S_i=\sum_{j=1}^i{A_j}</math>
在算法的世界里,效率是永恒的追求。而“前缀和”就像一把利刃,能够帮助我们快速解决一系列涉及数组区间求和的问题。如果采用朴素的遍历求和方法,时间复杂度会达到 O(n),其中 n 是区间长度。而前缀和技巧可以将区间求和的时间复杂度降低到 O(1),大大提高了程序的效率。


一个部分和即数列A某个下标区间内的书的和,可表示为前缀和相减的形式:<math>sum(l,r)=\sum_{j=l}^r{A_j}=S_r-S_{L-1}</math>
 
==一维前缀和==
对于一个给定的数列A,它的前缀和数列S的定义是:<math>S_i=\sum_{j=1}^i{A_j}</math>
 
其中,Si 表示 A 中从第一个元素到第 i 个元素的和。特别地,我们定义 S0 = 0,表示空的前缀和。
 
你可以很简单的用递推来计算出一个数列的前缀和:
<math>
S_i=\begin{cases}
A_1 &i=1 \\
S_{i-1}+A_i&i>1
\end{cases}
</math>
 
一个部分和即数列A某个下标区间内的数的和,可表示为前缀和相减的形式:<math>sum(l,r)=\sum_{j=l}^r{A_j}=S_r-S_{l-1}</math>
 
 
 
=== 实现 ===
<syntaxhighlight lang="c" line>
#define SIZE 100001
 
int S[SIZE];
 
void init(int* A, int n) {
S[0] = A[0];
for (int i = 1; i < n; ++i)
S[i] = S[i - 1] + A[i];
}
 
int add(int l, int r) {
return S[r] - S[l - 1];
}
</syntaxhighlight>
 
==二维前缀和==
在二维数组(矩阵)中,可类似地求出二维前缀和,进一步计算出二维部分和。
 
对于一个二维数组(矩阵)A,其二维前缀和矩阵 S 的定义是:
<math>S_{i,j}=\sum_{k=1}^i\sum_{l=1}^j{A_{k,l}}</math>
 
其中,Si,j 表示 A 中以 (1,1) 为左上角,(i,j) 为右下角的子矩阵中所有元素的和。同样地,我们定义 S0,j = Si,0 = 0。
 
二维前缀和的计算也可以使用递推的方法:
 
<math>S_{i,j}= \begin{cases} 0 & i=0 \text{ or } j=0\\ A_{i,j} & i = 1 \text{ and } j = 1 \\ S_{i-1,j} + A_{i, j} & i > 1 \text{ and } j = 1\\ S_{i, j - 1} + A_{i, j} & i = 1 \text{ and } j > 1\\ S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} + A_{i,j} & i > 1 \text{ and } j > 1\\ \end{cases}</math>
 
二维前缀和的主要应用是快速计算子矩阵的元素之和。对于以 (x1, y1) 为左上角,(x2, y2) 为右下角的子矩阵,其元素之和可以表示为:
 
<math>sum(x1, y1, x2, y2) = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]</math>
== 参考资料 ==
# 算法竞赛进阶指南,李煜东,21~22页
[[Category:计算机]]

2024年6月23日 (日) 23:46的最新版本

在算法的世界里,效率是永恒的追求。而“前缀和”就像一把利刃,能够帮助我们快速解决一系列涉及数组区间求和的问题。如果采用朴素的遍历求和方法,时间复杂度会达到 O(n),其中 n 是区间长度。而前缀和技巧可以将区间求和的时间复杂度降低到 O(1),大大提高了程序的效率。


一维前缀和

对于一个给定的数列A,它的前缀和数列S的定义是:[math]\displaystyle{ S_i=\sum_{j=1}^i{A_j} }[/math]

其中,Si 表示 A 中从第一个元素到第 i 个元素的和。特别地,我们定义 S0 = 0,表示空的前缀和。

你可以很简单的用递推来计算出一个数列的前缀和: [math]\displaystyle{ S_i=\begin{cases} A_1 &i=1 \\ S_{i-1}+A_i&i\gt 1 \end{cases} }[/math]

一个部分和即数列A某个下标区间内的数的和,可表示为前缀和相减的形式:[math]\displaystyle{ sum(l,r)=\sum_{j=l}^r{A_j}=S_r-S_{l-1} }[/math]


实现

#define SIZE 100001

int S[SIZE];

void init(int* A, int n) {
	S[0] = A[0];
	for (int i = 1; i < n; ++i)
		S[i] = S[i - 1] + A[i];
}

int add(int l, int r) {
	return S[r] - S[l - 1];
}

二维前缀和

在二维数组(矩阵)中,可类似地求出二维前缀和,进一步计算出二维部分和。

对于一个二维数组(矩阵)A,其二维前缀和矩阵 S 的定义是: [math]\displaystyle{ S_{i,j}=\sum_{k=1}^i\sum_{l=1}^j{A_{k,l}} }[/math]

其中,Si,j 表示 A 中以 (1,1) 为左上角,(i,j) 为右下角的子矩阵中所有元素的和。同样地,我们定义 S0,j = Si,0 = 0。

二维前缀和的计算也可以使用递推的方法:

[math]\displaystyle{ S_{i,j}= \begin{cases} 0 & i=0 \text{ or } j=0\\ A_{i,j} & i = 1 \text{ and } j = 1 \\ S_{i-1,j} + A_{i, j} & i \gt 1 \text{ and } j = 1\\ S_{i, j - 1} + A_{i, j} & i = 1 \text{ and } j \gt 1\\ S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} + A_{i,j} & i \gt 1 \text{ and } j \gt 1\\ \end{cases} }[/math]

二维前缀和的主要应用是快速计算子矩阵的元素之和。对于以 (x1, y1) 为左上角,(x2, y2) 为右下角的子矩阵,其元素之和可以表示为:

[math]\displaystyle{ sum(x1, y1, x2, y2) = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1] }[/math]

参考资料

  1. 算法竞赛进阶指南,李煜东,21~22页