int array[n]; // Assume this is already filled with
arbitrary <int>'s
int partial_sum[n]; // When fill_partial_sums() is called,
// partial_sum[i] =
array[0]+array[1]+...+array[i-1]
void fill_partial_sums()
{
int i;
partial_sum[0] = 0;
for (i = 1 ; i < n ; i++)
{
partial_sum[i] = partial_sum[i-1] + array[n-1];
}
}
int sum_from_i_to_j(int i, int j)
{
return partial_sum[j] - partial_sum[i];
}
O(1) time complexity :-)
O(n) memory usage
