前缀和：修订间差异

2022年2月20日 (日) 16:41的最新版本

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

你可以很简单的用递推来计算出一个数列的前缀和： [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];
}

参考资料

算法竞赛进阶指南，李煜东，21~22页

@@ 第1行： / 第1行： @@
-对于一个给定的数组A，它的前缀和数列S是能通过递推能求出的基本信息之一：
+对于一个给定的数列A，它的前缀和数列S的定义是：<math>S_i=\sum_{j=1}^i{A_j}</math>
+你可以很简单的用递推来计算出一个数列的前缀和：
 <math>
-S_i=\sum_{j=1}^i{A_j}
+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>
+== 参考资料 ==
+# 算法竞赛进阶指南，李煜东，21~22页
+[[Category:计算机]]