Why do most of the codes involving Finding range minimum query without update use segment tree rather than Sparse table , which is easy to write and even a lot faster in finding RMQ
Sparse table cannot handle updates, if you change any value of the array then the entire table has to be computed again. Also if you have a well written general purpose segment tree template then it’s provides more flexibility and it remains just a matter of copy pasting a bunch of code with some subtle changes.
1 Like
It’s just your preference. Sometimes you might have a segment tree template available and it’s easier for you to use that. Segment Tree queries are logN. In some cases when you have to binary search and constantly query for the minimum, using a segment tree will give you a complexity of log2^N. A sparse table can be used to achieve logN here.
1 Like
Guys, I am a complete newbie here. Not getting a thing.
If you feel so please take get some time to answer my questions 
To start with , right now I only know about HTML and CSS that I use for WebDev. for Codechef however I have realised that I need to learn C / C++ / Python.
- What should be the correct sequence to learn the things (programming languages, DS-Algo etc) in order to be able solve the problems here & get rated good in future ?
- Does solving practice problems & getting them wrong display a bad picture of my profile ?
- Does solving the rated questions incorrectly deduct points ?
- How much & what should I practice till I become capable to enter rated contests ?
Whatever language you suggest me, please also tell majority of the topics that I need to cover to be confident to solve questions.
YES , I am a newbie here & you guys might make fun of me for that but I don’t want to be one forever. Also whatever I learn I want to learn it completely & perfectly with no doubts in head. Neither do i want to cheat. So in the end,
- Please suggest me Proper sources to learn whatever you have suggested. whether it is books, Youtube Videos or Website.
how you have learned dynamic programming plz tell
how you have learned dynamic programming plz tell
i have recently started to learn algo after seeing ‘wipl’ problem solution of january long challenge uderstanding that if i want to be good at contest it is necessry to learn diff algos
so plzz i will be grateful if you will share your expereince and thought on your journey to learn dsa
You can query in O(1) for RMQ in sparse table
Assuming you’re just starting off with dp I will suggest you solve these first (if you haven’t already ofc)
These resources cover most of the standard techniques that are used in solving dp problems. After that, solve 1200-1800 rated codeforces problems sorted by dp tag : Codeforces 1200-1800 DP Problems
That’s what I’ve done for learning dp. Though tbh, I don’t know very much about dsa so maybe you should also try asking for opinions of people who are proficient in it.
2 Likes
thank you so much for replying
1 Like