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!

             = 0 + 7 + 11 + 9 + 5 + 2 + 0
             = 34
==

 
The code looks like this:

Here's how the code looks:

== code(c) |
def update(S, A, i, k, x):

  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