There are four questions here. They need interpretation. The first question is how to find the sum of a sub-array of an array of numbers, the brute-force way. "brute-force" means direct and not necessarily efficient way. The second question is how to produce the prefix-sums (see below) and query the prefix-sums for any sub-array sum. The third question is to produce an efficient and average way on how to obtain the sum of the sub-array, while the array is being updated, to result in a different sub-array sum. The fourth question is direct, assuming that the reader knows the meaning of time complexity.

The complete solution is addressed under the following headings, where the word "query" means "find the sum of a sub-array":

14.1 Query and Update the Brute-force Way
14.2 Query and Update through Prefix-Sums
14.3 Query and Update through Fenwick (Binary Indexed) Trees (see below)
14.4 Time Complexity for Pre-processing, Query and Update

The four headings correspond to the four questions respectively.

This is a teaching document, so to answer in an interview, the candidate has to do some summarizing.

14.1 Query and Update the Brute-force Way

Assume that there is an array with the following 8 numbers:

2, 4, 6, 8, 10, 12, 14, 16

Adding all the eight numbers (2, 4, 6, 8, 10, 12, 14, 16), needs eight main operations in the computer (roughly). Adding the first three numbers (2,4,6), needs three main operations in the computer (roughly). Adding the next four numbers (6,8,10, 12) after the second, needs four main operations in the computer (roughly). Adding the last two numbers (14,16), needs two main operations in the computer (roughly).

The whole array is also considered as a sub-array. So querying here needs a maximum of 8 main operations. The time complexity is the maximum number of main operations. The query time complexity for the brute-force way is written as: O(N), where N here is 8, the length of the array.

Updating or replacing an element in the brute-force scheme, takes 1 main operation. This is because, the new value is simply assigned, by code, to the indexed array element. That is referred to as O(1) time complexity or constant time.

Brute-force Program

There are two functions here: the query() function, and the update() function. The query() function takes as arguments: the start index of the sub-array, and the last index of the sub-array (inclusive). The update() function takes as arguments: the index of the element whose value needs replacement and the new value.

The program below, looks for the sum of the sub-array from index 2 to index 5 (inclusive) of the array, [2, 4, 6, 8, 10, 12, 14, 16]. The sub-array is {6, 8, 10, 12} . The sum of the sub-array is 36. After that, the value for the fourth index is changed from 10 to 11 and the sum of the sub-array is looked for, again; to give 37.

The program is:

#include <stdio.h>

int A[] = {2, 4, 6, 8, 10, 12, 14, 16};

void update(int r, int val) {
    A[r] = val;
}

int query(int u, int v) {
    int subSum = 0;
    for (int i=u; i<=v; i++) {
        subSum = subSum + A[i];
    }
    return subSum;
}

int main(int argc, char **argv) {
    int ret1 = query(2, 5);
    printf("%i\n", ret1);
    
    update(4, 11);
    int ret2 = query(2, 5);
    printf("%i\n", ret2);

    return 0;
}

The output is:

36
37

14.2 Query and Update through Prefix-Sums

Prefix-sums or running-sums or running total is obtain according to the following table:

There are two arrays that have the same indexes for corresponding values. The first row in the table shows the indexes for the two arrays. The second row has the given array. The third row has the prefix sums, also called running sums, which is also called running total.

The prefix sums array consists of the totals of all the previous values in the given array. Before addition begins, the prefix-sum is 0. In the table, this 0 is just in front of the prefix-sums useful numbers. The first value in the above given array is 2; the second value in the given array is 4; third is 6; fourth is 8 and so on. Let the prefix sums array be denoted by P.

P[0] = 0+2 = 2
P[1] = 0+2+4 = 2+4 = 6
P[2] = 0+2+4+6= 6+6 = 12
P[3] = 0+2+4+6+8 = 12+8 = 20
P[4] = 0+2+4+6+8+10 = 20+10 = 30
P[5] = 0+2+4+6+8+10+12 = 30+12 = 42
P[6] = 0+2+4+6+8+10+12+14 = 42+14 = 56
P[7] = 0+2+4+6+8+10+12+14+16 = 56+16 = 72

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

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

where A is the name of the given array. The total number of elements in the given array is 8. Here N = 8. The total number of useful elements in the prefix-sums array (excluding the first 0) is also N = 8, here.

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

    s = P[v] – P[u-1]

where v is the index of the last element of the sub-array (included) and u is the index of the element just before the first element of the sub-array. To obtain, s the computer needs to do just one main operation (subtraction). And so the time complexity to obtain s is O(1), also known as constant time. The time complexity to produce the whole prefix sums array of N elements is O(N).

In the prefix sums scheme, producing all the prefix-sums is known in general terms as pre-processing. So the time complexity for preprocessing here, is O(N).

Querying here takes O(1) time because of the single operation of subtraction.

On the other hand, updating takes O(N) time, actually O(1+8) time here, because after the single value is replaced in the given array, most (if not the whole) prefix-sums array has to be reproduced.

