If you do block decomposition of size $O(n^{1/4})$ on the $blocks$ array, you could also attain $O(1)$ update and $O(sqrt(n))$ query complexity. I think it's more intuitive, but it seems a bit slower.
If you do block decomposition of size $O(n^{1/4})$ on the $blocks$ array, you could also attain $O(1)$ update and $O(sqrt(n))$ query complexity. I think it's more intuitive, but it seems a bit slower.