00:01
Hi, in part a to delete a horizontal line segment with endpoints that is range in 0 to k from a segment tree we need to traverse the tree and remove all the nodes that corresponding to the segment.
00:18
Remove nodes that correspond to the segments.
00:23
This can be done by recursively traversing the tree and checking if each node range overlap with the segment.
00:38
If it does, we remove all the nodes and continue to traverse around the children.
00:50
The time complexity of this operation is 0 log to the base k because we need to traverse the tree from root to leaf nodes and the height of the tree is log k b.
01:08
To prove n does not contain tree nodes that are at the same level we use the contradiction.
01:13
Let us assume there exist these nodes a b and c in n that there are same level without loss of generality.
01:35
Let's assume that a is leftmost node b is middle node and c is rightmost node.
01:58
Since a b c are at the same level they must have the same parent node p.
02:03
Now let us consider the ranges of a b c...