Prefix Array
This page provides links to solutions that use the Prefix Array.
Overview
A prefix array, also known as a prefix sum array or cumulative sum array, is an array where each element at an index stores the sum of all elements preceding it, including itself. Prefix arrays are often used to efficiently compute cumulative sums for various ranges within the original array.
How to Spot These Problems
You can identify prefix array problems if the problem requires you to:
- Answering queries about a specific range of the array.
info
A prefix array doesn't support updating an element in the original array in constant time. For such use cases, we should use a segment tree or a Fenwick tree.
Leetcode Problem Set
# ▲ | Solution |
---|---|
548 | Split Array with Equal Sum |