COLLECT alternative

general
, ,
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.

21

My bad. Put the n in there by mistake.

22

please provide any link to learn this new method

23

Pls provide a good link !!

24

Square root decomposition can be thought of as follows. Arrange your numbers in a (square) grid. So thats a ceil(rootN) x ceil(rootN) grid. Now fill in the numbers in row major order, and maintain rowsums. When you need to find sum of range (i…j), divide the range into : i’s row, j’s row, and all rows inbetween. You can find the sum now in time O(length of i’s row) + O(number of rows between i and j) + O(length of j’s row). If your grid is of the rootN x rootN type, all these three will be O(rootN). Thus, such solutions use time complexity O(rootN) per query.

4 Likes
25

This is new, and fascinating!! Lets get everything (LHS and RHS) “modulo moD” and try to understand it.

The above is basically saying something like, if you write “moD = i * q + r”, then take modulo moD, you get something like 0 = i * q + r => 1/i = -q * 1/r (modulo moD). Since r < i, we would have already computing “1/r” earlier.

Wow, this is amazing - thanks for pointing out!

2 Likes