DP Optimization: Sliding Window Sums, Monotonic Deques and Fenwick Trees

This is an extension topic beyond most interviews; it pays off when a correct DP has an O(n) inner loop that makes it O(n^2) or O(nW), and the constraints (n around 10^5) demand one less factor. Hard OAs and top-tier rounds like to ask for exactly that last step.

Intuition

Many recurrences look like f[i] = g(i) + best of f[j] over some set of j, where the set is a window of recent indices or "all earlier j with a smaller value". The inner loop recomputes almost the same aggregate for consecutive i. Keep that aggregate in a structure that updates in O(1) or O(log n) instead:

Transition reads	Structure	Cost per step
Sum of f over a sliding window	Running window sum / prefix sums	O(1)
Max or min of f over a sliding window	Monotonic deque	Amortized O(1)
Max or sum over earlier states with smaller values	Fenwick tree over value ranks	O(log n)
The same linear map applied many times	Matrix exponentiation	O(log steps)

Further techniques (convex hull trick, divide-and-conquer or Knuth optimization, slope tricks) exist for special cost functions; they are beyond interview scope.

When to use it in interviews / OAs

• You have a correct O(n * k) DP where each state looks back over the last k states, and n * k is around 10^10.
• The recurrence takes the max/min over a window: "jump at most k steps", "the previous chosen element is at most k positions back".
• The recurrence sums probabilities or counts over a window (drawing a random number from 1 to W, jumping 1 to k steps).
• The recurrence ranges over "earlier elements with a smaller value" (weighted LIS variants).

Pattern 1: sliding window sums

A player starts at 0 and keeps drawing a uniform random integer in [1, W] while their total is below k. What is the probability the final total is at most n? Let p[x] be the probability that the running total ever equals x. Then p[x] = (1/W) * sum of p[y] for y in [x - W, x - 1] with y < k (only totals below k keep drawing). Maintain that sum as a sliding window:

def new21_probability(n: int, k: int, max_pts: int) -> float:
    if k == 0 or n >= k - 1 + max_pts:
        return 1.0  # every possible final total is at most n
    p = [0.0] * (n + 1)  # p[x] = probability that the running total ever equals x
    p[0] = 1.0
    window = 1.0  # sum of p[y] for y in [x - max_pts, x - 1] that are still drawing (y < k)
    for x in range(1, n + 1):
        p[x] = window / max_pts
        if x < k:
            window += p[x]  # x keeps drawing, so it feeds later totals
        if 0 <= x - max_pts < k:
            window -= p[x - max_pts]  # leaves the window for the next x
    return sum(p[k:])

The naive version is O(n * W); this one is O(n).

Pattern 2: monotonic deque for window max/min

From index 0 you may jump forward at most k steps at a time, collecting nums[i] at every landing spot. Maximize the score at the last index: f[i] = nums[i] + max f[j] for j in [i - k, i - 1]. A deque keeps candidate indices whose f values are decreasing: an older index with a smaller-or-equal value can never be the maximum again, so it is popped.

from collections import deque


def max_jump_score(nums: list[int], k: int) -> int:
    n = len(nums)
    f = [0] * n  # f[i] = best score of a path from 0 that lands on i
    f[0] = nums[0]
    dq = deque([0])  # indices with decreasing f; the front is the window maximum
    for i in range(1, n):
        while dq[0] < i - k:  # the front fell out of the window [i - k, i - 1]
            dq.popleft()
        f[i] = nums[i] + f[dq[0]]
        while dq and f[dq[-1]] <= f[i]:  # older and not better: never useful again
            dq.pop()
        dq.append(i)
    return f[-1]

Each index is pushed and popped at most once, so the whole loop is O(n).

The same idea speeds up the bounded knapsack. Split capacities by their remainder r modulo the item weight w: for capacity x*w + r, taking c copies reads old[(x-c)*w + r] + c*v. Writing x' = x - c, this is (old[x'*w + r] - x'*v) + x*v with x' in the window [x - k, x], which is a sliding-window max:

def bounded_knapsack_mq(weights: list[int], values: list[int], counts: list[int], cap: int) -> int:
    f = [0] * (cap + 1)
    for w, v, k in zip(weights, values, counts):
        if w == 0:  # weightless copies never compete for capacity: take all k if they help
            f = [val + k * max(v, 0) for val in f]
            continue
        old = f[:]  # values before this item
        for r in range(min(w, cap + 1)):  # capacities r, r + w, r + 2w, ...
            dq = deque()  # x' with decreasing old[x'*w + r] - x'*v
            x = 0
            while x * w + r <= cap:
                cur = old[x * w + r] - x * v
                while dq and old[dq[-1] * w + r] - dq[-1] * v <= cur:
                    dq.pop()
                dq.append(x)
                while dq[0] < x - k:  # at most k copies: x - x' <= k
                    dq.popleft()
                best = dq[0]
                f[x * w + r] = old[best * w + r] - best * v + x * v
                x += 1
    return f[cap]

This brings the bounded knapsack to O(n * W), independent of the counts.

Pattern 3: Fenwick tree over values

The maximum sum of a strictly increasing subsequence: f[i] = nums[i] + max(0, max f[j]) over j < i with nums[j] < nums[i]. The condition is on values, not positions, so a sliding window does not fit. Compress values to ranks and keep a Fenwick tree of prefix maxima: querying ranks below nums[i] returns the best predecessor in O(log n).

def max_sum_increasing(nums: list[int]) -> int:
    ranks = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}
    tree = [0] * (len(ranks) + 1)  # Fenwick tree of prefix maxima over value ranks
    best = float("-inf")
    for x in nums:
        r = ranks[x]
        q, i = 0, r - 1  # best f among strictly smaller values (0 = start fresh)
        while i > 0:
            q = max(q, tree[i])
            i -= i & -i
        cur = x + q
        best = max(best, cur)
        i = r
        while i < len(tree):
            tree[i] = max(tree[i], cur)
            i += i & -i
    return best

Replace max by + in the tree to count increasing subsequences, or query a value range with a segment tree when the condition is "values within d of each other".

Complexity

Problem	Naive	Optimized
Window sum of probabilities	O(n * W)	O(n)
Jump with window max	O(n * k)	O(n)
Bounded knapsack	O(W * sum of counts)	O(n * W)
Value-conditioned max	O(n^2)	O(n log n)

Common pitfalls

• Window off-by-one: write down the exact range [i - k, i - 1] (or [x - k, x]) and test the boundaries with k = 1.
• Storing values instead of indices in the deque: you need the index to know when an element leaves the window.
• Pushing before the value is final: only push i after f[i] is computed, and pop expired fronts before reading.
• Window sums with modulo: when subtracting the element that leaves, add the modulus back before % in languages where % can be negative.
• Strict vs non-strict conditions in the Fenwick query: strictly smaller values means querying rank r - 1.
• Zero-weight items in the bounded knapsack: grouping capacities by their remainder modulo w is meaningless for w = 0 (the remainder loop would not run at all), so such items are handled separately, as in the code above.

Interview variations

• Jump game with at most k steps, constrained subsequence sum (consecutive chosen indices at most k apart): deque over f.
• Max value of an equation y_i + y_j + |x_i - x_j| with x_j - x_i <= k: deque over y_i - x_i.
• Shortest subarray with sum at least K (with negatives): deque over prefix sums.
• Drawing cards to a threshold, ways to climb with steps 1..k: sliding window sums.
• Longest increasing subsequence where neighbors differ by at most d: segment tree over values.
• Number of increasing subsequences: Fenwick tree with sums.