Advanced Contribution Technique

Quick Revisit
USE WHEN: sum over all subsets/subarrays/paths — flip to per-element contribution instead
INVARIANT: Σ f(S) over structures = Σ contribution(e) over elements (linearity of summation)
TIME: O(n) to O(n log n) depending on structure | SPACE: O(n)
CLASSIC BUG: double-counting when structures overlap — each element's contribution must be exact
PRACTICE: 08-ladder-mixed

Instead of computing $f$ over all structures and summing, compute each element's total contribution across all structures. This reframe turns impossible-looking $O (n \cdot 2^{n})$ sums into elegant $O (n)$ or $O (n \log n)$ formulas.

Difficulty: [Advanced]CF Rating Range: 1700-2300 Prerequisites: Contribution Technique, basic probability/expectation

The Contribution Mindset
Expected Value via Linearity of Expectation
Contribution to Tree Paths
Contribution in Permutations
Sum Over All Subarrays
XOR Contribution: Bit Independence
Common Mistake: Double Counting
Practice Problems

The Contribution Mindset

The intro file covers the basic reframe: instead of

\sum_{structure S} f (S)

compute

\sum_{element e} contribution (e)

where $contribution (e)$ counts how much $e$ adds across all structures $S$ that contain it. This file pushes the technique into harder territory: expected values, trees, permutations, and bitwise operations.

Expected Value via Linearity of Expectation

Linearity of expectation is contribution technique wearing a probability hat.

E [\sum_{i} X_{i}] = \sum_{i} E [X_{i}]

This holds regardless of dependence between the $X_{i}$ . That's the magic. You don't need to enumerate outcomes.

The connection. An indicator variable $X_{i} \in {0, 1}$ records "is element $i$ a member of this random structure?" Linearity says the expected sum is the sum of memberships. That's exactly contribution counting where the "weight of element $i$ " has been replaced by "probability that element $i$ contributes." Deterministic contribution counting and linearity of expectation are the same theorem applied to membership functions of different types — fixed sets in one case, random sets in the other.

Example -- Expected number of fixed points in a random permutation:

Let $X_{i} = 1$ if $π (i) = i$ . Then $E [X_{i}] = 1 / n$ for each $i$ . By linearity:

E [\sum X_{i}] = \sum_{i = 1}^{n} \frac{1}{n} = 1

A random permutation has exactly 1 fixed point on average, regardless of $n$ . No need to enumerate $n!$ permutations.

Example -- Expected number of comparisons in a random quicksort:

Let $X_{i j} = 1$ if elements $i$ and $j$ are ever compared. Elements $i < j$ are compared iff one of them is the first pivot chosen from ${i, i + 1, \dots, j}$ . Probability: $\frac{2}{j - i + 1}$ . Total expected comparisons:

\sum_{i < j} \frac{2}{j - i + 1} = O (n \log n)

Contribution to Tree Paths

Problem: Given a weighted tree on $n$ nodes, compute the sum of distances over all $(\binom{n}{2})$ pairs of nodes.

Brute force: $O (n^{2})$ , running BFS/DFS from every node.

Contribution reframe: Instead of summing over pairs, ask: "How much does edge $(u, v)$ with weight $w$ contribute to the total?"

Edge $(u, v)$ lies on the path between node $a$ and node $b$ iff $a$ is on one side of the edge and $b$ is on the other. If removing edge $(u, v)$ splits the tree into components of size $s$ and $n - s$ :

contribution of edge (u, v) = w \cdot s \cdot (n - s)

Total sum of all pairwise distances:

\sum_{edge (u, v)} w_{u v} \cdot sz [v] \cdot (n - sz [v])

where $sz [v]$ is the subtree size of the child endpoint. One DFS. $O (n)$ .

cpp

long long total = 0;
int sz[200005];

void dfs(int v, int p, vector<vector<pair<int,int>>>& adj, int n) {
    sz[v] = 1;
    for (auto [u, w] : adj[v]) {
        if (u == p) continue;
        dfs(u, v, adj, n);
        sz[v] += sz[u];
        total += (long long)w * sz[u] * (n - sz[u]);
    }
}

Contribution in Permutations

Problem: What is the expected number of inversions in a random permutation of ${1, \dots, n}$ ?

For each pair $(i, j)$ with $i < j$ , define $X_{i j} = 1$ if $π (i) > π (j)$ (an inversion). By symmetry, $P (X_{i j} = 1) = 1 / 2$ -- in a random permutation, each of the two relative orderings is equally likely.

E [inversions] = \sum_{i < j} E [X_{i j}] = (\binom{n}{2}) \cdot \frac{1}{2} = \frac{n (n - 1)}{4}

The contribution lens: each pair contributes $1 / 2$ in expectation. No need to enumerate permutations.

Sum Over All Subarrays