Prefix-Sums Program

There are three functions here: the preprocess() function, the query() function and the update() function. The preprocess() function produces the prefix-sums array for all the prefix sums. The query() function takes as arguments: the start index of the sub-array, and the last index of the sub-array (inclusive). The update() function takes as arguments: the index of the element whose value needs replacement, and the new value. The update() function here, also reproduces all the prefix-sums (prefix array), by calling the preprocess() function. There has to be a new prrefix-sums array content, before the next new update.

The program below, first does the pre-processing (produces the first content of the prefix-sums array), by calling preprocess(). Then the program looks for the sum of the sub-array from index 2 to index 5 (inclusive) of the array, [2, 4, 6, 8, 10, 12, 14, 16], by calling query(2, 5). The sub-array is {6, 8, 10, 12} . The sum of the sub-array is 36. After that, the value for the fourth index is changed from 10 to 11, by calling update(4, 11); and the sum of the sub-array is looked for, again, by calling query(2, 5), to give 37.

The program is:

#include 

int A[] = {2, 4, 6, 8, 10, 12, 14, 16};
int N=8;
int P[8];

void preprocess() {
    P[0] = A[0];
    for (int i=1; i<=N; i++) {
        P[i] = P[i-1] + A[i];
    }
}

void update(int r, int val) {
    A[r] = val;
    preprocess();
}

int query(int u, int v) {
    int s = P[v] - P[u-1];
    return s;
}

int main(int argc, char **argv) {
    preprocess();

    int ret1 = query(2, 5);
    printf("%i\n", ret1);
    
    update(4, 11);
    int ret2 = query(2, 5);
    printf("%i\n", ret2);

    return 0;
}

The output is:

   36
   37

14.3 Query and Update through Fenwick (Binary Indexed) Trees (see below)

The brute-force approach has no preprocessing structure. The prefix-sums approach has a preprocessing structure, which is the prefix-sums array itself. There is another approach which has a preprocessing structure, called the Fenwick Tree.

Time Complexities

Brute-force Approach

The query time complexity for the brute-force approach is O(N).
The update time complexity for the brute-force approach is O(1).

Prefix Sums Approach

The query time complexity for the prefix sums approach is O(1).
The update time complexity for the prefix sums approach is O(N).

It should interest the reader, that the time complexity to produce the prefix sums is O(N).

Fenwick Tree Approach (see below)

The query time complexity for the Fenwick Tree approach is O(log₂N).
The update time complexity for the Fenwick Tree approach is O(log₂N).

Comparing Prefix Sums Approach and Fenwick Tree Approach

The comparison is made here only for the query time and update time, and not for all the features that are comparable.

Consider a given array of length 8. That is N = 8. log₂8 = 3 .

With the prefix sums approach, a query activity followed by an update activity, would produce 1 + 8 = 9 main operations, from O(1) + O(8) time. With the Fenwick Tree approach, a query activity followed by an update activity, would produce 3 + 3 = 6 main operations, from log₂8 + log₂8 time.

Notice that the Fenwick Tree approach is faster than the prefix sums approach.

Teaching the Fenwick Tree approach takes a long document, longer than this whole document. So only the pseudo code for the Fenwick Tree approach, without the main function, is presented here. The reader should consult some other document for the full treatment (lesson) with Fenwick Tree.

Pseudo Code for the Fenwick Tree Approach

The pseudo code is:

A = Array[N]
Tree = Array[N+1]

FUNCTION sum(end)
	result = 0
	WHILE end > 0
		result += tree[end]
		last_one = end & -end
		end -= last_one
	END WHILE
	RETURN result

FUNCTION query(tree, index) is
    sum := 0
    while index > 0 do
        sum += tree[index]
        index -= lsb(index)
    return sum

FUNCTION update(tree, index, value) is
    while index < size(tree) do
        tree[index] += value
        index += lsb(index)

The first two lines are for the two arrays: the given array and the Fenwick Tree array.

14.4 Time Complexity for Pre-processing, Query and Update

Three solutions have been presented in this document: the brute force approach, the prefix sums approach and the Fenwick Tree approach.

The brute force approach has no preprocessing. The preprocessing for the prefix sums approach is the production of the prefix sums array. The preprocessing for the Fenwick Tree approach is the production of the Fenwick Tree.

Brute-force Approach

The query time complexity for the brute-force approach is O(N).
The update time complexity for the brute-force approach is O(1).

Prefix Sums Approach

The preprocessing time complexity for the prefix sums approach is O(N).
The query time complexity for the prefix sums approach is O(1).
The update time complexity for the prefix sums approach is O(N).

Fenwick Tree Approach

The preprocessing time complexity for the Fenwick Tree approach is O(N). Reason: see later.
The query time complexity for the Fenwick Tree approach is O(log2N). Reason: see later.
The update time complexity for the Fenwick Tree approach is O(log2N). Reason: see later.