Competitive Programming Patterns: 15 Essential Techniques

Competitive programming is pattern recognition under pressure. The faster you identify which technique a problem needs, the faster you solve it. This post covers 15 patterns that appear over and over in contests — from Codeforces rounds to ICPC regionals. Each pattern gets a clear explanation, the core idea, and working code.

1. Prefix Sums — The Foundation

A prefix sum array lets you answer “what is the sum of elements from index l to r?” in O(1) after O(n) preprocessing.

def build_prefix(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

arr = [3, 1, 4, 1, 5, 9]
prefix = build_prefix(arr)
print(range_sum(prefix, 1, 4))  # 1 + 4 + 1 + 5 = 11

2D prefix sums extend this to grids. The sum of a sub-rectangle is computed using inclusion-exclusion:

def build_2d_prefix(grid):
    m, n = len(grid), len(grid[0])
    P = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            P[i+1][j+1] = grid[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
    return P

def rect_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Think of a prefix sum as a running total on a receipt. To find the cost of items 3 through 7, take the running total after item 7 and subtract the running total after item 2.

2. Difference Arrays — The Dual of Prefix Sums

While prefix sums answer range queries, difference arrays handle range updates in O(1). Want to add 5 to every element from index l to r?

def range_add(diff, l, r, val):
    diff[l] += val
    if r + 1 < len(diff):
        diff[r + 1] -= val

# After all updates, recover actual values with prefix sum
def recover(diff):
    for i in range(1, len(diff)):
        diff[i] += diff[i - 1]
    return diff

diff = [0] * 6
range_add(diff, 1, 3, 5)   # add 5 to indices 1..3
range_add(diff, 2, 4, 3)   # add 3 to indices 2..4
print(recover(diff))        # [0, 5, 8, 8, 3, 0]

Real-world analogy: bus passengers. At stop 3, 5 people board; at stop 6, they all exit. Instead of updating every stop in between, you record +5 at stop 3 and -5 at stop 6.

3. Coordinate Compression

When values are huge but the count of distinct values is small, compress them into a dense range 0, 1, 2, … This lets you use arrays instead of hash maps.

def compress(arr):
    sorted_unique = sorted(set(arr))
    rank = {v: i for i, v in enumerate(sorted_unique)}
    return [rank[x] for x in arr], sorted_unique

values = [1000000, 3, 999999, 3, 1000000]
compressed, mapping = compress(values)
print(compressed)  # [2, 0, 1, 0, 2]
print(mapping)     # [3, 999999, 1000000]

When to use: any time you need to index into an array by value, but values can be up to 10^9. Common with Fenwick trees, segment trees, and sweep line algorithms.

4. Meet in the Middle

For problems with exponential search spaces, split the input in half, solve each half independently, then combine. This reduces O(2^n) to O(2^(n/2)).

Example — subset sum for large n

Given n numbers (n up to 40), determine if any subset sums to a target.

from itertools import combinations

def meet_in_middle(arr, target):
    n = len(arr)
    mid = n // 2
    left, right = arr[:mid], arr[mid:]

    def all_subset_sums(lst):
        sums = set()
        for r in range(len(lst) + 1):
            for combo in combinations(lst, r):
                sums.add(sum(combo))
        return sums

    left_sums = all_subset_sums(left)
    right_sums = all_subset_sums(right)

    for s in left_sums:
        if (target - s) in right_sums:
            return True
    return False

print(meet_in_middle([1, 2, 3, 4, 5, 6], 15))  # True

Analogy: searching for a combination lock code. Instead of trying all 10^6 combinations, try all 10^3 for the first half and all 10^3 for the second half, then check which pairs match.

5. Square Root Decomposition

Divide an array of size n into blocks of size sqrt(n). Queries and updates that would be O(n) become O(sqrt(n)).

import math

class SqrtDecomp:
    def __init__(self, arr):
        self.arr = arr[:]
        self.n = len(arr)
        self.block = int(math.sqrt(self.n)) + 1
        self.blocks = (self.n + self.block - 1) // self.block
        self.block_sum = [0] * self.blocks
        for i in range(self.n):
            self.block_sum[i // self.block] += arr[i]

    def update(self, i, val):
        self.block_sum[i // self.block] += val - self.arr[i]
        self.arr[i] = val

    def query(self, l, r):
        total = 0
        bl, br = l // self.block, r // self.block
        if bl == br:
            return sum(self.arr[l:r+1])
        # Partial left block
        total += sum(self.arr[l:(bl+1)*self.block])
        # Full blocks
        for b in range(bl + 1, br):
            total += self.block_sum[b]
        # Partial right block
        total += sum(self.arr[br*self.block:r+1])
        return total

Trade-off: sqrt decomposition is simpler to implement than a segment tree but offers weaker guarantees. For contests, it is often “good enough” and faster to code.

6. Sparse Table — O(1) Range Minimum Queries

A sparse table answers range minimum (or maximum) queries in O(1) after O(n log n) preprocessing. It works for any idempotent operation (where applying it twice gives the same result: min(a, a) = a).

import math

class SparseTable:
    def __init__(self, arr):
        n = len(arr)
        k = int(math.log2(n)) + 1 if n > 0 else 1
        self.table = [[0] * n for _ in range(k)]
        self.log = [0] * (n + 1)

        # Precompute logs
        for i in range(2, n + 1):
            self.log[i] = self.log[i // 2] + 1

        # Base case: intervals of length 1
        self.table[0] = arr[:]

        # Build table
        for j in range(1, k):
            for i in range(n - (1 << j) + 1):
                self.table[j][i] = min(
                    self.table[j-1][i],
                    self.table[j-1][i + (1 << (j-1))]
                )

    def query(self, l, r):
        length = r - l + 1
        k = self.log[length]
        return min(self.table[k][l], self.table[k][r - (1 << k) + 1])

st = SparseTable([2, 4, 1, 5, 3, 7, 1, 9])
print(st.query(1, 5))  # 1 (minimum of [4, 1, 5, 3, 7])

table[0]: each element alone         [2] [4] [1] [5] [3]
table[1]: intervals of length 2      [2,4] [1,4] [1,5] [3,5]
table[2]: intervals of length 4      [1,2,4,5] [1,3,4,5]
Query [1,4]: overlap table[2][1] and table[2][1]
Two precomputed intervals whose union is [1..4]

Key insight: for min/max, overlapping intervals do not cause double-counting. Two intervals of length 2^k that together cover [l, r] give the correct answer.

7. Binary Lifting — Lowest Common Ancestor in O(log n)

Binary lifting precomputes the 2^k-th ancestor of every node, enabling you to jump up a tree in O(log n) steps. The primary use case is LCA queries.

import math

class LCA:
    def __init__(self, n, adj, root=0):
        self.LOG = int(math.log2(n)) + 1 if n > 1 else 1
        self.depth = [0] * n
        self.up = [[0] * n for _ in range(self.LOG)]

        # BFS to compute depths and parents
        from collections import deque
        visited = [False] * n
        queue = deque([root])
        visited[root] = True
        self.up[0][root] = root

        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    self.depth[v] = self.depth[u] + 1
                    self.up[0][v] = u
                    queue.append(v)

        # Build binary lifting table
        for k in range(1, self.LOG):
            for v in range(n):
                self.up[k][v] = self.up[k-1][self.up[k-1][v]]

    def lca(self, u, v):
        # Bring to same depth
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        diff = self.depth[u] - self.depth[v]
        for k in range(self.LOG):
            if (diff >> k) & 1:
                u = self.up[k][u]

        if u == v:
            return u

        # Binary lift both
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                u = self.up[k][u]
                v = self.up[k][v]

        return self.up[0][u]

Analogy: instead of climbing stairs one at a time, you have an elevator that can jump 1, 2, 4, 8, … floors. To reach any floor, you combine at most log(n) jumps.

8. Mo’s Algorithm — Offline Range Queries

Mo’s algorithm answers multiple range queries [l, r] efficiently by processing them in a clever order that minimises pointer movement.

Idea: sort queries by (l // sqrt(n), r). Adjacent queries in this order differ by at most O(sqrt(n)) in their endpoints.

import math

def mo_algorithm(arr, queries):
    n = len(arr)
    block = max(1, int(math.sqrt(n)))
    q = len(queries)

    # Sort queries by (l // block, r)
    order = sorted(range(q), key=lambda i: (queries[i][0] // block, queries[i][1]))

    answers = [0] * q
    cur_l, cur_r = 0, -1
    cur_sum = 0

    def add(idx):
        nonlocal cur_sum
        cur_sum += arr[idx]

    def remove(idx):
        nonlocal cur_sum
        cur_sum -= arr[idx]

    for qi in order:
        l, r = queries[qi]
        while cur_r < r:
            cur_r += 1
            add(cur_r)
        while cur_l > l:
            cur_l -= 1
            add(cur_l)
        while cur_r > r:
            remove(cur_r)
            cur_r -= 1
        while cur_l < l:
            remove(cur_l)
            cur_l += 1
        answers[qi] = cur_sum

    return answers

arr = [1, 1, 2, 1, 3, 4, 5, 2, 8]
queries = [(0, 4), (1, 3), (2, 4)]
print(mo_algorithm(arr, queries))  # [8, 4, 6]

Time: O((n + q) * sqrt(n)). Not online (you need all queries upfront), but very general — you can count distinct elements, track frequencies, compute XOR, etc.

9-15. Seven More Patterns (Quick Reference)

9. Small-to-Large Merging (DSU on Tree)

When merging data structures on a tree, always merge the smaller set into the larger one. This guarantees each element is moved at most O(log n) times.

def small_to_large_merge(sets, u, v):
    if len(sets[u]) < len(sets[v]):
        u, v = v, u
    sets[u].update(sets[v])
    return u

10. Sweep Line

Process events sorted by coordinate. Used for interval scheduling, finding intersections, and computing area of union of rectangles.

11. Two Pointers on Sorted Data

Maintain two indices that move in one direction. Sliding window is a special case. Classic: find pairs summing to target, merge sorted arrays, container with most water.

12. Binary Search on Answer

When the answer is monotonic (if x works, then x+1 also works), binary search on the answer value and check feasibility.

def binary_search_answer(lo, hi, is_feasible):
    while lo < hi:
        mid = (lo + hi) // 2
        if is_feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

13. Offline Processing with Sorting

Some problems become trivial if you process queries or events in sorted order rather than the given order. Sort by deadline, by value, by difficulty — whatever makes greedy choices valid.

14. Contribution Counting

Instead of computing the answer directly, count how much each element contributes to the final answer. This often turns an O(n^2) approach into O(n) or O(n log n).

# Example: sum of all subarray minimums
# Instead of checking every subarray, compute for each element
# how many subarrays it is the minimum of.
def sum_subarray_mins(arr):
    n = len(arr)
    left = [0] * n   # distance to previous smaller element
    right = [0] * n  # distance to next smaller or equal element
    stack = []

    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    return sum(arr[i] * left[i] * right[i] for i in range(n))

15. Lazy Propagation

Defer updates in a segment tree until they are actually needed. This supports range updates and range queries in O(log n) each.

Pattern Selection Cheat Sheet

Recap

These 15 patterns form the toolkit that separates competitive programmers from casual coders. The key is not memorising code — it is recognising which pattern fits:

• Prefix sums and difference arrays are the bread and butter of range operations
• Coordinate compression is a preprocessing step that enables other techniques
• Meet in the middle halves the exponent in brute-force search
• Sqrt decomposition and sparse tables are alternatives to segment trees
• Binary lifting makes tree queries logarithmic
• Mo’s algorithm is the offline Swiss army knife for range queries

Practice two or three problems per pattern. Within a few weeks, you will start seeing these shapes in every contest problem.

Next steps

For tree-specific techniques, see Advanced Tree Algorithms. For advanced DP patterns that pair with these techniques, see Advanced DP Patterns.

Questions or feedback? Email codeloomdevv@gmail.com.