The range sum 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;border: 1px solid gray;}blog/square-root-trick?image00.png!
 

The code looks like this:
== code(c) |
i = l

   sum += a[lo]
==

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

The query takes less than <tex>k + n/k + k = 2k + n/k</tex> time. 2k + n/k is minimized when k ~ sqrt(n). For k = sqrt(n) the query takes O(sqrt(n)) time.