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

Tested only

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]!;
  }
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?