By SecondThread, history, 23 months ago, # AlgorithmsThread Episode 3: Segment Trees

Hi everyone, I just made Episode 3 of AlgorithmsThread. This one is a bit easier than usual and covers Segment Trees. At the end of the video, I talk about an interesting and difficult Segment Tree problem called Sneetches, that might be worth reviewing if you already know your segment trees quite well.

This video is a bit easier because the next two will be about some hard segment tree topics, and this should help prevent people who don't know segment trees yet from getting completely lost.

If you have any questions on stuff I covered, the comments below is a great place for them!  Comments (39)
 » Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
•  » » Can you make tutorial on merge sort trees???.... With online queries....
•  » » » I don't think they are useful.
 » I will just say that your recent content has great quality.
•  » » yeah , true
•  » » Thanks, man. That means a lot to me.
•  » » » I just hope you didn't blushed a lot...
 » What are next two topics?
•  » » The plan is for them to be on segtree beats and then persistent segtrees
•  » » » had hard time understanding seg tree beats, looking forward to it :)
 » Another amazing video.
 » Thanks a lot for such great content. Learned a lot from this video. Here's a C++ version of the SegTree class alongwith lazy propagation.
•  » » Correct me if I'm wrong. I think while doing range update if the interval covers it, u can just write lazy = val and update the sum, as you have already called updatelazy() at the beginning. I think the commented part is redundant. void rangeUpdate(int left, int right, int val) { updateLazy(); if(right rightmost) return; if(right>=rightmost and leftmost>=left){ sum+= val*(rightmost-leftmost+1); /*if(!leaf()) { lchild->lazy+= val; rchild->lazy+= val; }*/ //instead lazy +=val; return; } lchild->rangeUpdate(left, right, val); rchild->rangeUpdate(left, right, val); recalc(); return; } 
•  » » » This is incorrect. The updatelazy function updates the node in the segtree so as to correct its value when the node is required. You have increased the lazy value of the node in consideration. However, this node has already updated its sum: sum+=val*(rightmost-leftmost) . We don't need to update its value at a later instance. So lazy+=val should not be here.However we do want to update the children of this node and hence the child nodes should be the ones that require an increment in their lazy values.
•  » » » » Thank you for taking the effort in answering.Now I get it,I overlooked the sum that is being calculated while calling updatelazy().
 » why do we take array size 4*N in segment tree. i know little bit math behind that but it's still confusing for me..
