Sum of Numbers in a Range: Naïve, Formula, Prefix Array

Three approaches exist to sum all integers in an inclusive range [L, R]: a loop, a closed-form Gauss formula, and a prefix-sum array for repeated queries.

Each trades a different resource. The loop is O(R-L+1) time with O(1) space. The Gauss formula is O(1) time with O(1) space. The prefix-sum approach costs O(N) time and space to precompute, then answers every query in O(1). Knowing which to reach for is the actual interview skill being tested.

What the Problem Asks

Given two integers L and R, find the sum of all integers from L to R, inclusive. Both endpoints count.

For range [1, 10]: the answer is 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55. For range [3, 7]: the answer is 3 + 4 + 5 + 6 + 7 = 25.

A second variant appears in online judges: given an array, answer Q range-sum queries on it. The naive approach re-traverses a slice for each query. The prefix-sum approach precomputes once and then answers each query in one subtraction.

The Off-by-One Trap

Most bugs in range-sum code come from misreading whether the bounds are inclusive or exclusive. The inclusive convention means [3, 7] includes both 3 and 7. The half-open convention [3, 7) stops at 6, giving 3+4+5+6 = 18. Not 25.

Always check: does the worked example match your formula? For [1, 10] the expected answer is 55. If your formula returns 54 or 56, you have an off-by-one.

Approach 1: Naïve Loop (O(R-L+1) time, O(1) space)

Initialise a counter at zero. Iterate from L to R inclusive, adding each integer to the counter.

Algorithm

• Set sum = 0
• For i from L to R (inclusive), add i to sum
• Return sum

Trace on [3, 7]

• Start: sum = 0
• i = 3: sum = 3
• i = 4: sum = 7
• i = 5: sum = 12
• i = 6: sum = 18
• i = 7: sum = 25
• Return 25. Matches the expected value.

Code

C

#include <stdio.h>

int rangeSum(int L, int R) {
    int sum = 0;
    for (int i = L; i <= R; i++) {
        sum += i;
    }
    return sum;
}

int main() {
    printf("%d\n", rangeSum(1, 10));  // 55
    printf("%d\n", rangeSum(3, 7));   // 25
    return 0;
}

Java

public class RangeSum {
    static int rangeSum(int L, int R) {
        int sum = 0;
        for (int i = L; i <= R; i++) {
            sum += i;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(rangeSum(1, 10));  // 55
        System.out.println(rangeSum(3, 7));   // 25
    }
}

Python

def range_sum(L, R):
    return sum(range(L, R + 1))

print(range_sum(1, 10))  # 55
print(range_sum(3, 7))   # 25

Complexity

• Time: O(R-L+1), linear in the number of integers in the range.
• Space: O(1). Only the accumulator variable is stored.

The loop is suitable when you have one or a few queries and the range fits within time limits. For very large ranges, the loop will time out on a 1-second online judge limit. The Gauss formula fixes that.

Approach 2: Gauss Closed-Form (O(1) time, O(1) space)

The sum of integers from 1 to N is N*(N+1)/2. This is the arithmetic-series formula. The derivation: pair the first and last terms (1 + N), the second and second-last (2 + N-1), and so on. Each pair sums to N+1, and there are N/2 such pairs, giving N*(N+1)/2.

For a range starting at L rather than 1, subtract the sum of [1, L-1] from the sum of [1, R]:

sum(L, R) = R*(R+1)/2 - (L-1)*L/2

Derivation

• sum(1, R) = R*(R+1)/2
• sum(1, L-1) = (L-1)*((L-1)+1)/2 = (L-1)*L/2
• sum(L, R) = R*(R+1)/2 - (L-1)*L/2

Verification

Range [1, 10]:

• R*(R+1)/2 = 10 * 11 / 2 = 55
• (L-1)*L/2 = 0 * 1 / 2 = 0
• Answer: 55 - 0 = 55 ✓

Range [3, 7]:

• R*(R+1)/2 = 7 * 8 / 2 = 28
• (L-1)*L/2 = 2 * 3 / 2 = 3
• Answer: 28 - 3 = 25 ✓

Range [5, 5] (single element):

• R*(R+1)/2 = 5 * 6 / 2 = 15
• (L-1)*L/2 = 4 * 5 / 2 = 10
• Answer: 15 - 10 = 5 ✓

The formula handles a single-element range correctly without a special case.

Code

C

#include <stdio.h>

long long rangeSum(long long L, long long R) {
    return R * (R + 1) / 2 - (L - 1) * L / 2;
}

int main() {
    printf("%lld\n", rangeSum(1, 10));  // 55
    printf("%lld\n", rangeSum(3, 7));   // 25
    return 0;
}

Java

public class RangeSumFormula {
    static long rangeSum(long L, long R) {
        return R * (R + 1) / 2 - (L - 1) * L / 2;
    }

