Suma kumulacyjna podtablicy

Tablica sum częściowych to tablica wszystkich sum elementów danej tablicy aż do danego indeksu.

Na przykład, 

Arr={1,2,3,4}

dla i=0 suma częściowa wyniesie 1

dla i=1 suma częściowa wyniesie 1+2=3

dla i=2 suma częściowa wyniesie 1+2+3=6

dla i=3 suma częściowa wyniesie 1+2+3+4=10

Zatem tablica sum częściowych będzie miała postać {1,3,6,10}

Jednym ze sposobów obliczenia jej jest użycie dwóch zagnieżdżonych pętli, obliczenie sumy i zapisanie jej w tablicy. Na przykład:

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

Innym, najwydajniejszym sposobem obliczenia tablicy sum częściowych jest dodawanie bieżącego elementu do poprzedniej sumy.

Arr={1,2,3,4}

cumArr[] to tablica sum częściowych.

1. cumArr[0]=1
2. cumArr[1]=poprzednia suma+Arr[1] = 1 + 2 = 3
3. cumArr[2]=poprzednia suma+Arr[2] = 3 + 3 = 6
4. cumArr[3]=poprzednia suma+Arr[1] = 6 + 4= 10

Można to wykonać tak:

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

Łamigłówka

Jak myślisz, jaka będzie złożoność czasowa obu tych podejść?