•  » » I believe the logic is the following: If n is a power of 2, it takes 2*n-1 nodes to represent it.If n is less than a power of 2, there is a power of 2 less than 2*n.So we will need at most 2*(2*n-1) nodes, which is just less than 4*n nodes for a segment tree of size n.Of course, you can also write it object based and not worry about it at all like I do.
•  » » » Not actually. Any segment tree on $N$ elements will always have $2N-1$ nodes. But their indexes are not necessarily in range $[0,2N)$, if we are marking left and right child of node $u$ as $2u$ and $2u+1$. If we mark nodes by their dfs order, then we will always need exactly $2N - 1$ nodes as well as indexes. One way to do this is my marking left node of $u$ as $u+1$, and right node of $u$ as $u + 2 \times \text{# elements in left subtree}$ (as left subtree will take $2 \times \text{#elements} - 1$ indexes).
 » Can anyone please help me. I have this one doubt I want to update elements between arr[l....r] with are[i]=min(arr[i],x). Can I do this in O(login) time using Segment Tree? Anyone please? How can I do this?
•  » » Hi, yes you can do this using segment tree beats actually. The next AlgorithmsThread video is on how to do that. You'll get log(n) time amortized, but I think that is pretty much what you are looking for.
•  » » » Thanks I will see them.
•  » » Actually, you don't need segment tree beats for that if you want for example only to query the value of arr[i]. You can just do lazy propagation for that: you can use the non-leaf nodes of your segment tree as tree[node] = minimum value that updated the current interval. When you query for the value of arr[i] you go up in the segment tree and keep the answer as ans = min(ans, tree[node]) until you reach the root. https://pastebin.com/JQDyRiRc
 » Hi, can you attach the links of the problems discussed in the video in the cf blog ? I want to try them before watching the video.
•  » » Actually I was not solving the problem discussed in the blog but was doing the recentProblem D1 of Facebook Hacker Cup. My solution was brute force $O(N*M)$ complexity Like below. for(int i=0;i
•  » » » 22 months ago, # ^ | ← Rev. 3 →   You don't need a Segment Tree for this, you can get a greedy O(N) solution. However, if you want to speed up your dp transition, you don't need Segment Tree Beats. You can simply query for the min in the range(l, r) and update the current value with min + cost[u]. This will take roughly O(N.log(N)).
•  » » » » What is the point of taking minimum in range if we are not updating value in the range because it might possible that some current value will be least even if we go far from (more than M distance) but clearly after we visit M city the cost must increase. So I think this method will give wrong answer we need to update in range. Or please clarify if I misunderstood it.
•  » » » » » 22 months ago, # ^ | ← Rev. 5 →   Ok think of the transition this way: Initially, we are at city 0. Here, our fuel tank is already full. We don't need to buy fuel here. Buying fuel at city 0 is not optimal. So the minimum cost to reach city 0 is 0. Hence, dp = 0. Now as we have a full tank, we are able to reach m more cities. The total minimum cost of refuelling at any of those next m cities will be cost[i] + dp because we can go to the next m cities from city 0 and the cost of fuel at city 0 is minimum i.e. it is 0. So now that we have our base cases, let's rewrite your transition: for (int i = m + 1; i <= n; i++) { dp[i] = INF; for (int j = i - m; j <= i; j++) { dp[i] = min(dp[i], dp[j] + cost[i]); } }  Here, i represents the city we are at. j represents a city where we could have come from. We already have the minimum total costs to reach cities j. As we could only come from one of them, we can simply update the minimum total cost of reaching city i and refuelling to be the minimum in the range(i-m, i) + cost[i]. Our initial complexity is O(N*M). We can optimise this. Instead of constantly checking through each of those j cities, we can use a segment tree and get the minimum for the range(i-m, m). We update the current value of dp[i] to the minimum in the range + cost[i]. We also modify this position in our segment tree with the value at dp[i]. We can easily query our dp array for minimums this way. Complexity achieved is roughly O(N.log(N)). I used an iterative Segment Tree to perform this optimisation because we only had point updates. Here is the link to my contest submission which got accepted: D1 with a Segment Tree I think one of dp problems in the starting of the AtCoder dp contest contains a transition just like here (Segment Tree isn't required there). You could take a look at that problem. Also, there is a problem — candymountain_ex on dunjudge which has a similar transition (we have to optimise n^2 dp to nlogn with a Segment Tree).
•  » » » » » » Thanks got it. Btw I just did it using Priority Queue. Since the cost will be monotonic function(non-decreasing) I used priority queue. D1 Min Heap
•  » » Hi, good idea. I added the problem statement of the harder ST problem, as well as another problem that uses a similar idea that was published shortly after my video came out.
 » David: records a video about segment treesantOn trygub: declines every problem about segment treeDavid: pikachu face
 » Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
 » Also, I think some problems from "can you answer the queries" series on SPOJ are also a good practice to segment trees.
 » Actually thanks to your suggestion which is also here i understood how i can range update in Fenwick tree using partial sum.I was trying to solve this problem and i know that i can solve it using lazy propagation and i don't even need to use DS but it's just for practice.BUT my problem is that i want to get the prefix sum as well after the range update and i don't know how to do that.In other words update a range in log n and i can do that but now i also would like to get the prefix sum after the update in log n.Is this possible?And for example :if we got an array with 2 elements [0, 0] then we used range update with value 20 then it will be [20, 20] but i want it to be [20, 40]...If anyone can help will be much appreciated..