Hi, let's get straight to the topic.

MO whithout Update

==================

Problem : given an array a of size n. you are given q queries and in each queries you are given two intigers l and r ($$${l \le r}$$$) and you are supposed to print the sum of $$${a_l}, {a_{l + 1}}, ..., {a_r}$$$.
Very easy huh?
First, let's solve it with time complexity $$$O(q * n)$$$. why?.
It's gonna help you to understand Mo's algorithm better.
suppose we have a start pointer and an end pointer on the array and a value cur such that cur is equal to the sum of segment $$$[start, end]$$$, now we for each query, we are going to reach r with end and reach l with start and change cur such that after reaching both start and end to l and r, cur will be equal to the sum of segment $$$[l, r]$$$.

suppose $$$end < r$$$ : we can change end to end + 1 and update cur, just add $$$a_{end + 1}$$$ to cur.

We can use the same method to decrease end and change start and now we have an algorithm of complexity $$$O(n * q)$$$. what if for each query we know that given r will be bigger or equal than the r given before. total complexity will still be $$$O(n * q)$$$ but total changes of end will be $$$O(n)$$$ and that's good. even if queries didn't give us r in increasing order we could always sort queries base on their r.

now for decreasing the total changes of start what can we do?
let's decompose a to blocks of size S. what if we sort the queries such that for queries in each block have increasing r (You can see HERE for exact sorting method). let's calculate time complexity.

For the i-th block suppose we change end at most $$$O(n)$$$ times, so total changes of end will be $$$O((n / S) * n)$$$.
Suppose we have $$$q_i$$$ queries that have l in the i-th block.
For the i-th block, we change start at most $$$O(q_i * S)$$$. so total changes of start will be $$$O(S * q)$$$.
We do $$$O((n / S) * n + S * q)$$$. with $$$S = n / \sqrt q$$$ we get $$$O(n * \sqrt q)$$$ and that's really good. now you can apply the method described here with problems that are much harder and good luck.

I suggest before reading Mo with update, you solve some of the problems below.

Powerful array
XOR and Favorite Number
Ann and Books
Little Elephant and Array
Chef and Problems

MO with update

==================

Problem : The same problem before with diffrence that we have change query. You are given pos and $$$val$$$ and that means you have to change $$$a_{pos}$$$ to $$$val$$$.

What will happen if we use the same method that we used above? We get time complexity $$$O(q * n * \sqrt(q))$$$ because before each query we have to do some updates or undo some updates.
That's not good enough. Here is the main idea for what we will do:

Decompose array into blocks of size S.(pretty similar to the last one huh?) and sort queries that ask for some sum, firstly based on the block which l lies in and secondly by the block that r lies in and finally by t. t is the number of the update queries before this query.

now let's calculate the time complexity :

total changes of the start: for the i-th block that l lies in it, the start will change $$$O(q_i * S)$$$ ($$$q_i$$$ have the same definition as before). So total changes of the start will be $$$O(S * q)$$$.
total changes of the end: for the i-th that l lies in it, and for the j-th block that r lies in it, the end changes will be $$$O(q'_{i, j} * S)$$$. ($$$q'_{i, j}$$$ is number of queries that l of them lies in block i and r of them lies in block j). So the total change of the end for a fixed block for l is $$$O(S * q)$$$.
Changes of the end when changing between blocks of l is $$$O(n)$$$ and therefore we get total changes between blocks of the end is $$$O({n ^ 2} / S)$$$. So the total change will be $$$O(S * q + {n ^ 2} / S)$$$.
total updates we have to do and we have undo: because for the i-th block of l and the j-th block of r, t is in increasing order the total changes of t for these two fixed blocks is

Unable to parse markup [type=CF_MATHJAX]

TOTAL COMPLEXITY: from above we get total complexity of $$$O(S * q + S * q + {n ^ 2} / S + q * {n ^ 2} / {S ^ 2})$$$ and that is equivalent to $$$O(S * q + q * {n ^ 2} / {S ^ 2})$$$, If $$$S = {n ^ {2 / 3}}$$$ we get $$$O(q * n ^ {2 / 3})$$$.

FACT : with S = $$$(2 * n ^ 2) ^ {1 / 3}$$$ you will get best complexity.

Here is some problems (Sorry I didn't find many :) ) :
Primitive Queries
Machine Learning (rip)
Candy Park
Any suggestion or problem, please comment :D.