Tổng tích lũy của mảng con

Mảng tổng tích lũy là mảng chứa tổng các phần tử của một mảng tính đến từng chỉ số.

Ví dụ, 

Arr={1,2,3,4}

với i=0, tổng tích lũy sẽ là 1

với i=1, tổng tích lũy sẽ là 1+2=3

với i=2, tổng tích lũy sẽ là 1+2+3=6

với i=3, tổng tích lũy sẽ là 1+2+3+4=10

Vậy mảng tổng tích lũy sẽ là {1,3,6,10}

Một cách tính là dùng hai vòng lặp lồng nhau để tính tổng và lưu vào một mảng. Cụ thể:

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

Cách còn lại và hiệu quả nhất để tính mảng tổng tích lũy là cộng phần tử hiện tại với tổng trước đó.

Arr={1,2,3,4}

cumArr[] là mảng tổng tích lũy.

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

Có thể thực hiện như sau:

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

Câu đố

Bạn nghĩ độ phức tạp thời gian của cả hai cách tiếp cận này là bao nhiêu?