concept · INFO-CS-ADS-224Prefix Sums and Difference Arrays
Prefix Sums and Difference Arrays are complementary techniques for processing range queries and range updates efficiently. Prefix sums answer cumulative or static range-sum queries, while difference arrays simplify repeated range additions.
Explanation
Overview
A Prefix Sum Array stores cumulative totals so that the sum of a range can be calculated using the difference between two prefix values. A Difference Array stores changes between consecutive elements so that adding a value to an entire range can be represented using only two boundary updates.
Key concepts
Cumulative sums; Range queries; Boundary updates; Difference representation; Prefix reconstruction; Zero-based indexing
Time complexity
operation: Build prefix sums; complexity: O(n); operation: Prefix-sum range query; complexity: O(1); operation: Build difference array; complexity: O(n); operation: Individual range update; complexity: O(1); operation: Reconstruct final array; complexity: O(n)
Space complexity
O(n) for the prefix or difference array.
Example
originalArray: 2; 4; prefixSums: 2; 6; query: range: 1; 3; calculation: 10 - 2; differenceArray: description: Add 3 to every element from index 1 through index 3.; boundaryUpdates: diff[1] += 3; diff[4] -= 3
Applications
Static range-sum queries; Repeated range additions; Frequency accumulation; Subarray sum problems; Matrix prefix sums; Scheduling and interval updates
Advantages
Prefix sums answer static range-sum queries in constant time after preprocessing.; Difference arrays make repeated range-add operations efficient.; Both techniques are simple to implement.; They are useful building blocks for more advanced data structures and algorithms.
Example or application
Difference Array
Description
Add 3 to every element from index 1 through index 3.
Definition
A Prefix Sum Array stores cumulative totals so that the sum of a range can be calculated using the difference between two prefix values. A Difference Array stores changes between consecutive elements so that adding a value to an entire range can be represented using only two boundary updates.
Prefix Sums
Description
For an original array, the prefix sum at index i represents the sum of all elements from the beginning through i. Using a prefix array, an inclusive range sum can be calculated without traversing the entire range.
Formula
prefix[i] = array[0] + array[1] + ... + array[i]
Range Query
sum(L, R) = prefix[R] - prefix[L - 1]
Note
When L is zero, the query uses prefix[R] directly if the prefix array is indexed in the same way. A common alternative is a prefix array of length n + 1 with prefix[0] = 0.
Difference Arrays
Description
A Difference Array stores the change between neighboring values. A range addition can be represented by adding the update value at the left boundary and subtracting it immediately after the right boundary.
Formula
diff[L] += value; diff[R + 1] -= value
Reconstruction
The original updated values are reconstructed by taking cumulative sums of the difference array.
Note
The difference array is especially useful when many range updates are performed before the final array is needed.
Implementation
Code
function buildPrefix(array):
prefix = array of size n + 1
prefix[0] = 0
for i from 0 to n - 1:
prefix[i + 1] = prefix[i] + array[i]
return prefix
function rangeSum(prefix, left, right):
return prefix[right + 1] - prefix[left]
function rangeAdd(diff, left, right, value):
diff[left] += value
if right + 1 < length(diff):
diff[right + 1] -= value
Time Complexity
| Operation | Complexity |
|---|
Build prefix sums | O(n) |
Prefix-sum range query | O(1) |
Build difference array | O(n) |
Individual range update | O(1) |
Reconstruct final array | O(n) |
Space Complexity
O(n) for the prefix or difference array.
Advantages
Prefix sums answer static range-sum queries in constant time after preprocessing.
Difference arrays make repeated range-add operations efficient.
Both techniques are simple to implement.
They are useful building blocks for more advanced data structures and algorithms.
Limitations
A standard prefix-sum array does not efficiently support arbitrary point updates.
A difference array is most useful when updates are collected before reconstructing the final values.
Care is needed with inclusive and exclusive range boundaries.
Large cumulative values may require a wider numeric type.
Related Topics
Segment Trees
Fenwick Trees
Sliding Window Technique
Range Queries
Array Processing
Practice Questions
| Question | Answer |
|---|
What information does a prefix sum store? | The cumulative sum of elements from the beginning of an array up to a particular position. |
How can a static range sum be answered using prefix sums? | Subtract the prefix sum before the left boundary from the prefix sum at the right boundary. |
How many boundary changes are needed for one range addition in a difference array? | Usually two: add the value at L and subtract it at R + 1. |
When should a difference array be used? | When many range updates are performed and the final array is reconstructed afterward. |
Learning Objectives
Explain the central idea and purpose of prefix sums and difference arrays.
Identify the assumptions, inputs, and conditions relevant to prefix sums and difference arrays.
Evaluate an application of prefix sums and difference arrays for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Specialized Algorithms and Computational Topics
Suggest a correction or source · More in Algorithms & Data Structures