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:

p. The code looks like this:

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