部分和（partial sum）在算法求解中的作用

大家好，欢迎来到IT知识分享网。

• C++ 的 STL 库的 <numeric> 头文件的 partial_sum 函数已实现了对某一序列的 partial sum。
  
  • partial_sum(first, last, dest);

  
  

1. 部分和的引入

并非什么高级深奥的技巧，但却十分有用。

假设按照降序排列 $N$ 个学生的考试成绩并保存到数组 scores[]，现在想要编写求出从第 a 名到第 b 名成绩的函数 average(a, b)，最简单的方法是，将 scores[a] 到 scores[b] 的乘积全部相加，然后除以 b-a+1。

这种方法的循环次数最大会达到 $O(N)$。如果只计算 1 次平均值，这种时复杂度就足够了。但多次调用 average() 的话，就需要对函数进行优化。

此时需要用到部分和（partial sum）（或者累加和）的概念。部分和就是，对从数组起始位置到当前任一位置求和并保存的数组（类似于概率理论中的分布函数的概念）。

$$pSum[j]=\sum_{i=0}^jscores[i]$$

预先计算 psum 就能在 $O(1)$ 时间内求出 scores[] 在特定区间的和（君子）。假设 psum[-1] = 0，那么，scores[a] 和 scores[b] 之间的和可按照如下方式计算：

$$psum[b]-psum[b-a+1]$$

部分和的简单计算：

int A[101], pSum[101], pSqSum[101]; sort(A, A+n); pSum[0] = A[0];  pSqSum[0] = A[0]*A[0]; for (int i = 1; i < n; ++i){ 
    pSum = pSum[i-1] + A[i]; pSqSum = pSqSum[i-1] + A[i]*A[i]; }

一定千万要注意，在求解某一区域的部分和的时候，比如 [a, b]，pSum[a] 本身是包含数组在 a 处的值的，

// ∑_a^b A[i] ⇒ pSum[b] - (a == 0 ? 0 : pSum[a - 1]);

2. 均值、方差

$$\begin{split} v=&amp;\frac1{b-a+1}\sum_{i=a}^b\left(A[i]-\mu\right)^2\\ =&amp;\frac{\sum\limits_{i=a}^bA[i]^2}{b-a+1}-\mu^2 \end{split}$$

3. 从一维到二维数组

记，$\text{psum}[y, x]=\sum\limits_{i=0}^y\sum\limits_{j=0}^xA[i,j]$，则从 $(y_1,x_1)$ 到 $(y_2,x_2)$ 之间矩形所包含元素的和，

$$\text{sum}([y_1,x_1], [y_2,x_2])=\text{psum}(y_2,x_2)-\text{psum}(y_2-1,x_1)-\text{psum}(y_1,x_2-1)+\text{psum}(y_1-1,x_1-1)$$

int gridSum(const vector<vector<int>>& psum, int y1, int x1, int y2, int x2) { int ret = psum[y2][x2]; if (y1 > 0) ret -= psum[y1-1][x2]; if (x1 > 0) ret -= psum[y2][x1-1]; if (x1 > 0 && y1 > 0) ret += psum[y1-1][x1-1]; return ret; }