How should I start with segment trees? I am a beginner.
here segment trees concept is very well explained and i also learnt from here
For segment tree, first make sure you know concepts of recursion and arrays.
Follow hruday968 's link of hackerearth. I myself learnt from that tutorial, and can say that its pretty decent. Dont worry if lazy propagation doesn’t strike at first, you can come back to it again after doing some basics on segment tree.
That tutorial comes with sample/solved question on finding sum of a given range. Understand the code, working thoroughly. Then, give a hand at the given problem at the end. It should prove easy.
Then, with the concepts learned, remember one golden rule.
Deciding what to store in a node and how to determine relationship b/w parent and child nodes is the key of segment tree. The information you are storing at each node, should be such that on having information of 2 child nodes, you can determine required/asked data, and the information to store in parent node.
Eg, lets say we have nodes 1,2,3. 1 and 2 are child nodes and 3 is their parent. Lets say our query is sum of all elements in a range.
Then of course, we can store sum of respective ranges in child nodes. LEts say 1 and 2 store sum in range [0,3] and [4,8]. Now, since we are storing sums of given range, we can easily answer queries in this range, and for parent range [0,8], we know that sum of all elements in this range = sum of elements in [0,3] +sum of elements in [4,8].
A proper and valid relationship is made here, and this is the concept of segment tree in a summary. Dont worry about other details regarding answering query right now, first check the article and understand the working.
Once you do that, give a hand on Q SPOJ Frequent and SPOJ GSS1 . Do not try to solve them right away. Remember this concept, “The problem of segment trees are really easy if you know what to store, how to relate parent and child nodes, and any special trick (if needed) to extract data to answer query [if they cannot be directly answered]”. With this in mind, check one of the solutions to either of the problem. See what they are doing, question why and see how they related the child and parent nodes. Then, attempt both the Q. Both use similar concepts, and if you are able to do atleast one of them without any help, then treat it as a yourself a nice success.
You can then either choose to further your concepts by attempting previous long Q like PRMQ, Chef and Sub-Array, Stable market, or go ahead with handling updates. I can help you till here, from afterwards, its upto you to decide.
2 Likes
just one more doubt when should one start with segment trees i mean i recently studied about graphs(dfs,bfs,djikstra) and currently struggling with dp(just watched tutorials of standard problems -_- ) so should i start learning segment trees at this moment?
I feel it’s worth reading this tutorial also…kartikkukreja’s blog well written, easy to understand and intuitive
The thing about segment trees is, they are usually bit frustrating to code (all those big function headers with so many variables and blehhh recursion) that we beginners are not really able to focus on idea of applying them.
The best thing IMO is to learn iterative segment trees first (you cannot make persistent segment trees out of these, rest is similar). For that read this http://codeforces.com/blog/entry/18051
Just to show you how simple it is to use these, Here is my implementation of Merge Sort trees :https://www.codechef.com/viewsolution/14060497
The build function is just 1 line! and query is only 4 lines of c++ code!
If you do not understand any of these, please feel free to comment, I will try my best to explain it to you
The real Q to ask is, can you successfully manage learning all of these at once? Segment tree, as in concept, doesnt have dp and graph as pre requisite. But, if you start segment tree, will you be able to manage giving justified time to all 3 topics? If yes, then go ahead, if no, then i will say try to give 1-2 days time reading the tutorial and checking problems. In 3-5 days, (or some hours, depending how much time you give per day), you will be able to handle problems of queries w/o update. Almost good enough for Long contest (1Q usually comes from seg tree). Then continue whatever you wish.
1 Like
i guess i cant learn all these at once better to proceed sequentially thanks:)
1 Like
Segment trees is very well explained here. I too learned it from here.