Topic 1

9 min read

Array Techniques

Prefix Sum • Sliding Window • Contribution Technique

By Bhagwati Prasad

1. The Setup — Range Sum Query

You are given an array A[] of N elements and Q queries. Each query is a pair (L, R). For every query, return the sum of all elements from index L to index R, both inclusive:

answer = A[L] + A[L+1] + … + A[R]

Worked Example

Take the array:

Index

A[i]

−3

−9

Five queries and their answers:

Query #	L	R	Sum from L to R	Answer
1	4	8	5 + 2 + 8 + (−9) + 3	9
2	3	7	4 + 5 + 2 + 8 + (−9)	10
3	1	3	6 + 2 + 4	12
4	0	4	−3 + 6 + 2 + 4 + 5	14
5	7	7	−9	−9

2. Brute-Force Approach

The most direct solution: for each query, walk from L to R and add up the elements one by one.

function void querySum(int[] A, int queries, int[][] Q):

for (i = 0; i < queries; i++):

L = Q[i][0]

R = Q[i][1]

sum = 0

for (j = L; j <= R; j++):

sum = sum + A[j]

print(sum)

Complexity

Time: Outer loop runs queries times. Inner loop runs at most N times. → TC = O(queries × N)
Space: Just a handful of variables (~5), each ~4 bytes. Total ≈ 20 bytes whether N is 10⁴ or 10⁶. → Extra Space = O(1)

⚠ Why this is a problem

If N = 10⁵ and queries = 10⁵, the total work is 10¹⁰ iterations — far beyond the ~10⁸/sec a judge can do. Result: Time Limit Exceeded.

3. The Cricket Scoreboard Insight

Imagine a cricket match. After every over, the scoreboard records the cumulative runs scored so far:

Over

Cumulative

Three Quick Questions

Question	Calculation	Answer
Runs in just the 7th over?	65 − 49	16
Runs across overs 6 to 10?	97 − 31	66
Runs in just the 10th over?	97 − 88	9

Once cumulative sums are recorded, every range-sum question becomes a single subtraction.

4. The Prefix Sum Array

Apply the same idea to a generic array. Define:

psum[i] = A[0] + A[1] + … + A[i]

Recurrence

Each entry is one addition away from the previous:

psum[0] = A[0]

psum[i] = A[i] + psum[i − 1] (for i ≥ 1)

Built for the Running Example

Index

A[i]

−3

−9

psum[i]

−3

Range-Sum Formula

sum(L, R) = psum[R] − psum[L − 1] when L > 0

sum(0, R) = psum[R] when L = 0

Why subtract psum[L−1]? Because psum[L−1] holds the sum of everything before L, which is exactly what you want to remove from psum[R].

Verification

Query (L = 4, R = 8): psum[8] − psum[3] = 18 − 9 = 9 ✓

Query (L = 1, R = 3): psum[3] − psum[0] = 9 − (−3) = 12 ✓

5. Optimised Pseudocode

Two passes: one to build psum, one to answer queries.

// Step 1: Build the prefix-sum array — O(N)

psum[0] = A[0]

for (i = 1; i < N; i++):

psum[i] = A[i] + psum[i - 1]

// Step 2: Answer each query in O(1)

for (i = 0; i < queries; i++):

L = Q[i][0]

R = Q[i][1]

if (L == 0):

sum = psum[R]

else:

sum = psum[R] - psum[L - 1]

print(sum)

Final Complexity

Approach	Time	Extra Space
Brute force	O(N × queries)	O(1)
Prefix sum	O(N + queries)	O(N)

For N = queries = 10⁵: brute force needs ≈ 10¹⁰ operations (TLE), prefix sum needs ≈ 2 × 10⁵ operations (instant). The trade is O(N) extra memory for the psum array — almost always worth it.

6. Application — Sum of Even-Indexed Elements

Problem

Given an array of size N and Q queries (L, R). For each query, return the sum of all even-indexed elements between L and R, inclusive.

Trick

Build an auxiliary array that keeps even-indexed values and zeroes out odd-indexed ones. Run prefix sum on the auxiliary array.

Walk-Through

A[] = {2, 3, 1, 6, 4, 5}

Index

A[i]

aux[i]

pe[i]

Query (L = 2, R = 5): pe[5] − pe[1] = 7 − 2 = 5 ✓ (= A[2] + A[4] = 1 + 4)

Pseudocode

// Build auxiliary array

for (i = 0; i < N; i++):

if (i % 2 == 0): aux[i] = A[i]

else: aux[i] = 0

// Build prefix sum of aux

pe[0] = aux[0]

for (i = 1; i < N; i++):

pe[i] = pe[i - 1] + aux[i]

// Answer queries

for each query (L, R):

if (L == 0): sum = pe[R]

else: sum = pe[R] - pe[L - 1]

print(sum)

Exercise

Solve the same problem for odd-indexed elements. Mirror the approach: keep odd, zero out even, prefix-sum it.

7. Application — Special Indices

Problem

Given an array of size N, count the number of special indices.

Definition: An index i is special if, after removing A[i] from the array, the sum of all even-indexed elements equals the sum of all odd-indexed elements (in the resulting smaller array).

Walk Through Every i

A[] = {4, 3, 2, 7, 6, −2}

