Loading...

Preview

Showing 8 of 25 steps

Login to see all

Prefix Sum (1D)

Easy

Prefix Sum (1D)

Preprocessing technique for O(1) range sum queries

📊 Complexity

Type	Value
Average	O(n) 전처리, O(1) 쿼리
Worst	O(n) 전처리, O(1) 쿼리
Space	O(n)

🏷️ Tags

Range SumPreprocessingArray

📖 Introduction

Prefix Sum is a technique that pre-calculates cumulative sums from the first element to each position, enabling O(1) range sum queries.

1/25

Loading...

🚀Fast Range Sums!

Prefix Sum calculates range sums in O(1)! By pre-calculating sums, any range sum can be found with just one subtraction! 🚀

Basics

Prefix Sum (1D)

Definition

Prefix Sum is a technique that pre-calculates cumulative sums from the first element to each position, enabling O(1) range sum queries.

Key Characteristics

✓prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
✓Range sum: sum(l, r) = prefix[r+1] - prefix[l]
✓O(n) preprocessing, then O(1) per query
✓Extends to 2D for O(1) submatrix sums

Time Complexity

Average

O(n) 전처리, O(1) 쿼리

Worst

O(n) 전처리, O(1) 쿼리

Space Complexity

O(n)

Prefix Sum (1D) | AlgoNote