Prefix_Sum

Revision en7, by eng_OmarMohamed, 2021-02-01 07:30:59

First of all we have to distinguish between two types of an array:
1. Static Array i.e The array values are never updated between the queries
2. Dynamic Array

In range queries our task is to calculate a value based on a subarray of an array.
Types of range queries are:
1. sum(a, b)
2. min(a, b)
3. max(a, b)
Where a, b here stand for the beginning and the ending of the interval

What we're interested in here is the Static Array queries and we will begin with the sum queries


So given an array like this if we want to calculate sum(3, 7)  the first thing may come to your mind is using a loop over this range and we are done. and that's totally fine and the simplest solution the better

int result = 0;
for (int i = 2; i <= 6; i++) {
    result += arr[i];
}

But what if we have a lot of queries ? The running time of the previous naive approach is O(nq) where n is the range length and q is the number of queries.

So before dealing with the queries we will make some preprocessing and construct Prefix Sum Array, And the way to do this is very simple:
1. make an array with size equal to the original array + 1
2. the initial value for the first element is zero Because we need to calculate every cell value using the previous calculated one. and if we used the same array size we will go beyond the array boundary while calculating the first cell.

Then loop through the original array and calculate the prefix sum array as following:
prefix0 = a0
prefix1 = a0 + a1 = a1 + prefix0
prefix2 = a0 + a1 + a2 = a2 + prefix1
....

we will end up with something like this:-

As we can see the first cell holds only the first value in the array, the second cell hold the sum of the first two values and the third cell holds the first three values and so on...

Back to the sum query we can now calculate any query in O(1) using this array.
For example: sum(3, 7) is prefix[7] — prefix[2]

Implementation

int numbers[] = {7, 11, 6, 55, 98, 45, 16, 96, 46};  // length = 9
int prefix[10];
prefix[0] = 0;
for (inti = 1; i < 10; i++)  {
    prefix[i] = prefix[i - 1] + numbers[i - 1];
}
Tags #range query, #preffix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English eng_OmarMohamed 2021-02-01 09:45:17 472 Tiny change: 'm/961/B)\n\n\n' -> 'm/961/B)\nand there is some more listed in the comments. \n\n\n'
en11 English eng_OmarMohamed 2021-02-01 07:55:30 60
en10 English eng_OmarMohamed 2021-02-01 07:37:11 750 Tiny change: '56c.jpg)\n the fir' -> '56c.jpg)\n\n the fir'
en9 English eng_OmarMohamed 2021-02-01 07:35:03 748
en8 English eng_OmarMohamed 2021-02-01 07:32:46 749
en7 English eng_OmarMohamed 2021-02-01 07:30:59 747
en6 English eng_OmarMohamed 2021-02-01 07:28:24 753
en5 English eng_OmarMohamed 2021-02-01 07:26:40 749
en4 English eng_OmarMohamed 2021-01-31 21:16:38 6100 post v.1 (published)
en3 English eng_OmarMohamed 2021-01-31 18:57:02 1835 Tiny change: ' (int i = 0; i < 9; i++) {\n' -> ' (int i = 2; i <= 6; i++) {\n'
en2 English eng_OmarMohamed 2021-01-31 18:19:10 1518 adding two photos
en1 English eng_OmarMohamed 2021-01-31 18:01:44 997 Initial revision (saved to drafts)