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 (0)

There are currently no matching articles.