RANGE SUM QUERY WITH PREFIX SUM(without updating the values) :

                         If You are already familiar with this topic, this will look silly to you. Yeah,purpose of this post is to introduce the concept of prefix sum which will help you while learning segmentation trees.

Throwing some light on it :-

      You are given an array.Now you are going to given some queries which requires you to calculate the sum of the elements in the array between the two indices l,r(consider).Yes, naive solution of keep tracking the range and calculating the cumulative sum between the respective indices will answer this problem in O(q*n) in the worst case.What if you are going to given a reduced time limit.Definitely your naive solution will time out then. TO overcome this TLE,you are going to use a prefix sum method which will answer your queries in O(1)<constant time> in the worst case.

Calculation :

      Just declare an array to store the sum. now at 0th index store the first element.Then at the every "ith" index store the sum of the prefix_sum[i-1]+ith element.Tricky part of answering the queries starts here.

Answering Queries :-

       case 'I'  :

             If the given 'l' value is 0 then just return the prefix_sum[r] as the sum.

          case 'II' :

             If the given l == r then all you need to return now is the element at the respective index(this is not the normal case,so don't bother about it.) .

          Case 'III':

             If l>=0 and r<=n then return the Prefix_sum[r]-Prefix_sum[l-1]. If l == 0 and r == n-1(0 based index),return the Prefix_sum[r] as the answer.

Source Code :-  Ideone

import sys

lists = list(map(int,sys.stdin.readline().split()))

q = input()

prefix_sum = []

prefix_sum.append(lists[0])

for i in range(1,len(lists)) :

  prefix_sum.append(prefix_sum[-1]+lists[i])

for i in range(q) :

  l , r = map(int,sys.stdin.readline().split())

if l == 0 :

print prefix_sum[r]

else :

print prefix_sum[r] - prefix_sum[l-1]

Tat's it...wait for the next article on segmentation trees useful while updation of the array elements is also given.

THANKS FOR READING...!!!

Read More