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
1 Like
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
2 Likes
And here is a good tutorial for BIT trees http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees