DP Precomputation & Lookup Tables

Lesson 2 of 5

Prerequisites

Sum-Array Win Detection

DP Precomputation & Lookup Tables

What is it? (The Analogy)

Imagine you run a pizza restaurant. Every day, customers ask "How much would a pizza with

toppings A, B, and C cost?" If you calculate the price from scratch every time — looking up

each topping price, applying discounts, adding tax — that is slow when you have a hundred

customers asking the same questions.

Instead, what if you precomputed a menu card at the start of the day? You calculate the

price of every popular combination once, write it on a sheet, and when a customer asks, you

just look it up instantly. That is precomputation — doing expensive work once up front

so that every future query is a simple, fast lookup.

In computer science, DP (Dynamic Programming) precomputation means building a table of

answers before anyone asks. A classic example: the prefix sum array. If you have a list

of numbers and someone keeps asking "What is the sum from index i to index j?", you could

add up the numbers each time (slow) or build a prefix sum table once and answer every query

by subtracting two numbers (fast).

**The core idea: Pay a one-time cost to build a table, then answer unlimited queries

for free.**

Why do we need it?

The Problem: Repeated Expensive Queries

Consider a school that tracks daily test scores for every student across the year. The

principal frequently asks: "What was Student X's average score between Week 3 and Week 7?"

Brute force approach:

java

1// Every query sums up scores from index i to j — O(N) per query
2int rangeSum(int[] scores, int from, int to) {
3    int sum = 0;
4    for (int k = from; k <= to; k++) {
5        sum += scores[k];
6    }
7    return sum;
8}

If there are N scores and Q queries, the total cost is **O(N * Q)**. With 365 days and

1000 queries, that is 365,000 operations. Not terrible, but imagine a system with millions

of data points and thousands of queries per second.

The Better Way: Prefix Sum Table

Build a prefix sum array once in O(N) time. Then answer every query in O(1):

java

1scores:    [3, 1, 4, 1, 5, 9, 2, 6]
2prefix:    [0, 3, 4, 8, 9, 14, 23, 25, 31]
3              ^-- prefix[0] = 0 (sentinel)
4
5Sum from index 2 to 5 = prefix[6] - prefix[2] = 23 - 4 = 19
6Verification: 4 + 1 + 5 + 9 = 19  ✓

How it works — Step by Step

Pattern 1: 1D Prefix Sum

Allocate a prefix array of size N+1, initialized to 0.
Build the prefix array: prefix[i] = prefix[i-1] + scores[i-1] for i from 1 to N.
Query the sum from index from to to (inclusive):

sum = prefix[to + 1] - prefix[from]

That is it. O(N) build time, O(1) per query.

Pattern 2: 2D Prefix Sum (for grids)

For a matrix, the idea extends to two dimensions. Useful in image processing, game boards,

and heat maps.

Build: prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
Query the sum of a subgrid from (r1,c1) to (r2,c2):

sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

Pattern 3: Lookup Tables for Computed Results

Sometimes the "table" is not a sum but any expensive computation:

Factorials for combinatorics
Power-of-2 tables for bit manipulation
Win/loss lookup tables for game states

Let's Build It Together

Let's build a School Score Analyzer that answers range queries about student scores

using prefix sums.

java

1/**
2 * SchoolScoreAnalyzer — demonstrates DP precomputation with prefix sums.
3 *
4 * Scenario: Ms. Johnson wants to quickly find the total score
5 * for any range of days for her student.
6 */
7public class SchoolScoreAnalyzer {
8
9    private int[] prefixSum;  // Our precomputed lookup table
10
11    /**
12     * Step 1: Build the prefix sum table.
13     * This is the ONE-TIME cost we pay up front.
14     *
15     * @param dailyScores array of scores, one per day
16     */
17    public SchoolScoreAnalyzer(int[] dailyScores) {
18        int n = dailyScores.length;
19
20        // prefix[0] = 0 is a sentinel — it means "sum of zero elements"
21        // prefix[1] = dailyScores[0]
22        // prefix[2] = dailyScores[0] + dailyScores[1]
23        // and so on...
24        prefixSum = new int[n + 1];
25        prefixSum[0] = 0;
26
27        for (int i = 1; i <= n; i++) {
28            prefixSum[i] = prefixSum[i - 1] + dailyScores[i - 1];
29        }
30        // Done! We spent O(N) time here but saved O(1) per query.
31    }
32
33    /**
34     * Step 2: Answer a range query INSTANTLY.
35     *
36     * "What is the total score from day 'from' to day 'to'?"
37     *
38     * @param from start day (0-indexed, inclusive)
39     * @param to   end day (0-indexed, inclusive)
40     * @return sum of scores in that range
41     */
42    public int totalScoreInRange(int from, int to) {
43        // This is the magic one-liner.
44        // prefix[to + 1] contains sum of days 0..to
45        // prefix[from]   contains sum of days 0..(from-1)
46        // Subtracting gives us exactly sum of days from..to
47        return prefixSum[to + 1] - prefixSum[from];
48    }
49
50    /**
51     * Bonus: Average score in a range.
52     */
53    public double averageScoreInRange(int from, int to) {
54        int total = totalScoreInRange(from, to);
55        int count = to - from + 1;
56        return (double) total / count;
57    }
58}

