前缀和数组

前缀和数组是一种用于快速计算数组中连续子数组和的数据结构。

给定一个数组 $A = [A_1, A_2, \ldots, A_n]$，

前缀和数组 $S$ 定义为 $S[i] = A_1 + A_2 + \cdots + A_i$。

我们可以通过 $S$ 快速计算出任意子数组 $A[l, r]$ 的和，即 $A[l] + A[l+1] + \cdots + A[r] = S[r] - S[l-1]$（注意当 $l = 1$ 时，$S[l-1] = S[0] = 0$）。

示例

给定数组 $A = [3, 1, 4, 1, 5, 9, 2, 6]$，我们首先计算其前缀和数组 $S$：

$S[1] = A[1] = 3$
$S[2] = A[1] + A[2] = 3 + 1 = 4$
$S[3] = A[1] + A[2] + A[3] = 3 + 1 + 4 = 8$
$S[4] = A[1] + A[2] + A[3] + A[4] = 3 + 1 + 4 + 1 = 9$
$S[5] = A[1] + A[2] + A[3] + A[4] + A[5] = 3 + 1 + 4 + 1 + 5 = 14$
$S[6] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 3 + 1 + 4 + 1 + 5 + 9 = 23$
$S[7] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] = 3 + 1 + 4 + 1 + 5 + 9 + 2 = 25$
$S[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] = 3 + 1 + 4 + 1 + 5 + 9 + 2 + 6 = 31$

所以，前缀和数组 $S$ 为 $[0, 3, 4, 8, 9, 14, 23, 25, 31]$（注意 $S[0] = 0$）。

现在，我们可以通过前缀和数组 $S$ 快速计算任意子数组的和。

例如:

• 计算子数组$A[3] \dots A[6]$ 的和：
  

$A[3] + A[4] + A[5] + A[6] = S[6] - S[2] = 23 - 4 = 19$

因此，子数组 $A[3] \dots A[6]$ 的和为 19。

• 计算子数组$A[4] \dots A[6]$ 的和
  $A[4]+A[5]+A[6] = S[6]-S[3]$

因此,子数组$A[4] \dots A[6]$ 的和为$15$

结论 计算$A[l] \dots A[r]$之前所有的元素和

$结果=S[r]-S[l-1]$

初始化

int A[110], S[110];
int main(){
  int n;
  cin>>n;
  for(int i=1; i<=n; i++){
    cin>>a[i];
    S[i]=S[i-1]+A[i];    //初始化前缀和数组
  }
  int l, r;
  cin>>l>>r;
  cout<<S[r]-S[l-1]<<endl; //求A[l]+...+A[r]
}

应用

前缀和数组在处理数组和的查询问题时非常有用，特别是在多次查询的情况下，可以显著提高效率。