Once again I found a topic that is useful, interesting but has very less resources online. Before writing this I did a small survey and surprised that most competitive programmers do not know this algorithm. Its important to learn this, all the red programmers on Codeforces use this effectively in Div 1 C and D problems. There were not any problems on this topic an year and half back, but after that there was a spike! We can expect more problems on this in future contests.
State the problem
A simple solution which takes O(N^2)
Slight modification to above algorithm, still runs in O(N^2)
MO's algorithm to above problem and its correctness
Proof for complexity of MO's algorithm – O(sqrt(N) * N)
Persistent segment trees: Explained with SPOJ problems
In this post I will introduce the concept of persistent data structures. We shall deal with a couple of problems: COT, MKTHNUM
Consider the following question:
Given a linked list, you need to support 2 operations.
Update the first x values.
Print the linked list after k’th update (k <= number of update operations made till now)
Simple solution is to create a new linked list after each update operation. print it when needed. Let us optimize it for memory.
We are only updating first x elements of the linked list. That means the new linked list will be almost same as previous linked list if x is small. We shall take advantage of this and avoid allocating memory for some elements. We can allocate memory for x elements, store new values in them, then point the next pointer of x’th node...