Typorithm · easy

Range Sum Query

range-sum-queryprefix-sumsprefix-arrayprecomputeo1-query

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Range Sum Query

Prefix Sums

Precompute cumulative sums with a leading zero, then answer any range as the difference of two prefix entries.

Summing a range repeatedly by looping is O(n) per query.

Precomputing a prefix array (with a leading 0) makes each range a single subtraction.

sumRange(l, r) = prefix[r + 1] - prefix[l], answered in O(1).

Prefix array seeded with 0.

Each entry is a running total.

Range = prefix[r+1] - prefix[l].

class NumArray {
  constructor(nums) {
    this.prefix = [0];
    for (const num of nums) {
      this.prefix.push(this.prefix[this.prefix.length - 1] + num);
    }
  }

  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Leading zero

A leading 0 makes every range formula uniform.

this.prefix = [0]

2. Running total

Each entry is the sum of all values before it.

this.prefix.push(this.prefix[this.prefix.length - 1] + num)

3. Difference query

A range sum is the difference of two prefix totals.

return this.prefix[right + 1] - this.prefix[left]

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.