Array Techniques

Prefix Sum • Sliding Window • Contribution Technique

Contents

1. The Problem: Range-Sum Queries (Brute Force)

2. The Core Idea: Cumulative Totals

3. The Prefix Sum Array: Definition & Derivation

4. Prefix Sum: Code & Complexity

5. Application 1: Sum of Even-Indexed Elements in a Range

6. Application 2: Counting Special Indices

7. Sliding Window: Maximum Subarray Sum of Size K

8. Contribution Technique: Sum of All Subarrays

9. One-Page Revision Summary

Agenda

This module sits under the broader Array Techniques umbrella. The three techniques covered here are:

• Prefix Sum
• Sliding Window
• Contribution Technique

1. The Problem: Range-Sum Queries (Brute Force)

Setup. You are given an array of N elements and Q queries. Each query gives two indices, an L (left) and an R (right). For every query you must return the sum of all elements from index L to index R (both inclusive).

Worked array (indices on top):

With Q = 5 queries, the expected answers are:

Brute-force code

Complexity

Time. The inner loop can walk up to N elements, and it runs once per query, so TC = O(queries * N).

Space. Only a handful of variables are used (here 5). Five variables x 4 bytes = 20 bytes. Whether N is 10,000, 100,000, or 1,000,000, the extra space stays 20 bytes — it does not grow with N. So SC = O(1). The extra space taken is independent of N.

The repeated work is the weakness: overlapping queries re-add the same elements again and again. The rest of this section removes that repetition.

2. The Core Idea: Cumulative Totals

Before the array trick, build the intuition with a cricket example. You are given the cumulative runs scored after each of 10 overs:

Each number is the running total up to and including that over. To find runs in a particular stretch, subtract the cumulative total just before the stretch from the cumulative total at its end.

• Runs in just the 7th over = (total after 7) − (total after 6) = 65 − 49 = 16.
• Runs in overs 6–10 = (total after 10) − (total after 5) = 97 − 31 = 66.
• Runs in overs 9–10 = (total after 10) − (total after 8) = 97 − 88 = 9.

That single move — end total minus the total just before the start — is the whole idea of prefix sum. The next section applies it to the array.

3. The Prefix Sum Array: Definition & Derivation

Take the same array and build a second array where each cell holds the running total from index 0 up to that index. Call it psum (prefix sum).

Read how each cell is formed: -3, then -3+6 = 3, then 3+2 = 5, then 5+4 = 9, and so on. Each cell is the previous cell plus the current element.

Recurrence

Now any range sum is one subtraction. The sum from L to R equals everything up to R minus everything before L:

• If L > 0: sum(L..R) = psum[R] − psum[L−1]
• If L == 0: sum(L..R) = psum[R] (nothing to subtract)

Re-checking the earlier queries against psum:

• (4,8) = psum[8] − psum[3] = 18 − 9 = 9
• (1,3) = psum[3] − psum[0] = 9 − (−3) = 12
• (0,4) = psum[4] = 14

4. Prefix Sum: Code & Complexity

Step 1 — Build the prefix array

Step 2 — Answer each query in O(1)

Complexity

Building the array is O(N) and answering all queries is O(queries), so overall TC = O(queries + N). This replaces the brute-force product with a sum.

We now store one extra array of size N, so SC = O(N) (extra space).

Smaller end-to-end example:

5. Application 1: Sum of Even-Indexed Elements in a Range

Problem. Given an array of size N and Q queries with a start s and end e, for each query return the sum of all even-indexed elements from s to e.

Idea. Make a helper array that keeps the value only at even indices and writes 0 at odd indices. Then a plain prefix sum over that helper answers every query the same way as before.

Example: A[] = {2, 3, 1, 6, 4, 5} (indices 0–5).

Query (2,5): p_even[5] − p_even[1] = 7 − 2 = 5. The four sample queries return: (1,3)→1, (2,5)→5, (0,4)→7, (3,3)→0.

Code

Quiz. For A[] = {2, 4, 3, 1, 5}, the helper is {2, 0, 3, 0, 5} and its prefix is p_even[] = {2, 2, 5, 5, 10}.

Sum of odd-indexed elements in a range is left as an exercise — it is the same construction with the parity flipped.

6. Application 2: Counting Special Indices

Problem. Given an array of size N, count the number of special indices. An index is special if, after removing it, the sum of all even-indexed elements equals the sum of all odd-indexed elements.

Example: A[] = {4, 3, 2, 7, 6, -2}. Answer = 2. Removing each index in turn and recomputing the even-sum (Se) and odd-sum (So):

Indices 0 and 2 are special, so the answer is 2.

The key insight (so you never re-scan the whole array)

When you remove index i, the elements before it (positions 0 to i−1) keep their original position and parity. The elements after it (positions i+1 to N−1) all shift one step left, so their parity flips: old even becomes odd and old odd becomes even.

That gives two clean formulas:

Worked check on A[] = {2, 3, 1, 4, 0, -1, 2, -2, 10, 8}, removing index 3:

• Odd-index sum of result = S_odd(0..2) + S_even(4..9) = 3 + 12 = 15
• Even-index sum of result = S_even(0..2) + S_odd(4..9) = 3 + 5 = 8

Because the prefix part stays fixed and only the suffix part flips parity, prefix sums of even-indexed and odd-indexed elements let you evaluate each candidate index quickly instead of rebuilding the array every time.

7. Sliding Window: Maximum Subarray Sum of Size K

Problem. Given an array of N elements, print the maximum subarray sum among all subarrays of length K.

Example: N = 10, K = 5, A[] = {-3, 4, -2, 5, 3, -2, 8, 2, -1, 4}.

Maximum = 16. The trick is to avoid re-summing each window from scratch.

Sliding relation: sum of next subarray = sum of current subarray − outgoing element + incoming element.

Example slide from (0,4)=7 to (1,5): 7 − A[0] + A[5] = 7 − (−3) + (−2) = 8.

Code

8. Contribution Technique: Sum of All Subarrays

Problem. Given an array of integers, find the total sum of all possible subarrays. (Previously asked at Google and Facebook.)

Brute force just enumerates every subarray and adds its sum. For A[] = {1, 2, 3, 4, 5} the running totals of all subarray sums add up to 105.

Smaller case to see the pattern — A[] = {1, 2, 3}:

Total = 20.

The insight: count each element's contribution

Instead of summing subarrays, ask for each element A[i]: in how many subarrays does it appear? Call that count K. Then the answer is the sum of K × A[i] over all i.

For {1, 2, 3}: 1×3 + 2×4 + 3×3 = 3 + 8 + 9 = 20 — matching the brute-force total.

Counting the subarrays that contain index i

A subarray that contains index i is fixed by choosing a start (anywhere from 0 to i) and an end (anywhere from i to N−1). These choices are independent, so multiply them:

• choices of start = 0 to i → (i + 1)
• choices of end = i to N-1 → (N - i)
• subarrays containing i = (i + 1) * (N - i)

Check on {3, -2, 4, -1, 2, 6} (N = 6), index 1: starts {0,1} = 2 options, ends {1,2,3,4,5} = 5 options, so 2 × 5 = 10 subarrays — equal to (1+1)(6−1).

Code

9. One-Page Revision Summary

The thread tying it all together: do the heavy work once (a prefix array, a first window, or a per-element count), then answer everything else with cheap arithmetic instead of re-scanning.