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

Given an vector of numbers, a forward running sum is the sum of all the previous numbers, from the beginning (left) of the vector to an indexed element of interest, within the vector. 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 vector of numbers, the backward running sums are the opposite of the forward running sums, beginning from the end (right) of the vector.

Forward Running Sums

Consider the following vector 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 vector, and R is the running sum. The total number of elements in the given vector is 8. Here N = 8. The total number of elements in the running-sums vector is also N = 8, here.

Smart Running Sums Program in O(n) Time

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

fn running_sums(a: &Vec<i32>) {
    let n = a.len();
    
    let mut r = vec![0; n];    //not usually included in time complexity; initializing all elements to 0

    r[0] = a[0];

    for k in 1..n {    //running sums, calculated from k=1 and not k=0
        r[k] = r[k - 1] + a[k];
    }

    //output
    for i in 0..n {
        print!("{}, ", r[i]);
    }
    println!();
}

fn main() {
    let a = vec![3, 4, -1, 5, 2, -6, 6, 8];
    running_sums(&a);    // Passed as a reference using &
}

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-vector Sum

Another name for sub-vector is slice.

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

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

where v is the index of the last element of the sub-vector (included) and u is the index of the first element of the sub-vector (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 vector 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-Vector 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):

fn running_sums(a: &Vec<i32>) -> i32 {
    let n = a.len();
    
    let mut r = vec![0; n];    //not usually included in time complexity; initializing all elements to 0
    
    r[0] = a[0];
    
    for k in 1..n {    //running sums, calculated from k=1 and not k=0
        r[k] = r[k - 1] + a[k];
    }
    
    //sub vector sum with formula
    let sub_array_sum = r[6] - r[2 - 1];
    
    sub_array_sum
}

fn main() {
    let a = vec![3, 4, -1, 5, 2, -6, 6, 8];
    let sub_array_sum = running_sums(&a);
    println!("{}", sub_array_sum);
}

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 vector (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 vector, and R is the running sum. The total number of elements in the given vector is 8. Here N = 8. The total number of elements in the running-sums vector 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 vector (read through the code and comments):

fn brunning_sums(a: &Vec<i32>) {
    let n = a.len();
    
    let mut r = vec![0; n];    //not usually included in time complexity; initializing all elements to 0

    r[7] = a[7];

    for k in (0..=n-2).rev() {    //running sums, calculated from k=6 and not k=7
        r[k] = r[k + 1] + a[k];
    }

    //output
    for i in 0..n {
        print!("{}, ", r[i]);
    }
    println!();
}

fn main() {
    let a = vec![3, 4, -1, 5, 2, -6, 6, 8];
    brunning_sums(&a);     // Passed as a reference using &
}

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-Vector Sum

Another name for sub-vector is slice.

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

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

where u is the index of the first element of the sub-vector (included) and v is the index of the last element of the sub-vector (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 vector 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-Vector 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):

fn brunning_sums(a: &Vec<i32>) -> i32 {
    let n = a.len();
    
    let mut r = vec![0; n];    //not usually included in time complexity; initializing all elements to 0
    
    r[0] = a[0];
    
    for k in (0..=n-2).rev() {    //running sums, calculated from k=6 and not k=7
        r[k] = r[k + 1] + a[k];
    }
    
    //backward sub vector sum with formula
    let bsub_array_sum = r[2] - r[6+1];
    
    bsub_array_sum
}

fn main() {
    let a = vec![3, 4, -1, 5, 2, -6, 6, 8];
    let sub_array_sum = brunning_sums(&a);
    println!("{}", sub_array_sum);
}

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.