Loading learning content...
One of the most powerful optimization principles in computer science can be stated simply: Do work once, benefit many times. This is the essence of preprocessing—investing computational effort upfront to transform data into a form that makes subsequent operations dramatically faster.
Consider a chef who spends an hour in the morning preparing ingredients: washing, chopping, organizing. Each individual dish then takes minutes instead of the hour it would take starting from raw ingredients. The preprocessing investment pays dividends across many orders.
In algorithms, this principle applies everywhere. We sort data to enable binary search. We compute prefix sums to enable O(1) range queries. We build indexes to transform O(n) lookups into O(1). This page will make you a master of recognizing when preprocessing is the right optimization, and how to implement it effectively across a wide range of scenarios.
By the end of this page, you will be able to: • Recognize when preprocessing amortizes computational cost effectively • Implement prefix sums for O(1) range sum queries • Use sorting as preprocessing for binary search patterns • Build lookup tables that eliminate repeated computation • Understand the space-time tradeoff inherent in preprocessing • Apply preprocessing to graphs, strings, and geometric data
Preprocessing transforms the complexity landscape of a problem. It's a strategic decision: accept a one-time cost now to gain repeated benefits later. The decision to preprocess depends on a fundamental equation:
Total Cost Without Preprocessing: Q × query_cost_slow
Total Cost With Preprocessing: preprocess_cost + Q × query_cost_fast
Where Q is the number of queries. Preprocessing is worthwhile when:
preprocess_cost + Q × query_cost_fast < Q × query_cost_slow
Rearranging:
Q > preprocess_cost / (query_cost_slow - query_cost_fast)
This tells us: Preprocessing becomes more valuable as the number of queries increases. A higher preprocessing cost is justified if:
| Scenario | Without Preprocessing | With Preprocessing | Break-Even Point |
|---|---|---|---|
| Range sum queries | O(n) per query | O(n) build + O(1) per query | Profitable after ~2 queries |
| Finding elements by key | O(n) linear scan | O(n) to build hash map + O(1) lookup | Profitable after ~2 queries |
| Binary search on unsorted | O(n) per search | O(n log n) sort + O(log n) per search | Profitable after ~log n queries |
| All-pairs shortest paths | O(V+E) BFS per query | O(V³) Floyd-Warshall + O(1) per query | Profitable after ~V² queries |
Think of preprocessing as amortization—spreading a large cost across many operations. The cost of building a hash map seems high for one lookup. But spread across 10,000 lookups, that one-time O(n) cost becomes negligible compared to the O(n) per lookup you'd pay without it.
The prefix sum (also called cumulative sum or running total) is perhaps the most fundamental preprocessing technique. It transforms O(n) range sum queries into O(1) by precomputing cumulative sums.
The Core Insight:
For an array arr, the prefix sum array prefix is defined as:
Once computed, any range sum from index L to R can be calculated:
This works because prefix[R] contains the sum of all elements from 0 to R, and prefix[L-1] contains the sum of all elements from 0 to L-1. The difference gives exactly sum(L, R).
1234567891011121314151617181920212223242526272829303132333435363738394041
class PrefixSum: """ Preprocess array for O(1) range sum queries. Preprocessing: O(n) time, O(n) space Query: O(1) time """ def __init__(self, arr): """Build prefix sum array in O(n) time.""" n = len(arr) self.prefix = [0] * (n + 1) # Extra element for easier boundary handling for i in range(n): self.prefix[i + 1] = self.prefix[i] + arr[i] def range_sum(self, left, right): """ Return sum of arr[left:right+1] in O(1) time. Uses the identity: sum(L, R) = prefix(R+1) - prefix(L) """ return self.prefix[right + 1] - self.prefix[left] # Example usagearr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]ps = PrefixSum(arr) # Without preprocessing: each range sum takes O(n)# With preprocessing: one O(n) build, then O(1) per query print(ps.range_sum(0, 3)) # 3 + 1 + 4 + 1 = 9print(ps.range_sum(4, 7)) # 5 + 9 + 2 + 6 = 22print(ps.range_sum(2, 2)) # 4 (single element) # For Q queries on array of size n:# Without: O(Q × n)# With: O(n + Q × 1) = O(n + Q)# # If Q = n, this is O(n) vs O(n²) — a massive improvement!2D Prefix Sums:
The prefix sum concept extends beautifully to two dimensions, enabling O(1) submatrix sum queries:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
class PrefixSum2D: """ Preprocess 2D matrix for O(1) submatrix sum queries. Preprocessing: O(m × n) time and space Query: O(1) time Uses inclusion-exclusion principle: sum(r1,c1 to r2,c2) = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] """ def __init__(self, matrix): if not matrix or not matrix[0]: self.prefix = [[0]] return m, n = len(matrix), len(matrix[0]) self.prefix = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): self.prefix[i + 1][j + 1] = ( matrix[i][j] + self.prefix[i][j + 1] # Sum above + self.prefix[i + 1][j] # Sum to left - self.prefix[i][j] # Remove double-counted corner ) def submatrix_sum(self, r1, c1, r2, c2): """ Return sum of submatrix from (r1,c1) to (r2,c2) inclusive. Uses inclusion-exclusion in O(1) time. """ return ( self.prefix[r2 + 1][c2 + 1] - self.prefix[r1][c2 + 1] - self.prefix[r2 + 1][c1] + self.prefix[r1][c1] ) # Practical application: Image processing, game boards, density queriesmatrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]ps2d = PrefixSum2D(matrix) # Sum of entire matrixprint(ps2d.submatrix_sum(0, 0, 2, 3)) # 1+2+...+12 = 78 # Sum of bottom-right 2×2print(ps2d.submatrix_sum(1, 2, 2, 3)) # 7+8+11+12 = 38The prefix technique extends to any associative operation with an inverse: prefix products (using division), prefix XOR (XOR is its own inverse), and more. For operations without inverses (min, max), you need different structures like segment trees or sparse tables.
Sorting is the workhorse preprocessing operation. The O(n log n) investment unlocks a cascade of efficient operations that would be O(n) or worse on unsorted data.
What Sorting Enables:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
from bisect import bisect_left, bisect_right class SortedQueryStructure: """ Preprocesses array with sorting for efficient range and search queries. Preprocessing: O(n log n) sort Queries: O(log n) each """ def __init__(self, arr): self.sorted_arr = sorted(arr) self.n = len(arr) def count_in_range(self, low, high): """ Count elements where low <= element <= high. Without sorting: O(n) scan With sorting: O(log n) using binary search """ left = bisect_left(self.sorted_arr, low) right = bisect_right(self.sorted_arr, high) return right - left def count_less_than(self, value): """Count elements strictly less than value in O(log n).""" return bisect_left(self.sorted_arr, value) def exists(self, value): """Check if value exists in O(log n).""" pos = bisect_left(self.sorted_arr, value) return pos < self.n and self.sorted_arr[pos] == value def kth_smallest(self, k): """Return k-th smallest element in O(1) after preprocessing.""" if 1 <= k <= self.n: return self.sorted_arr[k - 1] return None def closest_to(self, target): """Find element closest to target in O(log n).""" pos = bisect_left(self.sorted_arr, target) if pos == 0: return self.sorted_arr[0] if pos == self.n: return self.sorted_arr[-1] # Compare neighbors before = self.sorted_arr[pos - 1] after = self.sorted_arr[pos] return before if target - before <= after - target else after # Example: Many queries on same datasetdata = [64, 34, 25, 12, 22, 11, 90, 45, 33, 77]sq = SortedQueryStructure(data) # Each query is O(log n) instead of O(n)print(sq.count_in_range(20, 50)) # Count elements between 20 and 50print(sq.kth_smallest(3)) # 3rd smallest elementprint(sq.closest_to(40)) # Element closest to 40print(sq.exists(25)) # Does 25 exist? # For Q queries: O(n log n + Q log n) vs O(Q × n)# Break-even around Q = log n, which is almost always exceededThe Two-Sum Pattern with Sorting:
Sorting enables the classic two-pointer technique that reduces O(n²) pairwise search to O(n):
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
def two_sum_exists(arr, target): """ Check if any two elements sum to target. Naive approach: O(n²) - check all pairs Sorting + two pointers: O(n log n) + O(n) = O(n log n) Hash set approach: O(n) - but sorting enables more operations """ sorted_arr = sorted(arr) # O(n log n) preprocessing left, right = 0, len(sorted_arr) - 1 while left < right: current_sum = sorted_arr[left] + sorted_arr[right] if current_sum == target: return True elif current_sum < target: left += 1 # Need larger sum else: right -= 1 # Need smaller sum return False # The sorting preprocessing enables ADDITIONAL queries: def count_pairs_less_than(arr, limit): """Count pairs with sum < limit. Needs sorted data.""" sorted_arr = sorted(arr) count = 0 left, right = 0, len(sorted_arr) - 1 while left < right: if sorted_arr[left] + sorted_arr[right] < limit: # All pairs from left to right-1 also work count += right - left left += 1 else: right -= 1 return count def closest_pair_to_target(arr, target): """Find pair with sum closest to target. Needs sorted data.""" sorted_arr = sorted(arr) left, right = 0, len(sorted_arr) - 1 best_diff = float('inf') best_pair = None while left < right: current_sum = sorted_arr[left] + sorted_arr[right] diff = abs(current_sum - target) if diff < best_diff: best_diff = diff best_pair = (sorted_arr[left], sorted_arr[right]) if current_sum < target: left += 1 else: right -= 1 return best_pairIf you need to preserve original indices while using sorted order, create an array of (value, index) tuples and sort that. This pattern is essential when the problem requires returning original positions after processing in sorted order.
Lookup tables precompute function results for all possible inputs. When the input domain is finite and small enough, we can trade memory for speed by storing every answer in advance.
When Lookup Tables Are Ideal:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
import math class PopcountLookup: """ Precompute bit count (popcount) for all bytes. Instead of counting bits at runtime, we store the answer for all 256 possible byte values. Build: O(256) = O(1) Query: O(1) per byte """ def __init__(self): # Precompute popcount for all byte values 0-255 self.table = [bin(i).count('1') for i in range(256)] def popcount(self, n): """Count set bits in 32-bit integer using byte lookups.""" return ( self.table[n & 0xFF] + self.table[(n >> 8) & 0xFF] + self.table[(n >> 16) & 0xFF] + self.table[(n >> 24) & 0xFF] ) class FactorialMod: """ Precompute factorials and inverse factorials for combinations. Essential for competitive programming where nCr queries are common. Build: O(n) Query: O(1) per combination """ def __init__(self, max_n, mod=10**9 + 7): self.mod = mod self.fact = [1] * (max_n + 1) self.inv_fact = [1] * (max_n + 1) # Precompute factorials for i in range(1, max_n + 1): self.fact[i] = self.fact[i-1] * i % mod # Precompute inverse factorials using Fermat's little theorem self.inv_fact[max_n] = pow(self.fact[max_n], mod - 2, mod) for i in range(max_n - 1, -1, -1): self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod def nCr(self, n, r): """Return nCr mod p in O(1) time.""" if r < 0 or r > n: return 0 return self.fact[n] * self.inv_fact[r] % self.mod * self.inv_fact[n - r] % self.mod # Example: Computing combinations without preprocessing# Each nCr(n, r) takes O(r) time for multiplication# With preprocessing: O(max_n) once, then O(1) per query comb = FactorialMod(1000) # Precompute up to n=1000print(comb.nCr(100, 50)) # O(1) queryprint(comb.nCr(500, 200)) # O(1) queryPrime Sieve as Preprocessing:
The Sieve of Eratosthenes is a classic example of preprocessing that enables O(1) primality testing:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
class PrimeSieve: """ Precompute prime status for all numbers up to n. Preprocessing: O(n log log n) time, O(n) space Primality check: O(1) List primes: O(π(n)) where π is prime counting function """ def __init__(self, max_n): self.max_n = max_n self.is_prime = [True] * (max_n + 1) self.is_prime[0] = self.is_prime[1] = False # Classic Sieve of Eratosthenes i = 2 while i * i <= max_n: if self.is_prime[i]: # Mark all multiples as composite for j in range(i * i, max_n + 1, i): self.is_prime[j] = False i += 1 # Optionally: collect primes list self.primes = [i for i in range(2, max_n + 1) if self.is_prime[i]] def check_prime(self, n): """O(1) primality check (for n <= max_n).""" if n > self.max_n: raise ValueError(f"n={n} exceeds precomputed range {self.max_n}") return self.is_prime[n] def count_primes_up_to(self, n): """Count primes <= n using binary search on primes list.""" from bisect import bisect_right return bisect_right(self.primes, n) def prime_factorization(self, n): """ Factor n using precomputed primes. Much faster than trial division when primes are known. """ factors = {} for p in self.primes: if p * p > n: break while n % p == 0: factors[p] = factors.get(p, 0) + 1 n //= p if n > 1: factors[n] = 1 return factors # Usage: Problems with many primality checkssieve = PrimeSieve(10**6) # One-time O(n log log n) setup # Now primality checks are O(1)print(sieve.check_prime(999983)) # Trueprint(sieve.check_prime(1000000)) # False # Factor large numbers efficientlyprint(sieve.prime_factorization(123456)) # {2: 6, 3: 1, 643: 1}Lookup tables trade memory for speed. A popcount table for bytes uses 256 bytes—trivial. A prime sieve to 10⁸ uses ~100MB. A factorial table to 10⁶ needs millions of large numbers. Always consider whether the memory cost is acceptable for your environment.
String algorithms frequently benefit from preprocessing. The KMP failure function, Z-array, suffix arrays, and rolling hash all preprocess strings to accelerate pattern matching and substring operations.
Rolling Hash Preprocessing:
Precomputing hash values enables O(1) substring hash queries, which transforms many O(n²) string comparisons into O(n):
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
class RollingHash: """ Precompute polynomial hash for O(1) substring hash queries. Uses: hash(s[i:j]) = (prefix_hash[j] - prefix_hash[i] * pow[j-i]) mod M Preprocessing: O(n) Substring hash query: O(1) Substring equality check: O(1) with high probability """ def __init__(self, s, base=31, mod=10**9 + 9): self.s = s self.n = len(s) self.base = base self.mod = mod # Precompute prefix hashes self.prefix_hash = [0] * (self.n + 1) for i in range(self.n): self.prefix_hash[i + 1] = ( self.prefix_hash[i] * base + ord(s[i]) ) % mod # Precompute powers of base self.pow = [1] * (self.n + 1) for i in range(self.n): self.pow[i + 1] = self.pow[i] * base % mod def get_hash(self, left, right): """ Get hash of s[left:right+1] in O(1). Without preprocessing: O(right - left) to compute each time With preprocessing: O(1) """ length = right - left + 1 return ( self.prefix_hash[right + 1] - self.prefix_hash[left] * self.pow[length] % self.mod + self.mod ) % self.mod def substring_equals(self, l1, r1, l2, r2): """ Check if s[l1:r1+1] == s[l2:r2+1] in O(1) with high probability. Useful for palindrome checking, repeated substring detection, etc. """ if r1 - l1 != r2 - l2: return False return self.get_hash(l1, r1) == self.get_hash(l2, r2) # Example: Count distinct substrings of length kdef count_distinct_substrings(s, k): """O(n) with preprocessing vs O(n × k) without.""" rh = RollingHash(s) hashes = set() for i in range(len(s) - k + 1): h = rh.get_hash(i, i + k - 1) # O(1) per substring hashes.add(h) return len(hashes) # Example: Find longest repeated substringdef longest_repeated_substring(s): """Binary search + rolling hash for O(n log n) solution.""" n = len(s) rh = RollingHash(s) def has_repeat_of_length(length): seen = {} for i in range(n - length + 1): h = rh.get_hash(i, i + length - 1) if h in seen: # Verify to handle hash collision if s[i:i+length] == s[seen[h]:seen[h]+length]: return seen[h] seen[h] = i return -1 # Binary search for longest length left, right = 1, n result = "" while left <= right: mid = (left + right) // 2 pos = has_repeat_of_length(mid) if pos >= 0: result = s[pos:pos + mid] left = mid + 1 else: right = mid - 1 return resultKMP Failure Function:
The Knuth-Morris-Pratt algorithm preprocesses the pattern to enable O(n + m) string matching instead of O(n × m):
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
def compute_failure_function(pattern): """ Precompute KMP failure function (longest proper prefix-suffix). Time: O(m) where m = len(pattern) Space: O(m) failure[i] = length of longest proper prefix of pattern[0:i+1] that is also a suffix of pattern[0:i+1] """ m = len(pattern) failure = [0] * m j = 0 # Length of previous longest prefix suffix i = 1 while i < m: if pattern[i] == pattern[j]: j += 1 failure[i] = j i += 1 elif j > 0: j = failure[j - 1] # Fallback using computed failure values else: failure[i] = 0 i += 1 return failure def kmp_search(text, pattern): """ Find all occurrences of pattern in text. Without preprocessing: O(n × m) naive comparison With KMP preprocessing: O(n + m) The preprocessing of pattern allows skipping characters in text that we know will match, rather than restarting comparison. """ n, m = len(text), len(pattern) if m == 0: return [] # Preprocess pattern - O(m) failure = compute_failure_function(pattern) matches = [] j = 0 # Current position in pattern # Scan text - O(n) for i in range(n): while j > 0 and text[i] != pattern[j]: j = failure[j - 1] # Use preprocessed failure function if text[i] == pattern[j]: j += 1 if j == m: matches.append(i - m + 1) j = failure[j - 1] # Continue searching return matches # The preprocessing investment:# - Failure function computation: O(m) one time# - Enables O(n) text scan instead of O(n × m)# - Essential when searching for same pattern in multiple textsGraphs frequently require preprocessing for efficient traversal queries. Common preprocessing includes computing levels, parent pointers, and specialized structures for Lowest Common Ancestor (LCA) queries.
Level and Parent Preprocessing for LCA:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
from collections import dequeimport math class LCABinaryLifting: """ Preprocess tree for O(log n) LCA queries using binary lifting. Preprocessing: O(n log n) time and space LCA Query: O(log n) Also enables O(log n) k-th ancestor queries and path queries. """ def __init__(self, n, edges, root=0): self.n = n self.log = max(1, n.bit_length()) # ceil(log2(n)) # Build adjacency list self.adj = [[] for _ in range(n)] for u, v in edges: self.adj[u].append(v) self.adj[v].append(u) # Precompute: depth and sparse table for ancestors self.depth = [0] * n self.parent = [[-1] * n for _ in range(self.log)] # BFS to set depths and immediate parents self._preprocess_bfs(root) # Binary lifting: parent[k][v] = 2^k-th ancestor of v self._build_sparse_table() def _preprocess_bfs(self, root): """Compute depths and direct parents via BFS.""" visited = [False] * self.n queue = deque([root]) visited[root] = True self.depth[root] = 0 self.parent[0][root] = root # Root is its own ancestor while queue: u = queue.popleft() for v in self.adj[u]: if not visited[v]: visited[v] = True self.depth[v] = self.depth[u] + 1 self.parent[0][v] = u queue.append(v) def _build_sparse_table(self): """Build sparse table for 2^k ancestors.""" for k in range(1, self.log): for v in range(self.n): if self.parent[k-1][v] != -1: self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]] def kth_ancestor(self, v, k): """Find k-th ancestor of v in O(log k) time.""" for i in range(self.log): if k & (1 << i): v = self.parent[i][v] if v == -1: return -1 return v def lca(self, u, v): """Find lowest common ancestor of u and v in O(log n).""" # Bring to same depth if self.depth[u] < self.depth[v]: u, v = v, u diff = self.depth[u] - self.depth[v] u = self.kth_ancestor(u, diff) if u == v: return u # Binary search for LCA for k in range(self.log - 1, -1, -1): if self.parent[k][u] != self.parent[k][v]: u = self.parent[k][u] v = self.parent[k][v] return self.parent[0][u] def distance(self, u, v): """Tree distance between u and v in O(log n).""" return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)] # Usage: Tree with many LCA/distance queriesedges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]lca_solver = LCABinaryLifting(7, edges, root=0) # O(log n) per query after O(n log n) preprocessingprint(lca_solver.lca(3, 5)) # LCA of nodes 3 and 5print(lca_solver.distance(4, 6)) # Distance between 4 and 6print(lca_solver.kth_ancestor(5, 2)) # 2nd ancestor of node 5All-Pairs Shortest Paths Preprocessing:
When you need distances between many pairs of nodes, Floyd-Warshall preprocesses the entire graph:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
def floyd_warshall(n, edges): """ Precompute all-pairs shortest paths. Preprocessing: O(V³) Query: O(1) Space: O(V²) Worthwhile when: - You need many distance queries - Graph is small enough (V ≤ ~500) - Graph changes rarely """ INF = float('inf') # Initialize distance matrix dist = [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for u, v, w in edges: dist[u][v] = min(dist[u][v], w) dist[v][u] = min(dist[v][u], w) # If undirected # Floyd-Warshall: O(V³) for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist # Now distance queries are O(1)class DistanceOracle: def __init__(self, n, edges): self.dist = floyd_warshall(n, edges) def query(self, u, v): """O(1) distance query after O(V³) preprocessing.""" return self.dist[u][v] def shortest_total_distance(self, sources, destinations): """Sum of distances from multiple sources to destinations.""" total = 0 for src in sources: for dst in destinations: total += self.dist[src][dst] return totalFor sparse graphs with few queries, single-source algorithms (BFS, Dijkstra) per query might be faster than all-pairs preprocessing. Floyd-Warshall's O(V³) preprocessing is only efficient when query count approaches O(V²). For very large graphs, neither approach scales—consider approximate or hierarchical methods.
Preprocessing is powerful but not universally applicable. Recognizing when preprocessing is inappropriate or insufficient is as important as knowing when to use it.
Situations Where Preprocessing Has Limited Value:
Dynamic Scenarios Require Different Approaches:
When data changes, consider data structures that support efficient updates along with queries:
| Query Type | Static (Preprocessing) | Dynamic Structure |
|---|---|---|
| Range sum | Prefix sum: O(n) build, O(1) query, no updates | Segment tree: O(n) build, O(log n) query and update |
| Sorted search | Sorted array: O(n log n) sort, O(log n) search, O(n) insert | Balanced BST: O(log n) for search, insert, and delete |
| Range min/max | Sparse table: O(n log n) build, O(1) query, no updates | Segment tree: O(n) build, O(log n) query and update |
| Connectivity | Precomputed components: O(n) build, O(1) query, full rebuild on edge add | Union-Find: O(α(n)) per operation including updates |
In practice, many systems use hybrid approaches: preprocess a baseline, handle a buffer of updates separately, and periodically merge. This allows preprocessing benefits while tolerating some data changes. Example: Search indexes rebuild nightly but handle same-day changes with a delta structure.
Preprocessing is one of the most versatile optimization techniques. By investing upfront computation, we transform the complexity landscape of many problems, turning expensive repeated operations into trivial lookups.
Key Preprocessing Techniques Mastered:
The Preprocessing Mindset:
Whenever you see repeated computation over static data, ask: "Can I precompute this?" The answer is often yes, and the resulting speedup can be dramatic—from O(n) per query to O(1), from O(n × m) to O(n + m).
What's Next:
The next page explores early termination—recognizing when you can stop computation before processing all data. While preprocessing invests time upfront, early termination saves time by knowing when to quit early.
You now command a powerful arsenal of preprocessing techniques. From simple prefix sums to complex graph structures, you understand how to trade upfront computation for query efficiency. The next page will teach you the complementary skill of early termination—knowing when to stop computing before the normal endpoint.