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.
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...