DSA-029 · Immutable prefix-boundary snapshot
Range Sum Query — Immutable
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 39191 deterministic checks. Learner drafts are not executed.
Understand the problem
Build an immutable sum-query object for an integer array, then answer any number of half-open range-sum queries.
- Construct Solution.NumArray from a non-null array of 0–100,000 signed int entries. Construction reads values without changing the array and captures a snapshot; later caller mutations must not change any query answer. Concurrent mutation during construction is outside the contract.
- sumRange(left,right) returns the long sum over indices left≤i<right. Require 0≤left≤right≤n; invalid endpoints throw IndexOutOfBoundsException. Empty ranges, including [n,n), return zero, and the only query on an empty array is [0,0).
- All prefixes and answers fit in long under the bounds. Prefix storage is private and not exposed. There is no update method: a new snapshot must be constructed to reflect changed source values.
Examples
Input:
nums=[2,-1,3]; sumRange(1,3)
Output:2The half-open range includes -1 and 3, but excludes index 3.
Input:
nums=[2,-1,3]; sumRange(2,2)
Output:0Equal boundaries select no elements.
Before you start
- Array positions versus prefix boundaries and half-open intervals
- Long arithmetic, frequency maps, and invariant reasoning
Recognize the structure
Many queries ask for overlapping sums over an unchanged snapshot. Store cumulative sums at boundaries so each query cancels a shared prefix instead of scanning the requested positions again.
Try before revealing
Hint 1
Define the sum before each boundary, including zero.
Hint 2
How do two prefixes cancel the positions before left?
Hint 3
Store n+1 long prefixes and return prefix[right]-prefix[left].
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Clone once, scan each query
Clone the source array to preserve snapshot semantics, then sum positions left through right-1 on demand. With [2,-1,3], query [0,3) adds 2,-1,3 for 4; [1,3) rescans -1,3 for 2. Construction costs O(n) time/storage; a range of length L costs O(L), including zero work for an empty range. Merely retaining the caller’s array would violate immutability after later writes.
Improve the baseline
Define boundary meanings
Create n+1 long entries. prefix[0]=0 and prefix[b] is the sum of exactly the first b source values. Boundary n is valid even though element index n is not.
Build the snapshot
For each i, prefix[i+1]=prefix[i]+nums[i]. Store only the computed private sums; retaining a source reference is unnecessary.
Subtract shared history
prefix[right] contains [0,right), while prefix[left] contains [0,left). Their difference leaves exactly [left,right), with no endpoint conversion inside the arithmetic.
Why it is correct
Construction invariant
Before processing i, prefix[b] is the exact sum of nums[0..b) for every b≤i. Adding nums[i] establishes the claim for boundary i+1; prefix[0]=0 supplies the base case.
Query identity
The disjoint decomposition [0,right)=[0,left)∪[left,right) implies prefix[right]-prefix[left]=sum(left,right). With left==right, identical prefixes cancel to zero.
Snapshot and bounds
The private prefix values contain no references to mutable source cells. Later source changes cannot affect them. Validated boundaries select existing prefix entries; loops terminate after n elements, including n=0.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static final class NumArray {
private final long[] prefix;
public NumArray(int[] nums) {
prefix = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
}
public long sumRange(int left, int right) {
if (left < 0 || right < left || right >= prefix.length) throw new IndexOutOfBoundsException("require 0 <= left <= right <= n");
return prefix[right] - prefix[left];
}
}
public static final class Baseline {
private final int[] snapshot;
public Baseline(int[] nums) { snapshot = nums.clone(); }
public long sumRange(int left, int right) {
if (left < 0 || right < left || right > snapshot.length) throw new IndexOutOfBoundsException("require 0 <= left <= right <= n");
long sum = 0;
for (int i = left; i < right; i++) sum += snapshot[i];
return sum;
}
}
}
Read the meaningful blocks
Allocate n+1 slots
The extra zero boundary eliminates a separate left==0 branch and represents the empty prefix.
Accumulate as long
Each recurrence adds into a long operand, preserving sums beyond int range from the first addition.
Validate once at the query boundary
Reject reversed, negative, or too-large endpoints before indexing; do not silently clamp an invalid request.
Complexity
O(n) preprocessing time and O(n) persistent snapshot storage. Each sumRange query uses O(1) time and O(1) additional workspace; q queries cost O(n+q) total.
The cloned-scan baseline uses O(n) construction time/storage and O(L) per query of length L, or O(n+ΣL) total. Prefix sums trade preprocessing for repeated query speed, not for constant total storage.
Exact-state walkthroughs
Reveal normal and boundary traces
Build once, query several boundary pairs
Input: {"nums":[2,-1,3],"queries":[[0,3],[1,3],[2,2]]} · Query answers: [4,2,0]
Step 1 of 8: Allocate a snapshot table with an empty-prefix boundary.
Boundary zero is known. Null display slots mean not built yet, rather than Java array contents.
- 0: 2
- 1: -1
- 2: 3
- 0: 0
- 1: unbuilt
- 2: unbuilt
- 3: unbuilt
Empty at this step.
| Variable | Value |
|---|---|
| values | [2,-1,3] |
| prefixBoundaries | [0,null,null,null] |
| builtThrough | 0 |
| answers | [] |
See the affected Java block
1 public final class Solution { 2 public static final class NumArray { 3 private final long[] prefix; 4 public NumArray(int[] nums) { 5 prefix = new long[nums.length + 1]; 6 for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i]; 7 } 8 public long sumRange(int left, int right) { 9 if (left < 0 || right < left || right >= prefix.length) throw new IndexOutOfBoundsException("require 0 <= left <= right <= n"); 10 return prefix[right] - prefix[left]; 11 } 12 } 13 public static final class Baseline { 14 private final int[] snapshot; 15 public Baseline(int[] nums) { snapshot = nums.clone(); } 16 public long sumRange(int left, int right) { 17 if (left < 0 || right < left || right > snapshot.length) throw new IndexOutOfBoundsException("require 0 <= left <= right <= n"); 18 long sum = 0; 19 for (int i = left; i < right; i++) sum += snapshot[i]; 20 return sum; 21 } 22 } 23 } 24
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Allocate a snapshot table with an empty-prefix boundary.
Boundary zero is known. Null display slots mean not built yet, rather than Java array contents.
- values
[2,-1,3]- prefixBoundaries
[0,null,null,null]- builtThrough
0- answers
[]
- Extend the exact sum by one source value.
Every built boundary b contains exactly the sum of the first b source values.
- values
[2,-1,3]- i
0- prefixBoundaries
[0,2,null,null]- builtThrough
1- answers
[]
- Extend the exact sum by one source value.
Every built boundary b contains exactly the sum of the first b source values.
- values
[2,-1,3]- i
1- prefixBoundaries
[0,2,1,null]- builtThrough
2- answers
[]
- Extend the exact sum by one source value.
Every built boundary b contains exactly the sum of the first b source values.
- values
[2,-1,3]- i
2- prefixBoundaries
[0,2,1,4]- builtThrough
3- answers
[]
- Query the completed private snapshot by cancelling shared history.
Only [left,right) remains after subtraction; equal boundaries give zero. Source values are not read during a query.
- values
[2,-1,3]- prefixBoundaries
[0,2,1,4]- builtThrough
3- left
0- right
3- leftPrefix
0- rightPrefix
4- answer
4- answers
[4]
- Query the completed private snapshot by cancelling shared history.
Only [left,right) remains after subtraction; equal boundaries give zero. Source values are not read during a query.
- values
[2,-1,3]- prefixBoundaries
[0,2,1,4]- builtThrough
3- left
1- right
3- leftPrefix
2- rightPrefix
4- answer
2- answers
[4,2]
- Query the completed private snapshot by cancelling shared history.
Only [left,right) remains after subtraction; equal boundaries give zero. Source values are not read during a query.
- values
[2,-1,3]- prefixBoundaries
[0,2,1,4]- builtThrough
3- left
2- right
2- leftPrefix
1- rightPrefix
1- answer
0- answers
[4,2,0]
- Complete the query sequence; each query returns one long.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
- result
[4,2,0]
The empty snapshot has one boundary
Input: {"nums":[],"queries":[[0,0]]} · Query answers: [0]
Step 1 of 3: Allocate a snapshot table with an empty-prefix boundary.
Boundary zero is known. Null display slots mean not built yet, rather than Java array contents.
Empty at this step.
- 0: 0
Empty at this step.
| Variable | Value |
|---|---|
| values | [] |
| prefixBoundaries | [0] |
| builtThrough | 0 |
| answers | [] |
See the affected Java block
1 public final class Solution { 2 public static final class NumArray { 3 private final long[] prefix; 4 public NumArray(int[] nums) { 5 prefix = new long[nums.length + 1]; 6 for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i]; 7 } 8 public long sumRange(int left, int right) { 9 if (left < 0 || right < left || right >= prefix.length) throw new IndexOutOfBoundsException("require 0 <= left <= right <= n"); 10 return prefix[right] - prefix[left]; 11 } 12 } 13 public static final class Baseline { 14 private final int[] snapshot; 15 public Baseline(int[] nums) { snapshot = nums.clone(); } 16 public long sumRange(int left, int right) { 17 if (left < 0 || right < left || right > snapshot.length) throw new IndexOutOfBoundsException("require 0 <= left <= right <= n"); 18 long sum = 0; 19 for (int i = left; i < right; i++) sum += snapshot[i]; 20 return sum; 21 } 22 } 23 } 24
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Allocate a snapshot table with an empty-prefix boundary.
Boundary zero is known. Null display slots mean not built yet, rather than Java array contents.
- values
[]- prefixBoundaries
[0]- builtThrough
0- answers
[]
- Query the completed private snapshot by cancelling shared history.
Only [left,right) remains after subtraction; equal boundaries give zero. Source values are not read during a query.
- values
[]- prefixBoundaries
[0]- builtThrough
0- left
0- right
0- leftPrefix
0- rightPrefix
0- answer
0- answers
[0]
- Complete the query sequence; each query returns one long.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
- result
[0]
Test the contract
Input:
nums=[]; sumRange(0,0)
Output:0One valid empty prefix boundary.
Input:
nums=[7]; sumRange(0,1)
Output:7A single element.
Input:
nums=[2147483647,2147483647]; sumRange(0,2)
Output:4294967294Wide sum.
Input:
nums=[1,2]; sumRange(2,1)
Output:IndexOutOfBoundsExceptionReversed boundaries are rejected.
Common mistakes and counterexamples
Treat right as inclusive
Counterexample: On [2,-1,3], [1,2) should be -1, not 2.
Keep one half-open convention end to end; convert an inclusive external end to end+1 once.
Retain mutable source values for queries
Counterexample: Changing source[0] after construction must not change sumRange(0,1).
Store computed private prefixes, or clone in the baseline.
Use an int prefix
Counterexample: [2147483647,2147483647] totals 4294967294.
Use long storage and return type.
Follow-ups
Allow point updates.
An immutable prefix table needs O(n) repairs after one value changes. A Fenwick tree or segment tree supports updates and sums in O(log n); choose an update-aware API and stop calling the object an immutable snapshot.
Accept inclusive endpoints.
Convert [left,right] to [left,right+1) after validating right<n. State whether an empty inclusive range is representable; do not mix inclusive element indices with prefix boundaries.
Expose many queries as a batch.
Build once and reuse the same object. Returning q results needs O(q) output space, but the query method itself still needs constant extra space. Avoid rebuilding prefixes for every request.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 240/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.