JUst Posting it for revision purpose.
First solution, n adds and 1 mod First, let's make ai = x * n + i (for some x). Then, let's mod the whole array with n (making ai = i). If the "add update" changed one index, we can just add i + n - ai%n to index i. The problem is, if we make ai = x * n + i, then update an index j > i, ai will be ruined. Just start from the back of the array!
Second solution, 1 add and n mods Note: for any a, b, if b > a, a%b = a. Additionally, if a ≥ b > a/2, a%b = a - b.
Let's add 5x10^5 to the whole array, loop over ai (in order), and mod prefix i with ai - i. Why does this work? Notice that ai%(ai - i) = ai - (ai - i) = i (the second note). Also, ai won't be changed afterwards (the first note).
Imp- if a>=b and b>a/2
Then a%b=a-b;