Segment Tree Beats - The complexity continued.

The Universal Proof And It's Variations

"

When we make a update, only O(logn) can be added to Φ(x) 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.  

"

^^ Read this part from my previous post. It's very important to understand why new tags are only added on ordinary nodes and not on extra nodes. Also just as a reminder, tag means the MAX value and not the lazy tag.

Task 2:

Now we want to have some more features in this task.

• ∨ i∈[L,R] i = min(i,UpdateVal)
• ∨ i∈[L,R] i = max(i,UpdateVal)
• ∨ i∈[L,R] i += updateVal
• range sum

Solution- Official:

So the official solution is to define the potential of a tag as its depth. So since maximum depth is O(logn) and there are initially no more than N tags, Φ(x) is initially O(nlogn).

So let us consider the alterations:

• Remember from my last post how I explained why there wont be tags on the extra nodes that we visit during a interval min/max operation? Well, that means that we only need to consider pushdown() on the ordinary nodes. Each pushdown can add atmost O(logn) (since a new tag *could* be created) and we visit O(logn) ordinary nodes so overall it adds O(log²n) to Φ(x)
• Similarly we add new tags only on ordinary nodes. so again O(logn*logn) can be added to Φ(x).
• during visiting extra nodes, we DO NOT add any new tags. (again, see the last post.) Now, when we traverse down, we delete SOME node in its subtree. Otherwise we wouldnt have gone down in the first place. However that means depth(t) nodes will get subtracted. But notice that we have to traverse depth(t) nodes to delete it.. so overall we delete 1 for each node. 

Hence it is easy to observe that the overall complexity again is O(log²n).

My Variation

So I am changing the potential function only a bit. Instead of considering the depth of the tag as its potential, we define it to be the identity function. What I mean is, if a tag exists, its potential is just 1. That's it. So Φ(x) just counts the number of tags present. Lets see how this affects everything:

• Firstly, during pushdown()s and range update, its just the same as above, just that instead of adding a O(logn) for every node we place a tag in, we just add 1. So the overall addition is O(logn).
• See therefore that the total value of Φ(x) is O(nlogn). Wait. Did we just make the complexity better?
• The change occurs when we are visiting extra nodes too. When we visit a extra node, we do so as we know that some tag will get deleted in the subtree. However, that would only subtract 1 from  Φ(x). But we required to traverse O(logn) nodes to subtract 1. Thus to delete O(nlogn) tags, we still need to visit O(nlog²n) extra nodes. 

Hence complexity is still O(nlog²n).

Task 1 revisited:

Lets look again at task 1 and see how we can prove it using the same potential function.

We make two key observations that ensures that the Φ(x) is of the size O(n), so that when we account for logn nodes for each deletion of tag, overall complexity is still O(nlogn)

• First notice that we only add tags in the extremal "ordinary" terminal nodes in this case. We DO NOT add tags to the intermediate terminal nodes. The reasoning is like such: The intermediate nodes have a uniform change so no new tags actually need to be added. If anything, tags converge. However, the extremal terminating nodes, when we go to their parent, are merged with nodes that are NOT within the update range too. So if their MAX is reduced, its parents (and by induction all its ancestors) will have its MAX either remain the same due to the influence of the other node, or it will have a new tag, in which case the current extremal node WONT have a tag. So in any case, we only add 2 tags on the two extremal terminal nodes. Hence we only add Φ(x) by O(1). Specifically 2.
• During pushdown() , we dont actually do pushdown on logn nodes, because for each of these logn nodes to even have a LAZY value(here i am kindof mixing the lazy tag and my description of tags as MAX value, because lazy tags will be how you implement them actually), there needs to be atleast logn updates, which in effect means O(1) pushdown for each update.

So these ensure that Φ(x) is O(n) overall. Hence the O(nlogn) complexity.

NOTE:  This does NOT apply to the Task 2 that we considered because of the presence of both min and max operations. In such a case, we would have to maintain separate "classes" of tags for a MAX and a MIN. So when we do a min operation, it can cause changes in the other tag "class". This is why in that case, update is actually O(logn). (I will exemplify this on a later update maybe :) ).

Thus we can use the same potential function to essentially prove both the tasks. Hope this helps. :)