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!

In $query(2, 14)$ we get <tex>A{2} + A{3}</tex> <tex> + (A[4] + A[5] + A[6] + A[7]) + (A[4] + A[5] + A[6] + A[7]) + A[12] + A[13] + A[14] = A[2] + A[3] + S[1] + S[2] + A[12] + A[13] + A[14] = 0 + 7 + 11 + 9 + 5 + 2 + 0 = 34</tex>
 
p. The code looks like this:

In $query(2, 14)$ we get
== code(c) |
query(2, 14) = A[2] + A[3]+
               (A[4] + A[5] + A[6] + A[7]) +
               (A[8] + A[9] + A[10] + A[11]) +
               A[12] + A[13] + A[14]
             = A[2] + A[3] +
               S[1] + S[2] +
               A[12] + A[13] + A[14]
             = 0 + 7 + 11 + 9 + 5 + 2 + 0
             = 34
==
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