Skip to content

Static Range Sum Queries

  • Title: Static Range Sum Queries
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1646
  • Secondary topics: 1D prefix sum, Range subtraction, Immutable array
  • Difficulty: easy
  • Subtype: Answer many range-sum queries on an array that never changes
  • Status: solved
  • Solution file: staticrangesumqueries.cpp

Why Practice This

This is the cleanest first prefix-sum problem in CSES.

The problem statement gives exactly the pattern we want to recognize early:

  • many range-sum queries
  • no updates
  • each answer should come from one precomputation

If this problem does not feel automatic yet, prefix-sum indexing discipline probably still needs a bit more repetition.

Recognition Cue

Reach for plain prefix sums when:

  • the array never changes
  • there are many range-sum queries
  • each query asks for an aggregate over one contiguous interval
  • the intended answer should be O(1) after one preprocessing pass

The strongest anti-cue is any update operation. Once updates appear, this exact tool is usually no longer enough.

Problem-Specific Transformation

The statement is already close to the final pattern. The only real rewrite is indexing:

  • build pref[i] = sum of first i elements
  • answer [l, r] by subtracting away the prefix before l

So the whole task becomes:

  • preprocess one cumulative array once
  • convert every inclusive range into one subtraction

This is why the problem is such a good first anchor: almost all of the work is choosing a clean indexing convention and staying faithful to it.

Core Idea

Build a prefix array where:

pref[i] = sum of the first i elements
pref[0] = 0

Then for a query [l, r] in one-based indexing:

sum(l..r) = pref[r] - pref[l - 1]

Why does that work?

Because pref[r] contains everything up to r, while pref[l - 1] contains exactly the part before the query range. Subtracting removes the left prefix and leaves only the sum on [l, r].

This is the core prefix-sum pattern:

  • preprocess once in O(n)
  • answer every static range query in O(1)

Complexity

  • prefix build: O(n)
  • each query: O(1)
  • memory: O(n)

Pitfalls / Judge Notes

  • Use long long because sums can exceed int.
  • The safest convention is pref[0] = 0 and pref[i] = sum of first i elements.
  • Queries are one-based and inclusive, so pref[r] - pref[l - 1] works directly.
  • This is static data. If updates appeared, prefix sums would no longer be enough on their own.

Reusable Pattern

Solutions