They said, let's see the source code, right?
Let's see what I have done here.
So as you can see, it's accepted.
Everything's fine.
Let's get into it.
So as we have talked about, I am going to need a segment three, which is going to tell me what is
the cave element?
What is the cave failure?
Right.
Because that segment was on values.
So let's see how the secondary is implemented for this kind of problem.
Right.
So, of course, first of all, I'm just reading and and K and the Q sorry.
And for each and every of the elements, I just read the element X.
And in order to initialize the segment we remember.
I can do one of the two things.
I can either build it.
We have a special recursive function build or I can just perform an updates.
Right.
Read the element update on that position, the element.
Read the element of it in the position.
The element.
This is what here.
Right.
So if opposition I, I read the value X, right.
I don't care about the position of words.
I care about the value which is X.
So I will update on position X.
This is the position.
And this is the value.
Right.
That I think I'm going to increase it by.
Yeah.
All right.
So basically I'm going to increase the value X by one.
Right.
That makes sense.
Then of course, if this is positive, I do that.
If this is negative, which.
Which means that I have to get it out of basically of the set.
What I do is that you can see here that I applied the query one one.
And then minus X. We are going to see what these free parameters are.
And minus X means that, of course, if this is negative, let's say it's minus five, minus X is five.
So I am basically finding B..
What, these the fifth smallest value.
This is what might be does.
Right.
And because I will subtracted.
I first find it.
So I apply query of one one and minus X.
And after finding it I will update this value P by minus one.
Right.
So I found a value.
Now I subtract its counter.
I subtract how many times it appears in disarray by one.
Right.
That makes sense.
So after performing this, after initializing the array and performing all these queries, either updates
increase by one or queries find the value and decrease by one.
And we're just going to check if this is aimed.
This is my my.
Array in Romania, we called it.
I include the same three or something like that.
So just remember, it is the array that represents the segment tree.
So if your eight of one equals zero, which means that there are zero total values in the array.
Right.
So let's remember.
End of node in that node we remember how many elements have a value between our word range, that node
specific range.
Right.
So if this is zero, this means that the number of elements we have, no matter what is the value,
the number of elements in the array zero.
So we have no element in the array.
So of course, you have to see all zero.
If not, that means there exists some elements so we can find the smallest element.
And how would we find the smallest element?
Of course, by performing the query in the whole array.
And we need the first smallest value, which is, of course, as one as value.
So all you need to do here is that we need to understand perfectly how the update and query recursive
function works.
And if we understand that that everything is fine.
The problem is already solved.
Right.
So let's say.
Hold on.
Let's see what this do.
Right.
So as you've noticed here, for example, when I wanted to to insert a value X, I will update on one
and one, an X and one.
Right.
So this is the mode from this segment, Terrene.
This is the range specific to that note.
This is the position in this segment three, which I have to update.
And this is the value by by which I really increase the value in that position.
Right.
So let's take a look here.
So I have not I have its range, which is left.
Right.
In Romania, we call it standard, wrapped ourselves as the NDR.
But let's just call it left.
Right here.
So node left, right.
B and Val.
And what do I do?
As you know, the signatories are a cultural thing.
It starts from the root, which was not one.
That's where I had one one n right node one with the range of one N.
And it goes all the way to finding the specific leaf from the segment tree, which corresponds to the
position key.
And when it reaches that leaf, be it increases the value by Val.
And that's basically it.
Everything's fine.
So what I do here is that once left equal is right.
This means that I am done searching and I have found the leaf.
So now I have to do is that increase the value in that node.
By that end, we return the function.
It's over.
We can continue and do the other updates.
Right.
So this is basically the base case where we start the discussion, if left equals right, then if not.
We have basically the range left, the right, and we have to split it in half.
Right, the left, the middle half and the middle plus one, right.
Half right.
Because this is what happens in a segment we are not has two children and each children means the left
half of the subarea and the right half of that subgroup.
Right.
So I come to this middle, which is left plus right, divided by two.
And now I have left middle middle class on the right.
My two children with their specific ranges.
And I just check with respect if B is going to be in the left son or in the left range.
So if be less or equal than meat, then I go and update.
I basically move into the left son, which is to cross node because there's the notation right in the
array which corresponds to the range or left middle.
And I try to find position B..
And of course, increase the value on that position by that.
So there arguments limits, of course.
The other scenario is that B is greater than me.
Which means we are going to update starting from the right son.
So we should go in the right side, which is to cross node plus one, which corresponds to the range
middle plus one.
Right.
Find the value P, find the position B and increase its value by.
Of course.
Very, very important.
When you are in the node, no matter in what son, you have gone to update the values either the left
on or the right one.
In the end, when the recovery is over, you are going to return on the recursion tree.
Again, on that call.
And you are.
And when you are here.
So when you finish either this call or that call.
You have to be very careful because the value in one of the signers, either the left on the right on,
has changed.
So the value in the father would also change.
Right.
The father is always the sum between the left son, the left son and the right son.
So if either of these changed, you have to change the sum in the father.
Right.
So just update again.
Segment tree node is equal to the single tree into grassland pricing, wanting to press on CROSSFIRE.
And that's it, right?
No matter what, the son was updated.
You know that.
Now the sum is updated.
And after you do that, you will basically finish this recursion call and return to the father and update
that father and so on and so forth until we hit the road.
Now we just have to find about the query function.
Call it super simple to understand that you just have node left.
Right.
And Kay.
So the exact same thing.
But this time you are searching in the range left.
Right.
Which corresponds to this node.
You are searching the Kafe smallest number.
Right.
So you are basically searching the first node.
The first leaf which basically the leaf which corresponds split keeps smallest number.
Right.
So that's it.
This is super simple.
We have explained it in the previous video.
Basically again, when we hit left equals right.
This scenario means that we hit that leaf.
So we have found the leaf that corresponds to the smallest value.
Everything's fine.
Return that position, which is left or right.
No matter what, they are equal.
And yep, that's it.
We've got a solution.
Everything's fine.
So this is the base case.
Right.
And we are guaranteed, by the way, we will implement this function that when we hit this base case,
we have found the cave smallest number.
Of course, if it exists.
But the problem already assures us that the that very is going to exist.
Right.
So middle is left prostrate, divided by two.
Again, we split the range in two left son and right son.
And we just have to see in the left side.
Right.
So this is the left side.
This is the the right side.
I am looking for the Kafe smallest number.
I just have to look in the left, son.
I have at least key numbers.
This means that because the left some stores in itself, the smallest numbers right.
So left son has smaller values than right son.
So if left son has at least Quaye values, this means that what I'm looking for is here.
So I just return query of the left son, which is to cross node, which corresponds to the range.
Left middle.
And we are looking of course, for Valiquette.
If not.
And the left son has a number of values which is less than key.
Let's say keys stem.
And this lets son has five values.
This means that of course, the term value, the ten smallest value is in the right son.
But because this has five values.
If I get rid of it, that DMF smallest value now is actually the fifth smallest value from the right
side, right?
So I just have to query on the right side, which is to cross node plus one on middle plus one.
And right.
And now I'm looking for K minus the sum in the left sun.
Smallest number.
And this is fine.
This is epic.
And this is how we solve it.
Right.
Update and query both of them.
Bigo of log of M and building the segment threes.
And again, perform the queries is M logjam.
And then you just perform one more query and that's it guys.
It's accepted and it should be pretty clear right now.
I see.
On the next one.