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.

Outline:

1. State the problem
2. A simple solution which takes O(N^2)
3. Slight modification to above algorithm, still runs in O(N^2)
4. MO's algorithm to above problem and its correctness
5. Proof for complexity of MO's algorithm – O(sqrt(N) * N)
6. Explain where and when we can use above algorithm
7. Problems for practice and sample code

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.

1. Update the first x values.
2. 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...

This is a long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”.

Why a Balanced Binary Tree is good?

A balanced binary tree with N nodes has a height of log N. This gives us the following properties:

• You need to visit at most log N nodes to r...