## Find Sum (i … j) in a list

The problem is to sum the ith to jth element of a given list. The easiest solution runs in $\mathcal{O}(n)$ time, which starts are the ith index and adds up the numbers in the list until it reaches the jth index. In this post i will show the process of calculating the sum of elements i through j both inclusive (where $i \le j$), which takes $\mathcal{O}(1)$ time for finding the sum, and $\mathcal{O}(n)$ time and space for preprocessing the given list of length n.

### Problem

Let there be a list $x_0, x_1, \ldots, x_n$. Then the function $sum (i, j)$ is defined as follows:

$sum (i, j) = x_i + x_{i+1} + \ldots + x_{j-1} + x_j$ for $i \le j \le n$

we need to make $sum (i, j)$

### $\mathcal{O}(n)$ runtime solution

This is a straight forward solution which simply starts adding the numbers in the list from the ith index to jth index.

### Sourcecode

The function for this process is shown below


/* Return the sum (i, j). Takes O(1) time
*/
int
sum (int i, int j, int *list)
{
int s = 0;

while (i<=j)
{
s += list[i];
i++;
}
return s;
}



### $\mathcal{O}(1)$ runtime solution

In this case we need an auxiliary array in which we do a simple preprocessing on the given list and store. Using this preprocessed list we find the required sum in $\mathcal{O}(1)$ time. We need an additional array of length (n + 1) to hold the preprocessed data. The preprocessed $p$ list is defined as follows.

$p_{i}=\sum_{j=0}^{i-1}x_{i}$ where $0 \le i \le n+1$

that is:

p[0] = 0
p[1] = x[0]
p[2] = x[0] + x[1]
p[3] = x[0] + x[1] + x[2]
.
.
.
p[n + 1] = x[0] + x[1] + x[2] + ... + x[n]


This process takes $\mathcal{O}(n)$ time, and the additional space taken by the preprocess list takes $\mathcal{O}(n)$ memory.

To retrieve the $sum (i, j)$ from the preprocessed array we need to perform the following operation:

$sum (i, j) = p_{j+1} - p_i$ where $0 \le i \le j \le n$

For example lets take the list $x_0, x_1, x_2, x_3, x_4$. Then the preprocessed list will be

$p_0 = 0$
$p_1 = x_0$
$p_2 = x_0 + x_1$
$p_3 = x_0 + x_1 + x_2$
$p_4 = x_0 + x_1 + x_2 + x_3$
$p_5 = x_0 + x_1 + x_2 + x_3 + x_4$

And example of the sum of the elements 1 through 3 (both inclusive) will be:

$sum (1, 3) = p_4 - p_1 = (x_0 + x_1 + x_2 + x_3) - (x_0) = x_1 + x_2 + x_3$

### Sourcecode

#include <stdio.h>
#include <stdlib.h>

/* Function to make the preprocess list from the input list
* This takes O(n) time.
*/
void
preprocess_list (int *list, int n, int *preprocess)
{
int i, s = 0;

for (i = 0; i <= n; i++)
{
preprocess[i] = s;
s += list[i];
}
}

/* Return the sum (i, j). Takes O(1) time
*/
int
sum (int i, int j, int *preprocess, int n)
{
if ((i > j) || (i >= n) || (j >= n) || (i < 0) || (j < 0))
{
}
return preprocess[j + 1] - preprocess[i];
}

/* Driver function to demonstrate the sum (i, j) function.
*/
int
main (void)
{
int *list, n, *preprocess;
int i, j, k;

printf ("\nEnter list elements: ");
scanf (" %d", &n);

list = malloc (sizeof (int) * n);
preprocess = malloc (sizeof (int) * n);

printf ("\nEnter the list elements: ");
for (k = 0; k < n; k++)
{
scanf (" %d", &list[k]);
}

preprocess_list (list, n, preprocess);

/* Enter out of bounds index to exit the program */
while (1)
{
printf ("\n\nTo get sum (i, j) Enter i, j: ");
scanf (" %d %d", &i, &j);

if ((i < n) && (j < n) && (i >= 0) && (j >= 0))
{
printf ("\nsum (%d, %d) = %d", i, j, sum (i, j, preprocess, n));
}
else
{
printf ("\nIndex out of bounds. quit.");
break;
}
}

free (list);
free (preprocess);

printf ("\n");
return 0;
}



### Sample Output

Enter list elements: 5

Enter the list elements: 1 2 3 -4 5

To get sum (i, j) Enter i, j: 1 3

sum (1, 3) = 1

To get sum (i, j) Enter i, j: 0 4

sum (0, 4) = 7

To get sum (i, j) Enter i, j: 3 1

sum (3, 1) = 0

To get sum (i, j) Enter i, j: -1 0

Index out of bounds. quit.