Prefix Sum : Query Time O(1) : Pre-processing Time O(n)

Range Sum is a popular problem in competitive programming and technical interviews. Range Sum problem asks sum of the elements in a range in a given array. Naïve approach requires O(N*Q) time which can be improved to be O(N+Q) using Prefix Sum approach. N is the size of the array and Q is the number of queries.