distance problem

A turnpike consists of n-1 stretches of road between n toll stations; Each stretch has an associated cost of travel. It is trivial to tell the cost of going between any 2 stations in O(n) time using only an array of the costs, or in constant time using a table of O(n^2) entries. Describe a data structure that requires O(n) space but allows the cost of any route to be computed in constant time.

Answer:

|------|-----|-----|-----|--------|
   a      b     c     d       e

An entry i in an array stores the sum of distance from the start of all stations <=i

i.e
distance[1] = a;
distance[2] = a+b;
distance[3] = a+b+c; 
and so on,

So distance between any two given stations i and j, distance[j] - distance[i]