Remove i	Resulting Array	S_even	S_odd	Special?
0	{3, 2, 7, 6, −2}	8	8	✓
1	{4, 2, 7, 6, −2}	9	8	—
2	{4, 3, 7, 6, −2}	9	9	✓
3	{4, 3, 2, 6, −2}	4	9	—
4	{4, 3, 2, 7, −2}	4	10	—
5	{4, 3, 2, 7, 6}	12	10	—

Answer: 2 special indices (i = 0 and i = 2).

Brute Force

For each i (N choices), rebuild the array and recompute both sums (O(N) each). Total: O(N²) — slow for large N.

The Insight

When index i is removed:

• Indices to the left of i (positions 0 … i−1) keep their parity — even stays even, odd stays odd.

• Indices to the right of i (positions i+1 … N−1) flip parity — they all shift left by one slot.

The Formulas

S_even (after removing i) = (S_even in 0…i−1) + (S_odd in i+1…N−1)

S_odd (after removing i) = (S_odd in 0…i−1) + (S_even in i+1…N−1)

Precompute two prefix-sum arrays — pe (prefix of even-indexed values) and po (prefix of odd-indexed values). Then for every candidate i, both sums are O(1) to evaluate. Total: O(N) overall.

Worked Verification

A[] = {2, 3, 1, 4, 0, −1, 2, −2, 10, 8}, remove i = 3.

S_odd afterwards = (S_odd in 0…2) + (S_even in 4…9) = (3) + (0 + 2 + 10) = 15
S_even afterwards = (S_even in 0…2) + (S_odd in 4…9) = (2 + 1) + (−1 − 2 + 8) = 8

8. Sliding Window Technique

Problem

Given an array of N elements and a window length K, print the maximum subarray sum among all subarrays of length exactly K.

Worked Example

A[] = {−3, 4, −2, 5, 3, −2, 8, 2, −1, 4}, K = 5

Index

A[i]

−3

−2

−1

All length-5 windows and their sums:

Start	End	Window	Sum
0	4	{−3, 4, −2, 5, 3}	7
1	5	{ 4, −2, 5, 3, −2}	8
2	6	{−2, 5, 3, −2, 8}	12
3	7	{ 5, 3, −2, 8, 2}	16
4	8	{ 3, −2, 8, 2, −1}	10
5	9	{−2, 8, 2, −1, 4}	11

Maximum: 16 (window starting at index 3).

Brute Force

Recompute each window from scratch — O(K) per window, O(N − K) windows. Total: O(N × K).

The Insight

When the window slides one step right, exactly one element leaves and one enters.

next_sum = current_sum − outgoing + incoming

Each slide is O(1) instead of O(K). Total work drops from O(N × K) to O(N).

Pseudocode

// Step 1: Sum the first window — O(K)

sum = 0

for (i = 0; i < K; i++):

sum = sum + A[i]

max = sum

// Step 2: Slide one step at a time — O(N − K)

s = 0

e = K - 1

while (e + 1 < N):

s = s + 1

e = e + 1

sum = sum - A[s - 1] + A[e]

if (sum > max):

max = sum

print(max)

Complexity: TC = O(N), SC = O(1) extra space — only a few scalar variables.

9. Contribution Technique

Problem

Given an array of integers, find the total sum of all possible subarrays.

Asked in interviews at Google, Facebook.

Worked Example

A[] = {1, 2, 3}

Subarray	Sum
{1}	1
{1, 2}	3
{1, 2, 3}	6
{2}	2
{2, 3}	5
{3}	3
Total	20

Brute Force

Enumerate every (i, j) and sum each subarray: O(N³). With prefix sums: O(N²). Still expensive at large N.

The Insight — Flip the Question

Instead of asking "what is the sum of each subarray?", ask:

For each element A[i], in how many subarrays does it appear?

If A[i] appears in K_i subarrays, it contributes A[i] × K_i to the grand total. So:

Total = Σ A[i] × K_i (for i = 0 … N − 1)

Counting K

A subarray is defined by a (start, end) pair where start ≤ i ≤ end. Independent choices:

Choices for start: 0, 1, …, i → (i + 1) choices.
Choices for end: i, i+1, …, N − 1 → (N − i) choices.

K_i = (i + 1) × (N − i)

Verification

For A[] = {1, 2, 3} (N = 3):

i	A[i]	(i + 1) × (N − i)	Contribution
0	1	1 × 3 = 3	1 × 3 = 3
1	2	2 × 2 = 4	2 × 4 = 8
2	3	3 × 1 = 3	3 × 3 = 9
Total	—	—	20 ✓

Pseudocode

total_sum = 0

for (i = 0; i < N; i++):

total_sum = total_sum + A[i] * (i + 1) * (N - i)

return total_sum

Complexity: TC = O(N), SC = O(1). Down from O(N³) brute force — a single loop replaces three nested ones.

10. Quick-Reference Summary

Technique	When to Use	Cost
Prefix Sum	Many range-sum queries on a static array	Build O(N), answer O(1) per query
Aux + Prefix Sum	Range queries restricted to a subset (even idx, odd idx, multiples of k, …)	O(N) build, O(1) per query
Sliding Window	Optimum (min/max/sum) over every contiguous subarray of fixed length K	O(N) total
Contribution	Aggregate (sum/count) over every possible subarray	O(N) total — each element counted once with its multiplicity

Common thread: avoid recomputing what you already know.

Precompute a smart auxiliary structure once, reuse it many times.