Preprocessing Data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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 usage
arr = [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 = 9
print(ps.range_sum(4, 7))  # 5 + 9 + 2 + 6 = 22
print(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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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 queries
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]
ps2d = PrefixSum2D(matrix)
 
# Sum of entire matrix
print(ps2d.submatrix_sum(0, 0, 2, 3))  # 1+2+...+12 = 78
 
# Sum of bottom-right 2×2
print(ps2d.submatrix_sum(1, 2, 2, 3))  # 7+8+11+12 = 38

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

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 dataset
data = [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 50
print(sq.kth_smallest(3))          # 3rd smallest element
print(sq.closest_to(40))           # Element closest to 40
print(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 exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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_pair

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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=1000
print(comb.nCr(100, 50))   # O(1) query
print(comb.nCr(500, 200))  # O(1) query

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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 checks
sieve = PrimeSieve(10**6)  # One-time O(n log log n) setup
 
# Now primality checks are O(1)
print(sieve.check_prime(999983))   # True
print(sieve.check_prime(1000000))  # False
 
# Factor large numbers efficiently
print(sieve.prime_factorization(123456))  # {2: 6, 3: 1, 643: 1}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

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 k
def 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 substring
def 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 result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

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 texts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

from collections import deque
import 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 queries
edges = [(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) preprocessing
print(lca_solver.lca(3, 5))       # LCA of nodes 3 and 5
print(lca_solver.distance(4, 6))  # Distance between 4 and 6
print(lca_solver.kth_ancestor(5, 2))  # 2nd ancestor of node 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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 total