Range Sum
Given an n elements array, implement a data structure for point updates and range sum queries:

- set(i, x): a[i] := k,
- sum(l, r) returns a[l] + a[l+1] + .. + a[r]).

-<tex>set(i, x)</tex><tex>: a[i] := k</tex>,
-<tex>sum(l, r) returns a[l] + a[l+1] + .. + a[r])</tex>.

The naive solution uses an array. It takes <tex>O(1)</tex> time for an update and <tex>O(r - l) \eq O(n)</tex> for the range sum.

The naive solution uses an array. It takes <tex>O(1)</tex> time for an update and <tex>O(r - l) = O(n)</tex> for the range sum.

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