hey! i was wondering that is there any other way to solve such problems except using segment tree(for finding the sum in the range) and using (factorial,inverse factorial,dynamic programming , so that it could run in given time limit) , the way i did it…
i saw some of the solutions of users like @kutengine and i did not understand it…
any help there… thanks in advance.
thats an alternative for segment tree… if i’m not wrong…, but is there any totally different implementation for this particular problem
@priyanshuid: without segment tree / fenwick tree how do u manage to keep the list of berries updated for 1e5 queries ?
@iitr_sonu and @thecodergame …you mind going through this solution and explaining me which DS this gentleman has used… thanks in advance.
http://www.codechef.com/viewsolution/2197920
i have given the link to the topcoder tutorial for the same (Binary Indexed Tree/ or fenwick tree), go through it, you’ll get the idea.
Once more here
thanks…
and apart from these approaches, segment tree, or interval trees or BIT, you wont be able to make it in the time limit, these query type questions mostly uses these DS for fast caluclation , and best suited for these kind of problems.
BIT (Fenwick tree)
Range queries with updates (Dynamic range queries) can be done in O(nlogn) using Segment/Fenwick Trees.
Summation Range queries without updates (Static range queries) can be done in O(n) using arrays that store cumulative sums.
I have used square root decomposition to solve this problem . It is neither Fenwick tree nor segment tree .
1 Like
@vineetpaliwal could you throw some light on the method… or provide some link for same… thanks in advance…
The alternative solution to using segment tree is using Binary Indexed Tree, also named as Fenwick tree or BIT. This data structure can calculate the summation of a range in O(logn) update and query. Here is a good tutorial to learn it: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
Actually its O(logn)
I just refreshed the page and found out that people have already answered with the same response 
My bad. Put the n in there by mistake.
@priyanshuid : This is the link
Read the paragraph which is under this heading :
An O(N), O(sqrt(N))> solution
please provide any link to learn this new method