Range Minimum Query(O(N),O(1))

catlak_profesor_mfb's blog

By catlak_profesor_mfb, 11 years ago, In English

Enjoy! http://paste.ubuntu.com/9507070/ Tested in: http://mirror.codeforces.com/contest/494/submission/9121141

advanced data structure

catlak_profesor_mfb
11 years ago
21

Comments (21)

Write comment?

Rivx

11 years ago, hide # |

← Rev. 2 →

+18

Now test to see how large the N has to be for it to be faster than segment trees ;p Though I have to admit, I didn't think it could be made so compact.

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

← Rev. 3 →

Well for N=100000 it is definetely faster :D To test it just overload the < operator and there you go. You can use it with everything as long as you overload < operator. The query returns the position of the minimum.

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

And I didnt try to optimize it. I just stopped coding when it worked

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

I think it is faster for N>15000 or something like that. I looked at 282-1-D(birthday) problems test cases

→ Reply

proVIDec

11 years ago, hide # |

+35

ans=min(ans,lookup[sblock[t]&(~(((1<<(l-(r1*lg+lg)))-1)<<(r1*lg+(lg<<1)-l)))]+r1*lg+lg);

That looks really nice :)

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

← Rev. 3 →

I know

→ Reply

CountZero

11 years ago, hide # |

← Rev. 4 →

You split array into $\text{[math]}$ blocks of size $\text{[math]}$ , then build sparse table for each block and for all $\text{[math]}$ blocks. Am I right?

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

Yes you are right

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

But I dont actually build a sparse table like in regular rmq for the small blocks

→ Reply

CountZero

11 years ago, hide # ^ |

then there are $\text{[math]}$ sparse tables, each of size $\text{[math]}$ . Therefore total complexity equals to $\text{[math]}$ .

In order to build O(N) algorithm you have to go further and group blocks by its types, such that blocks with equal types will have equal sparse tables. It is exactly what Farach-Colton and Bender did

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

İt is not O(N) bits memory. İt is O(N) in a 32bit system.

→ Reply

catlak_profesor_mfb

11 years ago, hide # ^ |

As you can see I take 4 vectors, one of them holds the data which is O(N) and N/logN integers in another vector, N integers in another one and 2^(logN) integers which is N in another vector so total memory is O(N)

→ Reply