The Universal Proof And It's Variations

"
"

^^ 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.

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).

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. :)