TLDR
Prefix sums is a simple yet powerful technique that we can use to easily calculate the sum of a segment or an array. It allows us to use a reusable lookup array to look up the sum for the whole array in constant time. The first approach would have been how many times we need to recalculate different array segments. With prefix sums, our time is reduced to O(O(n + m) times we can get the sum in constant O(1) time. In this post, we will look at prefix sums and how they can be used to solve a common coding problem.via the TL;DR App
no story
Written by micogongob | Software Engineer from the Philippines
