SGIFT  Sabbir and gifts
Sabbir is a little boy. he went to a gift shop with his mother. there were n different types of gifts in the shop . all gifts were attractive to sabbir. he wanted to buy all the gifts which are in price range . you are given prices of all the gifts and a , b . sabbir's mother need your help. please calculate the total amount of price of all gifts of that range for sabbir's mother.
Input
in the first line there will be n . number of gifts in the shop.
in the next line there will be n integers p_{1}, p_{2 }, p_{3 }... p_{n }denoting price of every gift
in the 3rd line there will be Q number of queries.
next Q lines contain two integes a and b
Output
print Q lines . every line contains one integer , sum of all prices for that range given in the query.
Example
Input: 7
1 3 2 1 5 2 2
4
1 2
1 5
3 5
4 5 Output: 8
16
8
5
NOTE: for first query sabbir will buy all the gifts of prices 1 , 2 , 1 , 2, 2 . so, sum is 8
for second query sabbir will buy all the gifts . so the sum is 16
hide comments
an09mous:
20200218 18:41:11
Did it using coordinate compression nd prefix array. 

dilip23:
20190528 16:03:39
Did anyone solve using Fenwick Tree? I am getting WA for few cases 

limon_88:
20190428 21:01:22
Nice problem @sabbir vai 

eulerkochy:
20181213 19:01:21
Prefix sum + binary search! : ) 

rifazn:
20180126 16:54:08
I sorted using python's built in sort method that sorts in O(n logn), then I used binary search for finding the lower bound, then again for finding the upper bound. Doing a sum(lowerbound, upperbound) makes the whole solution into O(n) which is maybe why I am getting a TLE. Is that what I am not doing right here? How can I do the sum in less than O(n) in this case? 

abhi1004:
20171211 20:10:37
Time limit is too strict for JAVA .


nadstratosfer:
20171013 18:18:18
I hardly sympathize with the bloatware called Java but the time limit here does make it a I/O challenge. O((n+q)*logn) in Python TLEs unless the code looks like a golfing solution. This shouldn't be necessary for AC. 

testing java:
20170911 15:13:07
What's the point of so strict time limit? I try to solve it in java, and because of time limits I do not know whether there is something wrong with algorithmic part of my code or I got TLE simply because my io isn't fast enough. It slightly spoils fun from solving problems Last edit: 20170911 15:46:33 

holmesherlock:
20170527 13:24:20
thanx a ton buddy @vengatesh15 

Shubham Jadhav:
20170517 20:26:11
O(n^2) works 
Added by:  sabbir 
Date:  20170226 
Time limit:  0.400s0.800s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 