סכום מצטבר של תת־מערך

מערך של סכומים מצטברים הוא מערך של כל הסכומים של מערך עד לאינדקס הזה.

לדוגמה, 

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}

אחת הדרכים לחשב אותו היא להשתמש בשתי לולאות מקוננות, לחשב את um ולשמור אותו במערך. כך:

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]=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

אפשר לבצע זאת כך:

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

חידת חשיבה

מה לדעתך תהיה סיבוכיות הזמן של שתי הגישות האלה??