AlgorithmsThread Episode 3: Segment Trees

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

yeah , true

Thanks, man. That means a lot to me.

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

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;
 
	}

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.

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.

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

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.

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.

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.

SecondThread this will help me too