Given an array and query ranges to get sum of each range.

Question

I have an array suppose A={10,20,30,40,50} and query ranges like 1. 1 4 ie sum of (10+20+30+40) 1 to 4 elements of array and so on.
I tried to solve using brute force method simply
1. Input Array and Query ranges
2. foreach range L to R from Array
a. retrieve elements from array
b. store their sum
3. print sum
but this method has complexity of O( numberOfElementsInArray * SizeOfRange) ie O(mn). Is their any better solution exists ?

Answer 1

Hi,
I am just sharing my view on this, you have mentioned that it's complexity is O(mn), but it's not.

As Input to you as a query is Range of indices (Start Index, End Index)
So the sum you can get easily by

for(i = startIndex-1 ; i < EndIndex; i++)
{
sum = sum + arr[i];
}

Which is linear complexities O(N), where N = EndIndex - StartIndex, and in case of worst case N can be equal to number of element in the array.

Share your view on this.

Comments

time limit is one second and for the ranges like 1 to 10^9 it is not a good approach. you are doing brute force @sachidananda

---

ques is not like given an array and a query range .. but there are so many ranges like
array = 1,2,3,4,5,6,.........
query ranges like: 1-5
2-10
100-10000000
**********-1000000000000