### Fype's blog

By Fype, 3 years ago,

Hi, let's get straight to the topic.

#### ==================

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.

#### ==================

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.

• +120

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +5 Also MO with updatehttps://codeforces.com/problemset/problem/940/F?locale=ru
 » 3 years ago, # |   0 is this a typo? ‘ we change start at most O(qi*S) ‘ what do you mean with qi*S? thanks!
•  » » 3 years ago, # ^ |   +4 For each query that their l lies in that block we change the start $O(S)$ times