Somma cumulativa del sottoarray

Una somma cumulativa è un array contenente tutte le somme degli elementi di un array fino a quell'indice.

Per esempio, 

Arr={1,2,3,4}

per i=0 la somma cumulativa sarà 1

per i=1 la somma cumulativa sarà 1+2=3

per i=2 la somma cumulativa sarà 1+2+3=6

per i=3 la somma cumulativa sarà 1+2+3+4=10

Quindi l'array cumulativo diventa {1,3,6,10}

Un modo per calcolarla è usare due cicli annidati, calcolare la somma e memorizzarla in un array. Per esempio:

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

L'altro modo, e il più efficiente, per calcolare l'array cumulativo è aggiungere l'elemento corrente alla somma precedente.

Arr={1,2,3,4}

cumArr[] è l'array cumulativo.

1. cumArr[0]=1
2. cumArr[1]=prev sum+Arr[1] = 1 + 2 = 3
3. cumArr[2]=prev sum+Arr[2] = 3 + 3 = 6
4. cumArr[3]=prev sum+Arr[1] = 6 + 4= 10

Può essere eseguito così:

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

Quiz

Quale pensi che sarà la complessità temporale di entrambi questi approcci??