The Constant Time Rule

They must be $O(1)$ for the $O(n\sqrt{m})$ bound, because the query count dominates. An $O(\log n)$ add makes the whole run $O(n\sqrt{m}\log n)$. Queries may arrive online, one at a time.

They must be $O(1)$ for the $O(n\sqrt{m})$ bound, because pointer moves dominate. An $O(\log n)$ add makes the whole run $O(n\sqrt{m}\log n)$. All queries must also be known up front.

They must be invertible for the $O(n\sqrt{m})$ bound, because pointer moves dominate. An $O(\log n)$ add leaves the whole run at $O(n\sqrt{m})$. All queries must also be known up front.

They must be $O(1)$ for the $O(n\sqrt{m})$ bound, because pointer moves dominate. An $O(\log n)$ add makes the whole run $O(n \log n)$. All queries must also be known up front.