p. Here is an update example:
!{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!

p. In $update(6, 5)$ we have to change $A[6]$ to 5 which results in changing the value of $S[1]$ to keep $S$ up to date.

p. In $update(6, 5)$ we have to change $A[6]$ to 5 which results in changing the value of $S[1]$ to keep $S$ up to date.

!{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!

  return s
==

Each query takes less than $k + n/k + k = 2k + n/k$ time. For $k = sqrt(n)$ we get a $O(sqrt(n))$ time complexity query.

Each query takes on average $k/2 + n/k + k/2 = k + n/k$ time. This is minimized for $k = sqrt(n)$. So we get a $O(sqrt(n))$ time complexity query.

This trick also works for other associative operations, like: min, gcd, product etc.

public

protected