Using it:

java

1public class ScoreDemo {
2    public static void main(String[] args) {
3        // Alice's daily quiz scores over 8 days
4        int[] aliceScores = {85, 90, 78, 92, 88, 76, 95, 89};
5
6        SchoolScoreAnalyzer analyzer = new SchoolScoreAnalyzer(aliceScores);
7
8        // Ms. Johnson asks: "Total score from day 2 to day 5?"
9        System.out.println(analyzer.totalScoreInRange(2, 5));
10        // Answer: 78 + 92 + 88 + 76 = 334
11
12        // "Average score for the whole week (day 0 to day 6)?"
13        System.out.println(analyzer.averageScoreInRange(0, 6));
14        // Answer: (85+90+78+92+88+76+95) / 7 = 86.29
15    }
16}

Now let's see a 2D example — a game board heat map:

java

1/**
2 * GameBoardAnalyzer — 2D prefix sums for subgrid queries.
3 *
4 * Scenario: A strategy game board where each cell has a "resource value."
5 * The player asks "How many total resources are in this rectangular region?"
6 */
7public class GameBoardAnalyzer {
8
9    private int[][] prefix;
10
11    public GameBoardAnalyzer(int[][] board) {
12        int rows = board.length;
13        int cols = board[0].length;
14
15        // Build 2D prefix sum with an extra row and column of zeros
16        prefix = new int[rows + 1][cols + 1];
17
18        for (int i = 1; i <= rows; i++) {
19            for (int j = 1; j <= cols; j++) {
20                // Include current cell + top + left - overlap (top-left)
21                prefix[i][j] = board[i - 1][j - 1]
22                              + prefix[i - 1][j]
23                              + prefix[i][j - 1]
24                              - prefix[i - 1][j - 1];
25            }
26        }
27    }
28
29    /**
30     * Sum of all values in the rectangle from (r1, c1) to (r2, c2), inclusive.
31     *
32     * Think of it like cutting out a rectangle from a sheet:
33     * Take the big rectangle, subtract the top strip, subtract the left strip,
34     * but add back the corner that was subtracted twice.
35     */
36    public int regionSum(int r1, int c1, int r2, int c2) {
37        return prefix[r2 + 1][c2 + 1]
38             - prefix[r1][c2 + 1]
39             - prefix[r2 + 1][c1]
40             + prefix[r1][c1];
41    }
42}

Dry Run / Trace

1D Prefix Sum Trace:

java

1Input scores: [85, 90, 78, 92, 88, 76, 95, 89]
2Index:          0   1   2   3   4   5   6   7
3
4Building prefix sum array:
5  prefix[0] = 0
6  prefix[1] = 0 + 85  = 85
7  prefix[2] = 85 + 90  = 175
8  prefix[3] = 175 + 78  = 253
9  prefix[4] = 253 + 92  = 345
10  prefix[5] = 345 + 88  = 433
11  prefix[6] = 433 + 76  = 509
12  prefix[7] = 509 + 95  = 604
13  prefix[8] = 604 + 89  = 693
14
15prefix = [0, 85, 175, 253, 345, 433, 509, 604, 693]

Query: totalScoreInRange(2, 5)

java

1  = prefix[5 + 1] - prefix[2]
2  = prefix[6] - prefix[2]
3  = 509 - 175
4  = 334
5
6  Verify: scores[2] + scores[3] + scores[4] + scores[5]
7        = 78 + 92 + 88 + 76
8        = 334  ✓

