Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesMathReviewsAbout
Language
EnglishTürkçe

Prefix Sum

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 6
-2
0
3
-5
2
-1

pref[0] = 0

Immutable nums. Build prefix once, then answer range sums in O(1).

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easyprefix-sum

Range Sum Query. Immutable

Problem (restated)

Design a structure that, given immutable nums, answers sumRange(left, right) efficiently.

Intuition

Precompute prefix[i] = sum of first i elements; range = prefix[r+1]-prefix[l].

Approaches

Prefix sums

Unverified
Time O(1) querySpace O(n)

Idea. Build prefix once; each query is two array lookups.

Walkthrough. nums=[-2,0,3,-5,2,-1]; sumRange(0,2)=1; sumRange(2,5)=-1.

Trade-offs. Segment tree overkill for immutable + range-sum only.

Solution
export class NumArray {
  private pref: number[];
  constructor(nums: number[]) {
    this.pref = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
  }
  sumRange(left: number, right: number): number {
    return this.pref[right + 1]! - this.pref[left]!;
  }
}

export class NumArray {
  private pref: number[];
  constructor(nums: number[]) {
    this.pref = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
  }
  sumRange(left: number, right: number): number {
    return this.pref[right + 1]! - this.pref[left]!;
  }
}

Template connection

Immutable prefix sums: sumRange = prefix[r+1] − prefix[l]. Mutable cousin is Fenwick (LC 307).

Reflection