By SecondThread, history, 7 weeks 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!

• +247

 » 7 weeks ago, # |   +3 Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
•  » » 7 weeks ago, # ^ |   0 Can you make tutorial on merge sort trees???.... With online queries....
•  » » » 7 weeks ago, # ^ |   0 I don't think they are useful.
 » 7 weeks ago, # |   +118 I will just say that your recent content has great quality.
•  » » 7 weeks ago, # ^ |   +24 yeah , true
•  » » 7 weeks ago, # ^ |   +52 Thanks, man. That means a lot to me.
 » 7 weeks ago, # |   +14 Your videos are great..!
 » 7 weeks ago, # |   +2 What are next two topics?
•  » » 7 weeks ago, # ^ |   +53 The plan is for them to be on segtree beats and then persistent segtrees
•  » » » 7 weeks ago, # ^ |   +13 had hard time understanding seg tree beats, looking forward to it :)
 » 7 weeks ago, # |   +13 Another amazing video.
 » 6 weeks ago, # |   +10 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.
 » 4 weeks ago, # |   0 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..
•  » » 4 weeks ago, # ^ |   +3 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.
•  » » » 12 days ago, # ^ |   +15 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).
 » 2 weeks ago, # |   +10 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?
•  » » 2 weeks ago, # ^ |   +3 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.
•  » » » 2 weeks ago, # ^ |   0 Thanks I will see them.
•  » » 2 weeks ago, # ^ |   0 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
 » 2 weeks ago, # |   +19 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.
•  » » 2 weeks ago, # ^ |   0 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
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 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)).
•  » » » » 2 weeks ago, # ^ |   0 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.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 5 →   0 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] = 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[0] 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).
•  » » » » » » 2 weeks ago, # ^ |   0 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
•  » » 2 weeks ago, # ^ |   +8 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.
 » 2 weeks ago, # |   +112 David: records a video about segment treesantOn trygub: declines every problem about segment treeDavid: pikachu face
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
 » 2 weeks ago, # |   0 Also, I think some problems from "can you answer the queries" series on SPOJ are also a good practice to segment trees.
 » 12 days ago, # |   +10 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..