Query: totalScoreInRange(0, 7) (entire array)

java

  = prefix[8] - prefix[0]
  = 693 - 0
  = 693

  Verify: 85 + 90 + 78 + 92 + 88 + 76 + 95 + 89 = 693  ✓

Query: totalScoreInRange(4, 4) (single element)

java

  = prefix[5] - prefix[4]
  = 433 - 345
  = 88

  Verify: scores[4] = 88  ✓

2D Prefix Sum Trace:

java

1Board (resource values):
2  [1, 2, 3]
3  [4, 5, 6]
4  [7, 8, 9]
5
6Building 2D prefix:
7  prefix[1][1] = 1 + 0 + 0 - 0 = 1
8  prefix[1][2] = 2 + 0 + 1 - 0 = 3
9  prefix[1][3] = 3 + 0 + 3 - 0 = 6
10  prefix[2][1] = 4 + 1 + 0 - 0 = 5
11  prefix[2][2] = 5 + 3 + 5 - 1 = 12
12  prefix[2][3] = 6 + 6 + 12 - 3 = 21
13  prefix[3][1] = 7 + 5 + 0 - 0 = 12
14  prefix[3][2] = 8 + 12 + 12 - 5 = 27
15  prefix[3][3] = 9 + 21 + 27 - 12 = 45
16
17Query: regionSum(1, 1, 2, 2) — the 2x2 bottom-right block
18  = prefix[3][3] - prefix[1][3] - prefix[3][1] + prefix[1][1]
19  = 45 - 6 - 12 + 1
20  = 28
21
22  Verify: 5 + 6 + 8 + 9 = 28  ✓

Time & Space Complexity

Approach	Build Time	Query Time	Space
No precomputation	None	O(N) per query	O(1)
1D Prefix Sum	O(N)	O(1) per query	O(N)
2D Prefix Sum	*O(NM)**	O(1) per query	*O(NM)**

When to use it: When you have many queries on the same static data. If Q queries each

take O(N) without precomputation, the total is O(N*Q). With precomputation, it is

O(N + Q) — a massive improvement when Q is large.

When NOT to use it: If the data changes frequently (updates between queries), a simple

prefix sum will not work. You would need a Segment Tree or Fenwick Tree instead.

Common Mistakes & Gotchas

Off-by-one errors are the #1 bug. The prefix array has size N+1, not N. The sentinel

value prefix[0] = 0 is crucial. Always draw it out on paper first.

Forgetting the sentinel. Without prefix[0] = 0, the query formula `prefix[to+1] -

prefix[from] breaks for from = 0`.

Modifying the original data after building the prefix sum. The prefix sum is a

snapshot. If the data changes, you must rebuild (or use a different data structure).

Integer overflow. If scores can be large and the array is long, prefix[N] might

overflow an int. Use long when needed.

2D inclusion-exclusion errors. In the 2D case, remember the formula:

add big rectangle, subtract top strip, subtract left strip, add back the corner.

Drawing a Venn diagram helps.

Interview Tip

Precomputation is a meta-technique that appears everywhere in LLD interviews.

Whenever you see a design that involves "frequent reads, rare writes," think

precomputation. Examples: leaderboard systems (precompute rankings), pricing engines

(precompute totals), and game boards (precompute sums for win detection). The interviewer

is looking for you to say: "We can precompute this so that queries are O(1)."

Quick Quiz

Design challenge: You are building a weather dashboard that shows the average

temperature for any date range. New readings arrive once per day. Would a prefix sum

work here? What happens when new data arrives?

Think about it: Can you use prefix sums to find the maximum value in a range?

Why or why not? (Hint: what mathematical property does max lack that sum has?)

2D extension: If you need to count how many cells in a subgrid have a value above

a threshold, how would you adapt the 2D prefix sum approach?

Summary — Key Takeaways

Precomputation trades build time for query speed. Pay O(N) once, get O(1) per query

forever.

Prefix sums are the most common precomputation pattern. They work for sums, counts,

and anything that can be expressed as a running total.

**The sentinel value prefix[0] = 0 is essential.** It makes the query formula clean and

handles edge cases like "sum from the very beginning."

This technique appears in almost every LLD problem — from game scoring to booking

systems to analytics dashboards. Master it, and you unlock O(1) queries everywhere.

Sum-Array Win DetectionPrevious

Home

SCAN (Elevator) AlgorithmNext