What signals in a problem statement indicate the Static range sum sub-pattern?

"sum of elements between l and r", called many times; a class with a constructor and a query function; "sum of the rectangle" in a matrix; "running sum"

Static range sum (Prefix Sum Sub-pattern)

Q: What makes Static range sum different from other sub-patterns?

No hash map, no search — just precompute and subtract. A *running sum* (`running[i]` includes `nums[i]`) and the *prefix array* are the same numbers shifted by one: `prefix[i + 1] = running[i]`. The leading 0 is what makes `l = 0` safe. In 2D the rectangle needs **four** corners: add the big one, subtract two strips, and add back the corner you subtracted twice.

The data never changes, and you're asked for many range sums. Build the prefix array once (O(N)), then answer each question with one subtraction.

Signals in the problem statement

›
"sum of elements between l and r", called many times
›
a class with a constructor and a query function
›
"sum of the rectangle" in a matrix
›
"running sum"

What makes it different

No hash map, no search — just precompute and subtract. A running sum (running[i] includes nums[i]) and the prefix array are the same numbers shifted by one: prefix[i + 1] = running[i]. The leading 0 is what makes l = 0 safe. In 2D the rectangle needs four corners: add the big one, subtract two strips, and add back the corner you subtracted twice.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Running Sum of 1d Array
Basic Anchor·LeetCode #1480
WalkthroughEasy
2
Range Sum Query – Immutable
Basic Reinforcement·LeetCode #303
WalkthroughEasy
3
Range Sum Query 2D – Immutable
Slight Variation·LeetCode #304
WalkthroughMedium

Template

range-template.cpp

// Build once: prefix[i] = sum of the first i elements, prefix[0] = 0.
vector<long long> buildPrefix(const vector<int>& nums) {
    vector<long long> prefix(nums.size() + 1, 0);
    for (int i = 0; i < (int)nums.size(); i++)
        prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

// Sum of nums[l..r] (inclusive) in O(1): everything up to r, minus everything before l.
long long rangeSum(const vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Prefix Sum overview Exact sum + hash map