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 $$$O(q * {n ^ 2} / {S ^ 2})$$$.

**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.

Also MO with update

https://mirror.codeforces.com/problemset/problem/940/F?locale=ru

is this a typo? ‘ we change start at most O(qi*S) ‘ what do you mean with qi*S? thanks!

For each query that their l lies in that block we change the start $$$O(S)$$$ times