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





Comments

Post a Comment

Popular posts from this blog

Small-to-Large

-
The Vanilla Method Let's take the given problem: We have some sets as U = {S1,S2,S3....Sn} where U is the "container" set. Initially each set contains a single element. After each operation each set will contain some numbers. We define the cost of a set as the number of unique elements in the set. For each query, we merge two unmerged set and then report the sum of cost of all the sets.  The most brute force approach is for each query, add all numbers in one of the sets and put them in the other set. This will take approximately O(nlogn) time per merge operation and since there can be about O(N) mergings (because after atmost N mergings there will be only 1 set left) this will take time proportional to O(n^2logn) time. For the report, part, we just return the sum of the sizes of the set. This part is O(1) as we only have to check the size of the new merged set as the sizes of the other sets haven't changed. This is obviously a poor algorithm for a seem...
Read more

Segment Tree Beats - An introduction

-
Segment Tree Beats  Disclaimer : This post is based on a recent post made by jiry_2 on codeforces. Before I begin, a clear understanding of segment tree and lazy propagation is required.  If you don't know those, I would recommend you to go search it up online and read it thoroughly, before coming back. With that out of the way, here goes... Hey wait wait wait. Hold on. Just to clarify, now that you have read it, in case you are confused with what I call terminal nodes in a segment tree update/query, it's basically the node that is completely inside the update range, the one where we generally end our search in a segment tree. I say generally.. well.. you will see :). Anyway without further ado...  A simple problem So the first problem I want to address, and it is fairly easy, is supporting two operations on a range: Range minimize (for each i in range, make it min(i, update_value) )  point query Solution : This is just a variant of the n...
Read more

Getting prepared for RMO

-
Regional Mathematics Olympiad The Regional Mathematics Olympiad (RMO) is the second stage in the selection for the selection of the Indian team to the IMO, the first being the pre-RMO. It is one of the tougher olympiads conducted across India, wherein only about 300 students are selected to sit for the Indian National Mathematics Olympiad(INMO). The main thing that makes RMO tough, at least for the common students, is twofolds -- firstly, the syllebus is quite a bit different than the normal class X or XI curriculum that is followed in schools, especially in areas like combinatorics and number theory, the latter being a topic that is scarcely touched upon. Secondly, in topics that are known to us, like geometry, the level of questions, even if they don't require advanced theorems and results, they need a level of creativity that cannot be mastered overnight. From hereon I will say what I did to clear it last year.. when I was studying in class IX. Firstly, I focused heavil...
Read more