How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time
$\mu^2(i)$ is 1 if $i$ is square-free, or 0 otherwise.  Therefore, your question is equivalent to asking how to count the number of square-free numbers in the range $1..n$.  That has been studied before; see, e.g.,

Counting Square-Free Numbers, Jakub Pawlewicz, arxiv 1107.4890.

That paper claims it can be computed in $\tilde{O}(n^{0.4})$ time (ignoring polylogarithmic factors).