The update takes constant time, because we have to update the value for A and the value for the corresponding $S$.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!

p. The code looks like this:
== code(c) |
def update(S, A, i, k, x):
  S[i/k] = S[i/k] - A[i] + x
  A[i] = x
==
 

The query is interesting. Slices completely contained in our range are summed up fast. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!

p. The code looks like this:

The code looks like this:

== code(c) |

def update(S, A, i, k, x):
  S[i/k] = S[i/k] - A[i] + x
  A[i] = x
 

def query(S, A, lo, hi, k):
  s = 0
  i = lo