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): 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 O(1) time for an update and O(r - l) = O(n) 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.
The update takes constant time.
The code looks like this:

[code]

S[i/k] = S[i/k] - A[i] + x
A[i] = x

[/code]

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.

The code looks like this:

[code]

i = l
while i % k != 0 and i < r:
  sum += a[i]

while lo + 1 <= r:
   lo += 1
   sum += a[lo]

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

[/code]
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.

This trick also works for other associative operations, like: min, gcd, product etc.

Nearest neighbour
Given a set S of n points and a query point p, find the point in S closest to p.

Given two strings A (n characters) and B (m characters), find their longest common subsequence. (eg. The longest common sub sequence for abcabc and abcbcca is abcbc.)
There is a standard dynamic programming solution:

[code]

best[i][j] = longest common sub sequence for A[0:i] and B[0:j], computed as below:
if A[i] == B[j]:
   best[i][j] = 1 + best[i - 1][j - 1]
else:
  best[i][j] = max(best[i-1][j], best[i][j-1])

[/code]

This algorithm takes O(nm) time and only O(n) space, since to compute a row you just need the previous row.
If you must return the actual sub sequence this doesn't work. You can keep an array of parent pointers, so that for each state (i, j) you know the previous state in the solution. The longest sub sequence corresponds to a path from (n-1, m-1) to (0, 0) on the parent matrix.  This solution takes O(nm) space.