The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Given an array of numbers, a forward running sum is the sum of all the previous numbers, from the beginning (left) of the array to an indexed element of interest, within the array. The summation normally begins with the first element, which is the first running sum. Next, is the total of the first two elements, which makes the second running sum. Next, is the total of the first three elements, which makes the third running sum; and so on.

Given an array of numbers, the backward running sums are the opposite of the forward running sums, beginning from the end (right) of the array.

Forward Running Sums

Consider the following array in a table:

The indexing is zero-based counting. The running sums are as follows:

3
7  = 3 + 4
6  = 3 + 4 + -1
11 = 3 + 4 + -1 + 5
13 = 3 + 4 + -1 + 5 + 2
7  = 3 + 4 + -1 + 5 + 2 + -6
13 = 3 + 4 + -1 + 5 + 2 + -6 + 6
21 = 3 + 4 + -1 + 5 + 2 + -6 + 6 + 8

Smart Forward Addition

The smart way to add these numbers consecutively, in the forward direction, is to be adding the previous sum (total) to the current number, as the following table shows:

Formulas

In general, the forward running sums are:

        r0 = a0, r1 = r0+a1, r2 = r1+a2, r3 = r2+a3, r4 = r3+a4, - - - ri = ri-1 + ai - - - rn = rn-1 + an

where a_i is the current given element, and r_i is the current running sum.

Read through the above list of additions, if that is not already done. That is, for any index, i from 1 to 7,

    R[i] = R[i-1] + A[i]

where A is the name of the given array, and R is the running sum. The total number of elements in the given array is 8. Here N = 8. The total number of elements in the running-sums array is also N = 8, here.

Smart Running Sums Program in O(n) Time

The following is a smart running sums program for the above array (read through the code and comments):

    #include <stdio.h>
    
    void runningSums(int A[], int N) { 
        int R[N]; 
        for (int i = 0; i < N; i++)    //not usually included in time complexity; initializing all elements to 0
            R[i] = 0; 

        R[0] = A[0];
        
        for (int k=1; k < N; k++)    //running sums, calculated from k=1 and not k=0
            R[k] = R[k - 1] + A[k];
        
        //output
        for (int i = 0; i < N; i++) 
            printf("%i, ", R[i]);
        printf("\n");
    } 

    int main(int argc, char **argv)
    {
        int A[] = {3, 4, -1, 5, 2, -6, 6, 8};
        int N = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        runningSums(A, N);

        return 0;
    }

The output is:

    3, 7, 6, 11, 13, 7, 13, 21, 

as expected.

The space complexity is given as O(N), actually O(2N), for arrays A[] and R[]. The temporary locations (variables) and the memory location for "int N" are ignored.

Forward Sub-array Sum

Another name for sub-array is slice.

Now, the sum of any sub-array in the given array is:

    s = R[v] - R[u-1]

where v is the index of the last element of the sub-array (included) and u is the index of the first element of the sub-array (included). This formula should be used instead of adding the individual numbers together, after the running sums have been obtained. To obtain s, the computer needs to do just one main operation (subtraction), using this formula. And so the time complexity to obtain s is O(1), also known as constant time. The time complexity to produce the whole running-sums array of N elements is O(N). The space complexity for this formula is given as just O(1), for the variable, s (temporary variables, internal to the computer are ignored, though they should not be ignored, in the strict sense).

Forward Sub-Array Sum from Running Sums

The following program uses the above subtraction formula to illustrate this, from index 2 to index 6, inclusive (read through the code and comments):

    #include <stdio.h>
    
    int runningSums(int A[], int N) { 
        int R[N]; 
        for (int i = 0; i < N; i++)    //not usually included in time complexity; initializing all elements to 0
            R[i] = 0; 

        R[0] = A[0];
        
        for (int k=1; k < N; k++)    //running sums, calculated from k=1 and not k=0
            R[k] = R[k - 1] + A[k];
            
        //sub array sum with formula
        int subArraySum = R[6] - R[2-1];
        
        return subArraySum;
    } 

    int main(int argc, char **argv)
    {
        int A[] = {3, 4, -1, 5, 2, -6, 6, 8};
        int N = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        int subArraySum = runningSums(A, N);
        printf("%i\n", subArraySum);
        
        return 0;
    }

