Need Advice: Range Queries

general
,
1

I want to start learning about Array Range Queries, and more likely Queries involving between Nodes of Trees. So i do some research and find that, i will have to learn the following things to master it.

before Starting : Since its a big list, need some advice on:

–>How to start(which topics first/last/more important/less important)??

–>Also if i want to master the “Queries” problems, do i have to learn more topics??

–>Any Other suggestion on learning “Queries” Problem.??

1.Segment Trees

2.Binary Index Trees

3.Treaps

4.Lazy Propogation

5.Sparse Tables

6.RMQ

7.LCA

8.Mo’s Algo

9.Heavy Light Decomposition

10.Square-Root Decomposition

1 Like
2

I will share my opinion:

MO’s,sqrt decomposition and sparse table are pretty easy.
First learn MO’s algorithm here https://blog.anudeep2011.com/mos-algorithm/ and sqrt decomposition here http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/ and sparse table here https://www.hackerearth.com/practice/notes/sparse-table/

Now learn segment trees and lazy propagation here https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/

No need to learn BIT if you are good at segment tree and lazy propagation.

Now learn LCA here https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

Learn HLD here https://blog.anudeep2011.com/heavy-light-decomposition/

I donno about treaps.

1 Like
3

Thanku Very much for guidance.