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]+(A[4]+A[5]+A[6]+A[7])+(A[8]+A[9]+A[10]+A[11])+A[12]+A[13]+A[14]</tex>
 
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