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

• 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]=∑i=0jscores[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. 均值、方差

v==1b−a+1∑i=ab(A[i]−μ)2∑i=abA[i]2b−a+1−μ2

3. 從一維到二維數組

記，psum[y,x]=∑i=0y∑j=0xA[i,j]，則從 (y1,x1) 到 (y2,x2) 之間矩形所包含元素的和，

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;
}