Prefix Sums & O(1) Range Queries

A Prefix Sum array precomputes cumulative totals: P[i] = P[i-1] + arr[i]. Any range sum query sum(L, R) is answered in O(1) time via P[R] - P[L-1].

class PrefixSum {
  prefix: number[];
  constructor(nums: number[]) {
    this.prefix = [0];
    for (let i = 0; i < nums.length; i++) {
      this.prefix.push(this.prefix[i] + nums[i]);
    }
  }
  query(L: number, R: number): number {
    return this.prefix[R + 1] - this.prefix[L]; // O(1) instant range sum!
  }
}