Hi Team,
I was learning segment trees for two three days,
I am facing a problem in understanding one thing,
Like if we have simple sum query or max query we are returning answer from rangequery function.
But in case of user defined structures with segment trees ,we are merging the branches in rangequery function,but why we are not returning the required answer directly,what is the need of merging different branches in rangequery.
Could you explain your doubt a bit more? I couldn’t understand the question.
1 Like
Like in this code https://cses.fi/paste/66df778b19dd205bf647f
In querySumTree we are simply returning the sum without merging.
But in this code
https://cses.fi/paste/b1f94eda33514b6d10315e/
In range query function we are merging the branches why it is that.
That’s because, the second code you paste for is basically the maximum sub array sum in a given range. So there can be three types of cases like, if the max subarray sum occurs in the left child or max subarray sum occurs in the right child. But there is one more condition where some part of left child (suffix) and some part of right child (prefix) as a whole can return the max subarray sum for the given range. So you are supposed to merge them and check as well.
For more information you can refer this
1 Like
Hey ayushman,
I am not asking that ,we are already dealing with three cases in build tree function so what is the need to again consider these 3 cases in query function also as every node supposed to store the answer already so what is the benefit of merging again.
You mention that you are convinced of the build tree function. Consider what you do in the build tree function: each node takes the answer for its two children, merges it, and therefore finds out the optimal answer for the combined range.
For example, say a node (not a leaf) is responsible for the range (i -> j). It will have two children, left child responsible for range (i -> mid) and the right one holds the answer for (mid+1 -> j). This node now wants to find out the answer for (i -> j) using the two answers of its children. The merge function does exactly this: given two nodes which are responsible for adjacent intervals of the array, it returns the answer for the combined interval.
Now say you make a query for (i -> j+1). There is no single node that is responsible for this exact interval, so you need to take the individual answers for separate nodes which altogether make up the queried interval. In this case, you should be able to get the queried interval using just 2 nodes: the one for (i -> j) that we considered while explaining, and another leaf node (j+1 -> j+1). Note that this might not always be the case, you might need more nodes. Anyways, now you need to do that thing again: given two nodes which are responsible for adjacent intervals of the array, find the answer for the combined interval. That is, combine the answer for (i -> j) and (j+1 -> j+1). Of course, you use the merge function.
It may help to realise that the sum that we return in the querySumTree function is also an implicit merge function. If you would have written the merge function for that tree, it would simply have been a+b, given two nodes with values a and b.
Let me know if anything is not clear.
1 Like
Hey Shiven,
Thanks a lot, i understood the concept now👍🏻
This is my work on the Segment Tree data structure Reddit - Dive into anything
here you can find the implementation Copy and Paste standard library | cpstl
You can check out https://www.codeintuition.io/blog/niBFVvULgdGGRQwSa6SLJ for an in depth knowledge of a segment tree