Coding Start Up!

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 maj

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 LA

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 normal lazy