COLLECT alternative

general
, ,
1

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.

2

I guess the other way is using Binary Indexed Tree,

3

thats an alternative for segment tree… if i’m not wrong…, but is there any totally different implementation for this particular problem

4

@priyanshuid: without segment tree / fenwick tree how do u manage to keep the list of berries updated for 1e5 queries ?

5

@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

6

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

7

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.

8

got it! thanks to both @thecodegame and @iitr_sonu .

9

I have used square root decomposition to solve this problem . It is neither Fenwick tree nor segment tree .

1 Like
10

@vineetpaliwal could you throw some light on the method… or provide some link for same… thanks in advance…

11

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: Topcoder

12

@priyanshuid : This is the link

Read the paragraph which is under this heading :

An O(N), O(sqrt(N))> solution

13

I worked out the mod inverse using GCD and extended euclid.

Then in one answer I saw this:

 for(i=2; i<=100000; i++)  modInverse[i] = (-(moD/i) * modInverse[moD%i])%moD + moD;

Can someone explain it?

2 Likes
14

thank you sir… @vineetpaliwal .Nice tutorial.

15

thanks…

16

BIT (Fenwick tree)

17

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.

18

Actually its O(logn)

19

I just refreshed the page and found out that people have already answered with the same response :stuck_out_tongue:

20

:smiley: @flaminrage … nevertheless thanks.