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 […]
More