i read rectangular query editorial…it is using a concept prefix sum…what kind of techinique is this??what is the advantage?why and for what kind of problems we use this technique?please help me to learn this idea…thanks

Well, the perfect example i can give of prefix sum is this month’s problem MARBLEGF,

You are given an array of lets say n elements, then you are asked to calculate sum of ith to jth element, simple solution will be slow as number of queries are a lot. The idea is to maintain a array (say sum[N]) where ith element will contain sum of all the elements from 0th to ith element, eg:-

arr [1,4,2, 3, 1, 4, 1, 4]

sum [1,5,7,10,11,15,16,20]

the advantage is that for any query (sum from i to j) is simply sum[j]-sum[i-1] (i not equal to 0)

But in that particular problem there are update queries too, BIT or segment tree would be more useful in any case

And here is a good tutorial for BIT trees http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees