For a finite sequence , its suffix sums are , with . They satisfy , so one backward pass computes all of them in additions.
For , the suffix sums are including the empty suffix. A range sum on is . Thus suffix sums provide the same constant-time range queries as prefix sums, with the accumulation direction reversed.
Articles by others on the same topic
There are currently no matching articles.