    public static void main(String[] args) {
        System.out.println(rangeSum(1, 10));  // 55
        System.out.println(rangeSum(3, 7));   // 25
    }
}

Python

def range_sum(L, R):
    return R * (R + 1) // 2 - (L - 1) * L // 2

print(range_sum(1, 10))  # 55
print(range_sum(3, 7))   # 25

Overflow note

Use long / long long in C and Java for large inputs. Specific example:

• R = 100,000: R*(R+1)/2 = 5,000,050,000, which exceeds the 32-bit int limit of 2,147,483,647.
• Python integers are arbitrary precision, so no overflow risk.

Complexity

• Time: O(1). Four arithmetic operations.
• Space: O(1).

Approach 3: Prefix-Sum Array for Multiple Queries

When the problem gives you a fixed array and Q queries of the form “sum of elements from L to R”, re-running the loop for each query costs O(N*Q) total. That is slow. A prefix-sum array brings this to O(N) precompute + O(1) per query.

This technique also appears in the equilibrium index problem, where the same prefix-array trick reduces an O(n²) solution to O(n).

Building the Prefix Array

Define prefix[i] as the sum of arr[1] through arr[i]. Use a 1-indexed array with prefix[0] = 0 as a sentinel:

• prefix[0] = 0
• prefix[i] = prefix[i-1] + arr[i] for each i from 1 to N

Answering a Query

The sum of arr[L] through arr[R] is prefix[R] - prefix[L-1].

Subtracting prefix[L-1] removes everything before L. Since prefix[0] = 0, queries starting at L=1 work without a special case.

Trace on arr = [2, 4, 6, 8, 10], query [L=2, R=4]

Build the prefix array (1-indexed):

Index	arr[i]	prefix[i]
0	—	0
1	2	2
2	4	6
3	6	12
4	8	20
5	10	30

Query [2, 4]: prefix[4] - prefix[1] = 20 - 2 = 18.

Direct check: 4 + 6 + 8 = 18. Matches.

The GeeksforGeeks prefix-sum article covers the general competitive-programming formulation, including 2D prefix sums for matrix queries.

Code

C

#include <stdio.h>
#define MAX 1001

int prefix[MAX];

void buildPrefix(int arr[], int n) {
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
}

int query(int L, int R) {
    return prefix[R] - prefix[L - 1];
}

int main() {
    int arr[] = {0, 2, 4, 6, 8, 10};  // 1-indexed, arr[0] unused
    buildPrefix(arr, 5);
    printf("%d\n", query(2, 4));  // 18
    printf("%d\n", query(1, 5));  // 30
    return 0;
}

Java

public class PrefixSum {
    static int[] buildPrefix(int[] arr, int n) {
        int[] prefix = new int[n + 1];
        prefix[0] = 0;
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
        return prefix;
    }

    static int query(int[] prefix, int L, int R) {
        return prefix[R] - prefix[L - 1];
    }

    public static void main(String[] args) {
        int[] arr = {0, 2, 4, 6, 8, 10};
        int[] prefix = buildPrefix(arr, 5);
        System.out.println(query(prefix, 2, 4));  // 18
        System.out.println(query(prefix, 1, 5));  // 30
    }
}

Python

def build_prefix(arr):
    # arr is 1-indexed; arr[0] is unused
    n = len(arr) - 1
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i]
    return prefix

def query(prefix, L, R):
    return prefix[R] - prefix[L - 1]

arr = [0, 2, 4, 6, 8, 10]
prefix = build_prefix(arr)
print(query(prefix, 2, 4))  # 18
print(query(prefix, 1, 5))  # 30

Complexity

• Build: O(N) time, O(N) space.
• Query: O(1) time, O(1) extra space.
• Q queries on the same array: O(N + Q) total, vs. O(N*Q) with the naive approach.

The space complexity angle here: the prefix array is the canonical O(N) auxiliary-space trade-off that delivers O(1) per-query time. That trade-off is worth memorising.

Choosing the Right Approach

Scenario	Best approach	Why
One query, any range	Gauss formula	O(1) time and space, no setup
A few queries, small range	Naïve loop	Simple, no precompute needed
Many queries (Q > 100) on a fixed array	Prefix-sum array	O(N+Q) beats O(N*Q)
Range contains negative values or arbitrary array	Loop or prefix-sum	Gauss formula requires consecutive positive integers
Memory is constrained	Loop or Gauss formula	Prefix-sum uses O(N) extra space

The related problem of finding the sum of digits uses a different loop pattern (modulo-divide instead of accumulate-increment) but shares the same iteration discipline worth knowing alongside range sum. For array traversal problems with hash-map structure, symmetric pairs in an array is a natural follow-on.

The O(1) formula insight (that a closed-form expression can replace a loop of any size) is the same reasoning behind caching and memoisation in larger systems. At the LLM layer, that principle is KV-cache reuse. Precompute the prefix context once; every subsequent call reuses it without reprocessing. TinkerLLM lets you build and test LLM-powered applications at ₹299, and the range-sum instinct you practise here applies directly to the optimisation problems you will hit there.