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$$.