子数组的累积和

累积和数组是一个数组，其中的每个值都是原数组截至对应索引处的所有元素之和。

例如， 

Arr={1,2,3,4}

当 i=0 时，累积和为 1

当 i=1 时，累积和为 1+2=3

当 i=2 时，累积和为 1+2+3=6

当 i=3 时，累积和为 1+2+3+4=10

所以，累积和数组变为 {1,3,6,10}

一种计算方法是使用两个嵌套循环来计算总和，并将其存储在数组中。例如：

int k=0;                           

while(k<n){
  int sum=0;
  for(int j=0;j<k+1;j++){
    sum=sum+arr[j];
    
  }
  ans[k]=sum;
  k++;
}

另一种也是最高效的计算累积和数组的方法，是将当前元素加到前一个总和上。

Arr={1,2,3,4}

cumArr[] 是累积和数组。

1. cumArr[0]=1
2. cumArr[1]=前一个总和+Arr[1] = 1 + 2 = 3
3. cumArr[2]=前一个总和+Arr[2] = 3 + 3 = 6
4. cumArr[3]=前一个总和+Arr[1] = 6 + 4= 10

可以这样实现：

int sum=0;
for(int i=0;i<n;i++){
  sum=sum+arr[i];
  ans[i]=sum;
}

脑筋急转弯

你认为这两种方法的时间复杂度分别是多少？？