The output is 6, as expected, since -1+5+2+-6+6 = -1+5+2-6+6 = 6. The time complexity is still given as O(N) and the space complexity is still given as O(N), each for O(8), for the whole program.

Backward Running Sums

Consider the following array (same as above) in a table:

The indexing is zero-based counting. The running sums from the right end, are as follows:

8
14 = 8+6
8 = 8+6+-6
10 = 8+6+-6+2
15 = 8+6+-6+2+5
14 = 8+6+-6+2+5+-1
18 = 8+6+-6+2+5+-1+4
21 = 8+6+-6+2+5+-1+4+3

Smart Backward Addition

The smart way to add these numbers consecutively, in the backward direction, is to be adding the previous sum (total) to the current number, going backwards, as the following table shows:

Formulas

In general, the backward running sums are:

        rn = an, rn-1 = rn+an-1, rn-2 = rn-1+an-2, rn-3 = rn-2+an-3, rn-4 = rn-3+an-4, - - - ri = ri+1 + ai - - - r0 = r0+1 + a0

where a_i is the current given element, and r_i is the current running sum.

Read through the above list of additions, if that is not already done. That is, for any index, i from 6 to 0 (backwards),

    R[i] = R[i+1] + A[i]

where A is the name of the given array, and R is the running sum. The total number of elements in the given array is 8. Here N = 8. The total number of elements in the running-sums array is also N = 8, here.

Smart Backward Running Sums Program in O(n) Time

The following is a smart backward running sums program for the above array (read through the code and comments):

    #include <stdio.h>
    
    void runningSums(int A[], int N) { 
        int R[N]; 
        for (int i = 0; i < N; i++)    //not usually included in time complexity; initializing all elements to 0
            R[i] = 0; 

        R[7] = A[7];
        
        for (int k=N-2; k >= 0; k--)    //running sums, calculated from k=6 and not k=7
            R[k] = R[k + 1] + A[k];
        
        //output
        for (int i = 0; i < N; i++) 
            printf("%i, ", R[i]);
        printf("\n");
    } 

    int main(int argc, char **argv)
    {
        int A[] = {3, 4, -1, 5, 2, -6, 6, 8};
        int N = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        runningSums(A, N);

        return 0;
    }

The output is:

    21, 18, 14, 15, 10, 8, 14, 8, 

as expected.

The space complexity is given as O(N), actually O(2N), for arrays A[] and R[]. The temporary locations (variables) and the memory location for "int N" are ignored.

Backward Sub-Array Sum

Another name for sub-array is slice.

Now, the sum of any backward sub-array in the given array is:

    s = R[u] - R[v+1]

where u is the index of the first element of the sub-array (included) and v is the index of the last element of the sub-array (included). This formula should be used instead of adding the individual numbers together, backwards, after the running sums have been obtained. To obtain s, the computer needs to do just one main operation (subtraction), using this formula. And so the time complexity to obtain s is O(1), also known as constant time. The time complexity to produce the whole backwards running-sums array of N elements is O(N). The space complexity for this formula is given as just O(1), for the variable, s (temporary variables, internal to the computer are ignored, though they should not be ignored, in the strict sense).

Backward Sub-Array Sum from Running Sums

The following program uses the above subtraction formula to illustrate this, from index 6 down to index 2, inclusive (read through the code and comments):

    #include <stdio.h>
    
    int bRunningSums(int A[], int N) { 
        int R[N]; 
        for (int i = 0; i < N; i++)    //not usually included in time complexity; initializing all elements to 0
            R[i] = 0; 

        R[7] = A[7];
        
        for (int k=N-2; k >= 0; k--)    //running sums, calculated from k=6 and not k=7
            R[k] = R[k + 1] + A[k];
        
        //backward sub array sum with formula
        int bSubArraySum = R[2] - R[6+1];
        
        return bSubArraySum;
    } 

    int main(int argc, char **argv)
    {
        int A[] = {3, 4, -1, 5, 2, -6, 6, 8};
        int N = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        int bSubArraySum = bRunningSums(A, N);
        printf("%i\n", bSubArraySum);

        return 0;
    }

The output is 6, as expected, since 6+-6+2+5+-1 = 6-6+2+5-1 = 6. The time complexity is still given as O(N) and the space complexity is still given as O(N), each for O(8), for the whole program.

Thanks for reading.