Sum Over Subsets (SOS DP): Yates’ Algorithm & High-Dimensional Prefix Sums in O(N 2^N)

1. The Problem Formulation & Asymptotic Complexity Tiers

Given an array A of length 2^N, the objective is to compute for every integer mask ∈ [0, 2^N - 1] the sum:

Consider the scaling across different algorithmic approaches for N = 20:

• Naive Iteration (O(4^N)): 4^{20} ≈ 1.09 × 10^{12} operations (takes days).
• Bitwise Submask Enumeration (O(3^N)): 3^{20} ≈ 3.48 × 10^9 operations (several seconds, TLE).
• Yates' Algorithm SOS DP (O(N 2^N)): 20 × 2^{20} = 20 × 1,048,576 ≈ 2.09 × 10^7 operations (under 30ms!).

2. Hypercube Geometry & Multidimensional Prefix Sums

To comprehend Yates' Algorithm, consider an N-dimensional space where each axis has length 2 (coordinates {0, 1}). A subset mask is a single point (b_0, b_1, ..., b_{N-1}) on this unit hypercube.

In 2D grid DP, computing a 2D prefix sum sum[x][y] = ∑_{i ≤ x, j ≤ y} A[i][j] is accomplished by:

1. First sweeping along all rows (1D prefix sum on dimension 0).
2. Then sweeping along all columns (1D prefix sum on dimension 1).

Yates' Insight: An N-dimensional prefix sum over an N-dimensional hypercube is simply computed by sweeping each dimension i ∈ [0, N - 1] sequentially!

3. In-Place SOS DP Implementation (Yates' Algorithm)

// SOS DP: O(N * 2^N) Time, O(2^N) Memory
vector<int> computeSOS(int N, const vector<int>& A) {
    int totalMasks = 1 << N;
    vector<int> F = A; // Initialize with base array

    // Sweep through each dimension i
    for (int i = 0; i < N; ++i) {
        for (int mask = 0; mask < totalMasks; ++mask) {
            if (mask & (1 << i)) {
                // If i-th bit is set, accumulate submask with i-th bit cleared
                F[mask] += F[mask ^ (1 << i)];
            }
        }
    }
    return F;
}

The outer loop iterates over the N bit dimensions. The inner loop visits all 2^N masks. If bit i is 1, the value of the submask lacking bit i is added into F[mask] in-place.

4. Dual Variant: Sum Over Supersets

When queries require summing over all supersets F[mask] = ∑_{mask ⊆ super} A[super], the condition is inverted:

If bit i is 0, the superset with bit i enabled propagates its aggregate downward.

5. Fast Walsh-Hadamard Transform (FWHT) & Algebraic Convolutions

Sum Over Subsets is fundamentally linked to the Fast Walsh-Hadamard Transform (FWHT). In polynomial algebra, multiplying two polynomials is accelerated from O(N^2) to O(N log N) via FFT. Similarly, computing the bitwise OR convolution of two arrays C[k] = ∑_{i | j = k} A[i] × B[j] is accelerated via SOS DP:

1. Forward Transform: Apply Yates' SOS DP to compute subset prefix sums A_hat = SOS(A) and B_hat = SOS(B) in O(N 2^N) time.
2. Pointwise Multiplication: Compute C_hat[mask] = A_hat[mask] × B_hat[mask] in O(2^N) time.
3. Inverse Transform: Apply inverse SOS DP (subtracting rather than adding bit contributions) to invert the prefix sums, recovering the exact pointwise convolution array C in O(N 2^N) time.

6. Problem Blueprint: Counting Orthogonal Disjoint Pairs

A classic algorithmic challenge asks: given an array of integers A, count the number of pairs (i, j) such that A[i] & A[j] == 0 (the bitwise AND is zero).

The algebraic insight is that A[i] & A[j] == 0 is logically equivalent to saying that A[j] is a submask of the bitwise complement of A[i]:

By populating a frequency array of occurrences and executing a single SOS DP pass, the number of orthogonal pairs for each element A[i] is retrieved in constant time O(1) by querying F[complement], reducing an O(M^2) quadratic scan to strictly O(N 2^N + M).

7. Engineering Invariants & Bitwise Cache Patterns

• Loop Nesting & Hardware Spatial Locality: In Yates' algorithm, the loop over dimensions i must strictly be the outer loop, with the mask iteration as the inner loop. Swapping the loop order invalidates the prefix accumulation semantics and destroys CPU cache prefetching.
• Bitwise Word Length Limits: N = 22 yields 2^{22} = 4,194,304 integers (~16MB of RAM), which fits comfortably within CPU L3 cache. However, N > 25 exceeds 33 million states (134MB+), introducing significant memory bus bandwidth saturation and page faults.

8. Algorithmic Complexity Comparison Matrix