MO's with Updates

Standard MO's handles read-only queries. What if you have point updates mixed with queries? Treat time as a third dimension.

Each query now has $(l, r, t)$ where $t$ is the timestamp (number of updates before this query).

Sort by $(\lfloor l/B \rfloor, \lfloor r/B \rfloor, t)$ with block size $B = n^{2/3}$. You now have three pointers: $currentL$, $currentR$, and $currentT$.

Moving $currentT$ applies or undoes updates. Complexity: $O(n^{5/3})$ with the optimal block size.