The problem is to sum the `i ^{th}` to

`j`element of a given list. The easiest solution runs in time, which starts are the

^{th}`i`index and adds up the numbers in the list until it reaches the

^{th}`j`index. In this post i will show the process of calculating the sum of elements

^{th}`i`through

`j`both inclusive (where ), which takes time for finding the sum, and time and space for preprocessing the given list of length

`n`.

### Problem

Let there be a list . Then the function is defined as follows:

for

we need to make

### runtime solution

This is a straight forward solution which simply starts adding the numbers in the list from the `i ^{th}` index to

`j`index.

^{th}### 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; }

### 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 time. We need an additional array of length `(n + 1)` to hold the preprocessed data. The preprocessed list is defined as follows.

where

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 time, and the additional space taken by the preprocess list takes memory.

To retrieve the from the preprocessed array we need to perform the following operation:

where

For example lets take the list . Then the preprocessed list will be

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

### 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 0x7eadbeef; } 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.