Quick Post: Sum Table

If you have an array of values, how can you take the sum of any range of them in constant time? With a sum table!

Here's a formal definition:

Given a list of values v_0, ..., v_n, then a sum table is a corresponding list s_0, ..., s_n such that s_i=\sum\limits_{j=0}^i v_j. That is, each value in the sum table is the sum of all the values up until that index. Then, the sum of values between any two can be easily found: s_{ij} = s_j - s_i.

Leave a Reply