SecondThread's blog

By SecondThread, history, 4 years ago, In English

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!

Update: Problem Links

  • Vote: I like it
  • +247
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you make tutorial on merge sort trees???.... With online queries....

»
4 years ago, # |
  Vote: I like it +118 Vote: I do not like it

I will just say that your recent content has great quality.

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Your videos are great..!

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What are next two topics?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    The plan is for them to be on segtree beats and then persistent segtrees

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      had hard time understanding seg tree beats, looking forward to it :)

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Another amazing video.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<leftmost or left> 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;
     
    	}
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank you for taking the effort in answering.Now I get it,I overlooked the sum that is being calculated while calling updatelazy().

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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).

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<n-1;i++){
        for(int j=i+1;j<=Math.min(i+m,n-1);j++){
            dp[j]=Math.min(dp[j],dp[i]+c[i]);
        }
    }
    // dp[i]=min cost to reach city i
    

    It's correct but will give TLE. So I thought If I can replace my inner for loop which is basically update in a range like $$$arr[i]=min(arr[i],x)$$$ with something in $$$O(logN)$$$ complexity then it will pass. That's the reason I asked this doubt.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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)).

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 5   Vote: I like it 0 Vote: I do not like it

          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).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +112 Vote: I do not like it

David: records a video about segment trees
antOn trygub: declines every problem about segment tree
David: pikachu face

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, I think some problems from "can you answer the queries" series on SPOJ are also a good practice to segment trees.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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..

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good question! I don't believe this is something you can easily do with a BIT (there is something called a "super-BIT" that can handle this, but it isn't really that helpful imo). A BIT can either do point update/range query, or range update/point query, not both. However, if you are comfortable using a segtree, then you can handle it with lazy propagation quite well. The idea is to have separate queries for range updates and range sums. The segment tree actually does range updates on the array (rather than point updates on the prefix sum array like the BIT does).

    So your node would need to have a lazyProp value that stores the amount that is added to every node in its range. Then, when you are at a node in the segment tree, first you need to push that lazy value down to your children and recalculate your own sum. Then, you can either return your sum, return 0, or ask both your children, depending on what the query range is.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thank you, i will focus more on segment tree i guess.

      Also saying that BIT can either do point update/ range query or update/ point query was really helpful to me :)

      So thanks :).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you give us code for lazy propagation please? I love to see coding part even if you think it is boring. It is quite helpful for newbies as me to understand and follow what you actually think