Problem: Given an array $a$ of length $n$ , compute $\sum_{l \leq r} f (a [l . . r])$ for various functions $f$ .

When $f$ = sum

\sum_{l \leq r} \sum_{i = l}^{r} a [i] = \sum_{i = 1}^{n} a [i] \cdot i \cdot (n - i + 1)

Element $a [i]$ appears in all subarrays with $l \leq i \leq r$ . There are $i$ choices for $l$ (from 1 to $i$ ) and $n - i + 1$ choices for $r$ (from $i$ to $n$ ).

When $f$ = min (or max)

For $\sum_{l \leq r} min (a [l . . r])$ : each element $a [i]$ is the minimum of the subarrays where it is the smallest. Use a monotonic stack to find the nearest smaller element to the left ( $L [i]$ ) and right ( $R [i]$ ).

contribution of a [i] = a [i] \cdot (i - L [i]) \cdot (R [i] - i)

This gives an $O (n)$ solution. The monotonic stack preprocessing is the same pattern from Technique Layering (Stack + DP combo).

cpp

// Sum of minimums of all subarrays
long long sum_of_mins(vector<int>& a) {
    int n = a.size();
    vector<int> left(n), right(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] > a[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++)
        ans += (long long)a[i] * (i - left[i]) * (right[i] - i);
    return ans;
}

Note the asymmetric comparison (>= left, > right) to handle duplicate values without double-counting.

XOR Contribution: Bit Independence

Problem: Compute $\sum_{i < j} (a_{i} \oplus a_{j})$ .

XOR operates independently on each bit. For bit $b$ :

Let $c$ = number of elements with bit $b$ set.
The pair $(a_{i}, a_{j})$ contributes $2^{b}$ to the XOR sum iff exactly one of them has bit $b$ set. Count of such pairs: $c \cdot (n - c)$ .

\sum_{i < j} (a_{i} \oplus a_{j}) = \sum_{b = 0}^{29} 2^{b} \cdot c_{b} \cdot (n - c_{b})

$O (30 n)$ total. The contribution reframe turns a pairwise XOR problem into per-bit counting.

cpp

long long xor_pair_sum(vector<int>& a) {
    int n = a.size();
    long long ans = 0;
    for (int b = 0; b < 30; b++) {
        long long c = 0;
        for (int x : a) if (x >> b & 1) c++;
        ans += (1LL << b) * c * (n - c);
    }
    return ans;
}

Avoiding double counting — a checklist

The single biggest failure mode of contribution counting is counting the same outcome twice (or zero times). Before you commit to a formula, walk through these four checks.

Define the structures you're summing over. Subarrays? Subsets? Pairs $(i, j)$ with $i < j$ or all ordered pairs? Tree paths from $u$ to $v$ with $u \neq v$ , or all $(\binom{n}{2})$ unordered pairs? Get this exact in writing.
Define the unit of contribution. Per element? Per edge? Per bit? Per (element, bit) pair? The unit must partition the contribution of each structure with no overlap.
Prove each structure's value is fully decomposed. Pick a single structure $S$ and verify that summing the contributions of its units reconstructs $f (S)$ exactly. If $f (S) \neq \sum_{e \in S} c (e, S)$ , you're missing or duplicating something.
Prove each contribution is counted exactly once across structures. For each unit $e$ , count how many structures it appears in and confirm that count matches the multiplier in your formula. This is where ties typically bite.

The tie-breaker pattern. When the contribution depends on $e$ being the "minimum" or "maximum" of its structure, multiple equal elements qualify simultaneously. The fix is to break the tie with index: declare that the leftmost occurrence wins. In code, that translates into one strict and one non-strict comparison:

cpp

while (!st.empty() && a[st.top()] >= a[i]) st.pop();   // strict on one side
// ...
while (!st.empty() && a[st.top()] >  a[i]) st.pop();   // non-strict on the other

Each subarray now has a unique "winning" index, and no subarray is double-counted.

Practice Problems

Problem	Contribution Flavor	CF Rating
CF 1648B - Integral Array	Counting pairs via contribution per value	1800
CF 817D - Imbalanced Array	Sum of max - min over all subarrays (monotonic stack)	1900
CF 1208E - Let Them Slide	Per-row contribution with sliding window	2200
CF 1110E - Magic Stones	Difference array reframe (contribution of each diff)	1700
CF 1436E - Complicated Computations	MEX contribution per segment	2400
CSES - Sum of All Subsequences	Each element contributes to $2^{n - 1}$ subsequences	Intro

Advanced Contribution Technique ​

Contents ​

The Contribution Mindset ​

Expected Value via Linearity of Expectation ​

Contribution to Tree Paths ​

Contribution in Permutations ​

Sum Over All Subarrays ​

When f = sum ​

When f = min (or max) ​

XOR Contribution: Bit Independence ​

Avoiding double counting — a checklist ​

Practice Problems ​