p. The naive solution uses an array. It takes $O(1)$ time for an update and $O(hi - lo) = O(n)$ for the range sum.

A more efficient solution splits the array into length $k$ slices and stores the slice sums in an array $S$.

p. A more efficient solution splits the array into length $k$ slices and stores the slice sums in an array $S$.

The update takes constant time, because we have to update the value for A and the value for the corresponding $S$.

p. The update takes constant time, because we have to update the value for A and the value for the corresponding $S$.

The query is interesting. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one, but for slices completely contained in our range we can use the values in $S$ directly and get a performance boost.

Here are an update and a query example:

p. Here is an update example:
!{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!

p. !<{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. !<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!

!{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!

p. In update(2, 5) we have to change A[2] which results in changing the value of S[1] to keep S up to date. In query(2, ) we get A[2] + A[3] + (A[4] + ...
 
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