Segment Tree Beats - The complexity

The Complexity Proof

Where we left off..

In the last post I described the basic idea of a segment tree beats

• In each node maintain a MAX value and a SECOND_MAX value
• Terminate your search only when update value is more than the SECOND_MAX value

However, the main problem was that there, we were visiting potentially lots of extra nodes. 

In this post I will attempt to explain the time complexity proof of why, even though it seems we are doing a lot of extra work, we actually are not.

Some Basic Concepts

First off, just forget about the lazy tags. Only remember that when we make a lazy update, we call a method pushdown(). It propagates the lazy tag. Thats it. Now forget about the lazy tags. Good.

Let me redefine tag as the maximal value of the node that is not the same as that of it's parent.

What I mean by this is that the MAX value of a node is now what we call a "tag". And we stick with this definition throughout the rest of this post. NOT LAZY TAGS.

Now to be a bit clear, the following two points are important:

• The MAX value is the tag. 
• If a node has the same MAX value as that of it's parent, then the node does not have a tag. Otherwise it does.
• The SECOND_MAX is , as a result, maximum tag present inside the subtree. (think why ).

The **SECOND** point is actually very important. Keep it in mind.

UPDATE: Basically for a node to have a tag, it is not that it needs a lazy value. Tags here have no connection with lazy tags here.. atleast in the proof. (Ofcourse the implementation part is different. There lazy tags are actually what is used to propagate these MAX value "tag"s. But for now, forget about them. ) What it means for a node to have a tag K is that its MAX = K and that its parent's MAX >K. If they are equal, the child is not deemed to have a tag.

Now lets define Φ(x): It basically stores the sum of potential of all tags.
UPDATE:  What I mean as the potential of a tag is some function on that tag. For example, it could be the depth function where potential of a tag means the depth of the node the tag is in. Or it could be a identity function which means if a tag exists, its potential is 1, otherwise 0. In this case the  Φ(x)  is calculating the count of tags.
 We manipulate this Φ(x) to achieve our proof by showing that the amount of values that u add to it is the maximum value that you can subtract from it as its value shall always be non negative. So total addition and time taken to remove a value will give us an estimate of how much work we are doing. Read on for a clearer understanding.

UPDATE : In this segment tree, we will be talking about two types of nodes. Ordinary nodes and extra nodes. Ordinary nodes are those that we would have visited when we would have traversed the segment tree with the normal tag conditions. Just think of them as the nodes u visit in the normal version of the segment tree. Extra nodes are those that we are visiting because of the stronger tagcondition. These are of more interest as we want to get a bound on the number of extra nodes that we visit in order to prove the time complexity. (In some places ordinary nodes mean the terminating ordinary node -- where we would have ended the search in case of normal segment tree, but whose children we might visit in this case due to the stronger tag condition.(these children are extra nodes by the way). However I hope the distinction will be clear when I am assuming terminal ordinary node or just ordinary node. Most of the time it is the former.)

The Original Proofs

So here we will consider two problems. The solutions are the ones discussed in the actual blog, but hopefully simpler to understand.

Task 1 :

This is the task we discussed in the earlier post. The operations we want to support are the following

• for i∈[L,R] Arr[i] = min(x, arr[i])
• range sum

Now consider the "potential" of a node (in this case we are not considering the potential of a tag) as the number of unique tags under its subtree.(NOTE : the word **UNIQUE** : It means that when we do a update, if several nodes under its subtree gets the same tag as a result of the update, we count it as one). Observe that initially we only have N tags in total in the segment tree. Why ? Well, a node cannot have the same tag as that of its parent, and there can be atmost N distinct values, so atmost N tags. Each tag will be under its parents.. so it will contribute logn to Φ(x), because it can have atmost logn parents.

So the inital value of Φ(x) is O(nlogn) (n tags * logn contribution per tag). If this is not clear, reread the rule 2 and the above para thoroughly. 

Just a reminder :  tags here does not mean lazy tags. They are the MAX values of the node that are unique from its parent's.

So let's observe the changes that happen to it:

• When we make a update, only O(logn) can be added to the potential functions. This is because we can add tags only to the ordinary nodes, which are O(logn) in number, and each gets added by 1 ONLY, because of the **UNIQUE** clause that I had mentioned earlier. Think about it... if it werent unique, then potentially O(log^2n) tags could be added as each tag would have contributed to its logn parents and there can be logn terminal nodes in general. Now something interesting should be noted here: we are saying that we place tags in only O(logn) nodes, that is, only on the ordinary nodes: what about the extra ones we visit? Turns out, we dont place tags on them. Think about it... the extra nodes are those that are completely inside the range...and a depth lower than the optimal position. What I mean by this is, even when we move to its parents, its still in the range and so it does not have to combine with any value that was outside of the range. The major effect of this is that all changes made to it are affected throughout. Everything is basically changed in a uniform manner. And due to Rule 2, new tags wont be added. The reasoning is kind of like, we add new tags on nodes that are on the boundary of the update range. This is because when we move to its parent, its value combines with the values of nodes that are outside the update range and hence unchanged. So for example, if the value of this node reduces due to a update, a potentially new tag could be created.Consider this scenario, when it had the same MAX as its parent, it had no tag. Now due to the update, its MAX may get reduced while that of the parent might not as it may be getting its MAX from its other child, which was outside of the update range. So this node gets a new tag. However this can never happen on an extra node because if its MAX is reduced, since even its parent lies completely in the range, its parent's MAX too will get reduced to the same value, so in effect it would have no new MAX and hence no new tags.                                                                                       
• The second thing that could happen is a pushdown() , but that would only increase Φ(x) by 2.
• Now we consider what happens when we visit a extra node. We visit an extra node in the first place because we had got that SECOND_MAX > updateValue. So somewhere down the line, we have to delete a MAX value. (Remember that SECOND_MAX also has to be a MAX of some node in that subtree?) Also note that when we delete that MAX value, we are not really adding a new tag because.. well... read the first point!. Also note that if we delete that MAX value, all other MAX values that were the same as this is going to be deleted. This means that there will a reduction of 1 for EACH extra node that we visit when going down. This is because a whole UNIQUE MAX value was lost. So every node that had it in its subtree must subtract 1 from Φ(x). 

Thus, Φ(x) can only be O(nlogn) at most since we never add more than O(logn) per update and it had O(nlogn) to start with. Moreover, each extra node we visit subtracts 1 from it. so we can visit at most O(nlogn) extra nodes overall. Hence total complexity is O(nlogn). 

In the next post I will talk about a slightly harder task. And I will also be proving this task using a general proof technique that can be universally applied.