Contribution Technique

Quick Revisit
USE WHEN: "Sum over all pairs/subarrays/subsets"—flip the sum and count each element's contribution
INVARIANT: Total = sum of (element value × number of substructures it participates in)
TIME: O(n) or O(n log n) with sorting/monotone stack | SPACE: O(n)
CLASSIC BUG: Double-counting equal elements in monotone stack—use strict on one side, non-strict on the other
PRACTICE: Practice Ladder

Most "sum over all subarrays/pairs/subsets" problems look like $O (n^{2})$ or worse until you realize you're summing the wrong way. Instead of iterating over every substructure and computing its value, flip the sum: ask how much each individual element contributes to the global total. One pass over elements instead of one pass over exponentially many structures.

Difficulty: Intermediate | CF Rating: 1400–1800 | Prerequisites: Prefix Sums, Sorting, Combinatorics

Intuition
C++ STL Reference
Implementation
Operations Reference
Problem Patterns & Tricks
Contest Cheat Sheet
Gotchas & Debugging
Self-Test
Practice Problems
Further Reading
Rating Progression
Before You Code Checklist
What Would You Do If...?
The Mistake That Teaches
Debug This
What to Solve Next

Intuition

"Compute the sum of $(max - min)$ over all subarrays of $[3, 1, 4, 1, 5]$ ."

Brute force: enumerate all $\frac{n (n + 1)}{2} = 15$ subarrays, compute max and min of each.

text

Subarrays of a = [3, 1, 4, 1, 5]       n = 5

  len 1:  [3]         -> 0     [1]         -> 0
          [4]         -> 0     [1]         -> 0
          [5]         -> 0
  len 2:  [3,1]       -> 2     [1,4]       -> 3
          [4,1]       -> 3     [1,5]       -> 4
  len 3:  [3,1,4]     -> 3     [1,4,1]     -> 3
          [4,1,5]     -> 4
  len 4:  [3,1,4,1]   -> 3     [1,4,1,5]   -> 4
  len 5:  [3,1,4,1,5] -> 4
                                            ------
                        Total:                33

This is $O (n^{2})$ —or $O (n^{3})$ if you recompute max/min from scratch each time. For $n = 10^{5}$ , dead on arrival.

Instead of summing over all subarrays and computing each one, flip the sum: for each element, count how many subarrays it contributes to as max or min.

\sum_{subarrays S} (max S - min S) = \sum_{i} a_{i} \cdot c_{max} (i) - \sum_{i} a_{i} \cdot c_{min} (i)

where $c_{max} (i)$ = number of subarrays where $a_{i}$ is the maximum, and $c_{min} (i)$ = number of subarrays where $a_{i}$ is the minimum.

Computing $c_{max} (i)$ and $c_{min} (i)$ for every $i$ takes $O (n)$ total with a monotone stack.

Visual Walkthrough

text

Array:   [ 3 ,  1 ,  4 ,  1 ,  5 ]
Index:     0    1    2    3    4

--- Contribution as MAXIMUM (element a[2] = 4) ---

  Find nearest element STRICTLY GREATER to the left  -> none, so L = -1
  Find nearest element >= to the right                -> a[4]=5, so R = 4

  Left choices:  start at index 0, 1, or 2     -> (2 - (-1)) = 3
  Right choices: end at index 2 or 3            -> (4 - 2)    = 2

  +-----+-----+-----+-----+-----+
  |  3  |  1  | [4] |  1  |  5  |
  +-----+-----+-----+-----+-----+
    <--- 3 choices ---|--- 2 --->
                      *
                 a[2] is max in 3 * 2 = 6 subarrays

  Contribution to max-sum:  4 * 6 = 24


--- Contribution as MINIMUM (element a[1] = 1) ---

  Find nearest element STRICTLY LESS to the left     -> none, so L = -1
  Find nearest element <= to the right                -> a[3]=1, so R = 3

  Left choices:  start at 0 or 1                -> (1 - (-1)) = 2
  Right choices: end at 1 or 2                  -> (3 - 1)    = 2

  +-----+-----+-----+-----+-----+
  |  3  | [1] |  4  |  1  |  5  |
  +-----+-----+-----+-----+-----+
    <- 2 -|--- 2 --->
           *
      a[1] is min in 2 * 2 = 4 subarrays

  Contribution to min-sum:  1 * 4 = 4


--- Full table ---

  i   a[i]   c_max(i)   c_min(i)   max contrib   min contrib
  0    3        1          1            3              3
  1    1        2          4            2              4
  2    4        6          1           24              4
  3    1        2          6            2              6
  4    5        4          3           20              3
                                      ---            ---
                                       51             20

The hand-trace above illustrates the method; the exact boundary rules (strict vs. non-strict) determine correctness with duplicates—see the Gotchas section.

The Invariant

text

+-------------------------------------------------------------------+
|  CONTRIBUTION DECOMPOSITION                                        |
|                                                                    |
|  Any sum of the form    SUM_{S in F}  f(S)                        |
|  can be rewritten as    SUM_{i=1..n}  contribution(i, F)          |
|                                                                    |
|  where contribution(i, F) measures how element i participates     |
|  across all members S of the family F.                             |
|                                                                    |
|  The technique works whenever the global function f decomposes    |
|  into independent per-element terms.                               |
+-------------------------------------------------------------------+

What the Code Won't Teach You

Every contribution solution is a summation swap. The original sum iterates over structures (subarrays, pairs, subsets); the swapped sum iterates over elements. Switching the order is the mathematical heart of the technique—everything else is bookkeeping:

text

  ORIGINAL sum:                   SWAPPED sum:

    SUM          f(S)               SUM          contribution(i)
   S in F                         i = 1..n

  |F| can be 2^n                  n terms
  or n^2 terms                    (one per element)

Whenever the family $F$ has $O (n^{2})$ or more members, ask: "Can I swap the order and sum over elements instead?"

The hardest part is the contribution formula, not the code. Once you have the formula, the code is usually 10–20 lines. The intellectual challenge is figuring out what each element contributes—which depends on counting how many structures give element $i$ a particular role. For subarray max/min problems, that count requires knowing the nearest dominating element on each side, which is exactly where the monotone stack enters.

text

  Difficulty breakdown:
  +------------------------------------------------+
  | 1. Recognize the pattern       |  *****        |
  | 2. Derive contribution formula |  ********** * |
  | 3. Write the code              |  ***          |
  +------------------------------------------------+
  The formula is the bottleneck, not the code.

Contribution technique + monotone stack is a canonical pairing. When the contribution count depends on "nearest greater" or "nearest smaller" elements, the monotone stack computes all boundaries in $O (n)$ . This pairing solves problems like "sum of subarray minimums," "sum of subarray maximums," and "sum of (max - min) over all subarrays."

Recognition is the bottleneck. The moment you spot one of these triggers, the technique is almost certainly the right frame.

When to Reach for This

Triggers in problem statements:

"Sum over all pairs / subarrays / subsets"
"Expected value of ..." (expectation is a sum—linearity applies)
"For every subsequence / subset, compute $f$ and sum the results"
Constraint $n \leq 10^{5}$ but the family has $O (n^{2})$ or more members

If you see these, ask: "Can I count each element's contribution independently?"

C++ STL Reference

Function / Class	Header	What it does	Complexity
`sort(a.begin(), a.end())`	`<algorithm>`	Sort for pair contribution	$O (n \log n)$
`stack<int>`	`<stack>`	Monotone stack for subarray bounds	$O (n)$ amort.
`accumulate(a.begin(), a.end(), 0LL)`	`<numeric>`	Sum contributions	$O (n)$
`long long`	built-in	Products of counts overflow `int`	--
`map<int,int>` / `unordered_map`	`<map>`	Frequency counting for subset contribution	$O (n)$ / $O (n)$ avg

Implementation

Pattern A—Sum of Absolute Differences over All Pairs

Given $a_{1}, \dots, a_{n}$ , compute $\sum_{i < j} | a_{i} - a_{j} |$ .

Minimal template:

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());

    long long ans = 0, prefix = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i] * i - prefix;
        prefix += a[i];
    }
    cout << ans << "\n";
}

Explained version:

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());

    // After sorting: a[0] <= a[1] <= ... <= a[n-1].
    // For pair (i, j) with i < j:  |a[i] - a[j]| = a[j] - a[i].
    //
    // Flip the sum.  a[j] appears with '+' in j pairs (one for each a[0..j-1]).
    // So:  answer = SUM_j  a[j] * j  -  SUM_j  (a[0] + ... + a[j-1])
    //             = SUM_j  (a[j] * j  -  prefix[j])
    //
    // We maintain a running prefix sum to avoid recomputation.

    long long ans = 0, prefix = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i] * i - prefix;   // a[i] is larger than i elements before it
        prefix += a[i];
    }
    cout << ans << "\n";
}

Pattern B—Sum of (max − min) over All Subarrays

Monotone stack approach— $O (n)$ .

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    // For each element, find how many subarrays it is the max/min of.
    // Use monotone stack to find left and right boundaries.
    // Break ties with strict-on-left, non-strict-on-right (avoids double count).

    auto contribution = [&](auto cmp) -> long long {
        // cmp = less<>()    -->  computes sum-of-max
        // cmp = greater<>() -->  computes sum-of-min
        vector<int> left(n), right(n);
        stack<int> st;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && !cmp(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() && cmp(a[i], a[st.top()]))
                st.pop();
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }

        long long total = 0;
        for (int i = 0; i < n; i++)
            total += a[i] * (long long)(i - left[i]) * (right[i] - i);
        return total;
    };

    long long ans = contribution(less<long long>())
                  - contribution(greater<long long>());
    cout << ans << "\n";
}

Pattern C—Expected Number of Distinct Values (Linearity of Expectation)

Array $a$ of $n$ elements. Each element is chosen independently with probability $\frac{1}{2}$ . Find the expected number of distinct values.

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // E[distinct values] = SUM_{v} P(v appears at least once)
    //                    = SUM_{v} (1 - P(v never chosen))
    //                    = SUM_{v} (1 - (1/2)^count(v))

    map<int, int> freq;
    for (int x : a) freq[x]++;

    double ans = 0;
    for (auto& [val, cnt] : freq)
        ans += 1.0 - pow(0.5, cnt);

    cout << fixed << setprecision(9) << ans << "\n";
}

Operations Reference

Six variants cover almost every contest problem where contribution technique applies. The key tool column shows what makes each one tractable.

Technique Variant	Time	Space	Key Tool
Pair contribution (sorted)	$O (n \log n)$	$O (n)$	Sorting + prefix sum
Subarray max/min contribution	$O (n)$	$O (n)$	Monotone stack
Subset contribution (independent)	$O (n)$	$O (n)$	Linearity of expectation
Subarray sum-of-products	$O (n)$	$O (1)$	Prefix sums
Bit decomposition	$O (n \cdot B)$	$O (1)$	Per-bit counting
Tree edge/path contribution	$O (n)$	$O (n)$	DFS + subtree sizes

Problem Patterns & Tricks

Pair Sum After Sorting

Trigger: "Sum of $f (a_{i}, a_{j})$ over all pairs $i < j$ " where $f$ depends on relative order (difference, absolute difference, product).

Sort first—that fixes the direction of every pair comparison. After sorting, $a_{i}$ is the smaller value in $(n - 1 - i)$ pairs and the larger value in $i$ pairs, giving a clean closed-form coefficient for each element.

cpp

sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < n; i++)
    ans += a[i] * (2LL * i - n + 1);  // net coefficient of a[i]

Practice: CF 1005E1—Median on Segments

Subarray Max/Min via Monotone Stack

Trigger: "Sum of max (or min) over all subarrays."

For each element, find the nearest strictly-dominating element on each side using a monotone stack. The count of subarrays where that element is the max (or min) is simply (left span) × (right span).

Handle equal elements with strict comparison on one side and non-strict on the other—this is what prevents double-counting (see Gotchas).

Practice: CF 817D—Imbalanced Array · LC 907—Sum of Subarray Minimums

Bit-by-Bit Contribution

Trigger: "Sum of $a_{i} \oplus a_{j}$ ", "Sum of $a_{i} & a_{j}$ ", or "Sum of $a_{i} | a_{j}$ " over all pairs.

Decompose each number into bits. For bit $b$ , let $c$ = count of elements with bit $b$ set:

Operation	Pair contribution for bit $b$
XOR	$c \cdot (n - c) \cdot 2^{b}$
AND	$(\binom{c}{2}) \cdot 2^{b}$
OR	$((\binom{n}{2}) - (\binom{n - c}{2})) \cdot 2^{b}$

text

  Bit-by-bit decomposition of XOR for a = [5, 3, 6]:

  Binary:  5 = 101    3 = 011    6 = 110

  bit 0:   1          1          0       c=2, n-c=1
           pairs with XOR bit 0 set: 2 * 1 = 2
  bit 1:   0          1          1       c=2, n-c=1
           pairs with XOR bit 1 set: 2 * 1 = 2
  bit 2:   1          0          1       c=2, n-c=1
           pairs with XOR bit 2 set: 2 * 1 = 2

  Total XOR pair sum = 2*1 + 2*2 + 2*4 = 2 + 4 + 8 = 14

  Verify: (5^3)+(5^6)+(3^6) = 6+3+5 = 14  <-- matches

cpp

long long ans = 0;
for (int b = 0; b < 30; b++) {
    long long c = 0;
    for (int i = 0; i < n; i++)
        if ((a[i] >> b) & 1) c++;
    ans += c * (n - c) * (1LL << b);  // XOR version
}

Practice: CF 1879D—Sum of XOR Functions

Linearity of Expectation

Trigger: "Expected value of ...", "expected number of ...", any probabilistic quantity that is a sum.

$E [X] = \sum_{i} E [X_{i}]$ —works even when $X_{i}$ are dependent. Define indicator random variables, compute each probability separately.

text

Example: E[inversions in a random permutation of n]
  X_{i,j} = 1 if position i > position j (i < j).
  P(X_{i,j} = 1) = 1/2 for any pair.
  E[X] = C(n, 2) * 1/2 = n*(n-1)/4.

Practice: CF 280C—Game on Tree

Position-Weighted Subarray Contribution

Trigger: "Sum of $f$ over all subarrays" where each element's role is determined only by its position.

Element $a_{i}$ (0-indexed) appears in exactly $(i + 1) \cdot (n - i)$ subarrays.

text

  Why (i+1)*(n-i)?

  Array:   [ a0 | a1 | a2 | a3 | a4 ]     n = 5
                        ^
                        i = 2

  Left endpoints:  can start at 0, 1, or 2   --> (i+1) = 3 choices
                   <-------- 3 ---------|
  Right endpoints: can end at 2, 3, or 4     --> (n-i) = 3 choices
                   |-------- 3 -------->

  Total subarrays containing a[2] = 3 * 3 = 9

cpp

long long ans = 0;
for (int i = 0; i < n; i++)
    ans += (long long)a[i] * (i + 1) * (n - i);  // sum of subarray sums

That one-liner computes the sum of all $O (n^{2})$ subarray sums in a single $O (n)$ pass—the contribution perspective at its most direct.

Practice: CSES 2402—Sum of All Substrings

Edge Contribution on Trees

Trigger: "Sum of distances over all pairs", "sum of $f$ over all paths in a tree."

For each edge, let $s$ = subtree size on one side. That edge lies on exactly $s \cdot (n - s)$ simple paths.

text

  Tree with 5 nodes:

       1                Edge (1--2): subtree below = {2,4,5}, s = 3
      / \                 paths crossing = 3 * (5-3) = 6
     2   3              Edge (1--3): subtree below = {3}, s = 1
    / \                   paths crossing = 1 * 4 = 4
   4   5              Edge (2--4): subtree below = {4}, s = 1
                          paths crossing = 1 * 4 = 4
                        Edge (2--5): subtree below = {5}, s = 1
                          paths crossing = 1 * 4 = 4

  Sum-of-distances (all edge weights = 1):
    total = 6 + 4 + 4 + 4 = 18

cpp

long long ans = 0;
auto dfs = [&](auto& self, int u, int par) -> int {
    int sz = 1;
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        int child = self(self, v, u);
        ans += (long long)w * child * (n - child);  // edge contribution
        sz += child;
    }
    return sz;
};
dfs(dfs, 0, -1);

Practice: CF 1092F—Tree Slicing · CSES 1132—Tree Distances I

Contest Cheat Sheet

text

+===================================================================+
|  CONTRIBUTION TECHNIQUE  --  QUICK REFERENCE                       |
+===================================================================+
|                                                                     |
|  CORE:  SUM_{S in F} f(S)  =  SUM_i  contribution(i)              |
|                                                                     |
|  1. Identify the family F  (pairs, subarrays, subsets, paths)      |
|  2. For each element, count appearances / role in F                |
|  3. Multiply value * count, sum everything                         |
|                                                                     |
|  PAIR (sorted):  coeff of a[i] = (2*i - n + 1)       O(n log n)   |
|  SUBARRAY SUM:   a[i] in (i+1)*(n-i) subarrays       O(n)         |
|  SUBARRAY MAX:   monotone stack for boundaries        O(n)         |
|  BIT DECOMP:     c set-bits, pair XOR = c*(n-c)       O(n*B)      |
|  TREE EDGE:      s * (n-s) paths cross each edge      O(n)        |
|  EXPECTED VAL:   E[X] = SUM E[X_i]  (linearity!)      varies      |
|                                                                     |
|  WATCH OUT:                                                         |
|   - long long overflow  (count * count * value)                    |
|   - equal elements in monotone stack  (strict vs non-strict)       |
|   - modular subtraction  ((a - b) % M + M) % M                    |
+===================================================================+

Gotchas & Debugging

Overflow

Two counts multiplied: $(i + 1) \cdot (n - i)$ can reach $\sim 2.5 \times 10^{9}$ for $n = 10^{5}$ . Multiply by $a_{i}$ (up to $10^{9}$ ) and you blow past int. Rule: Cast to long long before the multiplication.

cpp

// BAD:  a[i] * (i + 1) * (n - i)        <-- int overflow
// GOOD: (long long)a[i] * (i + 1) * (n - i)

Equal elements in monotone stack

If you use strict < on both sides to find "subarrays where $a_{i}$ is the max", subarrays whose maximum is achieved by multiple equal elements get counted more than once.

Fix: Use strict comparison on one side, non-strict on the other. For example: left boundary uses >= (pop while top is not strictly greater), right boundary uses > (pop while top is strictly less). This assigns each subarray to exactly one "representative" maximum.

text

  Worked example: equal elements cause double-counting

  a = [2, 2]     subarrays: [2], [2], [2,2]
                  sum of max = 2 + 2 + 2 = 6

  WRONG (strict < on both sides):
    a[0]=2: L=-1, R=2  --> count = 1*2 = 2   contrib = 4
    a[1]=2: L=-1, R=2  --> count = 2*1 = 2   contrib = 4
    Total = 8.  WRONG (should be 6).
    Subarray [2,2] counted TWICE -- once for each 2.

  CORRECT (strict on left, non-strict on right):
    a[0]=2: L=-1, R(>=)=1  --> count = 1*1 = 1   contrib = 2
    a[1]=2: L(<) =-1, R=2  --> count = 2*1 = 2   contrib = 4
    Total = 6.  <-- correct
    Subarray [2,2] assigned to a[1] only.

Off-by-one in boundaries

Left boundary $L$ = index of nearest dominator (or $- 1$ ). Right boundary $R$ = index of nearest dominator (or $n$ ). Number of left starting positions = $i - L$ , not $i - L - 1$ . Number of right ending positions = $R - i$ . Product = $(i - L) \cdot (R - i)$ .

Modular arithmetic

If the answer is modulo $10^{9} + 7$ , you cannot naively compute sum_max - sum_min after applying mod—the difference may go negative.

Fix: ((sum_max - sum_min) % MOD + MOD) % MOD, or track max-sum and min-sum in separate variables and combine at the end.

Forgetting to sort

Pair contribution formulas assume sorted order. Applying the coefficient formula $a_{i} \cdot (2 i - n + 1)$ to an unsorted array produces garbage.

Contribution ≠ Frequency

"Number of subarrays containing $a_{i}$ " $\neq$ "Number of subarrays where $a_{i}$ is the max." Make sure the contribution function matches what the problem asks.

Mental Traps

Trap: "I need to iterate over all pairs/subarrays."

text

  WRONG thinking (O(n^2)):                RIGHT thinking (O(n)):
  +-------------------------+             +-------------------------+
  | for each subarray S:    |             | for each element i:     |
  |   compute f(S)          |             |   count = #subarrays    |
  |   add to total          |             |           containing i  |
  |                         |             |   total += a[i] * count |
  | n^2 subarrays to visit  |             |                         |
  +-------------------------+             | n elements to visit     |
                                          +-------------------------+

Trap: "Contribution is always a[i] x count."

text

  "sum of subarray sums"             "sum of subarray maximums"
  +---------------------------+      +-------------------------------+
  | contribution(i)           |      | contribution(i)               |
  |  = a[i] * (i+1) * (n-i)  |      |  = a[i] * L[i] * R[i]        |
  |                           |      |            ^         ^         |
  | count depends ONLY on     |      | count depends on NEAREST      |
  | position i                |      | GREATER elements on each side |
  +---------------------------+      +-------------------------------+

Trap: "This only works for sums."

text

  +--------------------------------------------------+
  | Operation  | Contribution rule                    |
  |------------|--------------------------------------|
  | SUM        | a[i] * count(i)                      |
  | XOR        | a[i] if count(i) is odd, else 0      |
  | OR         | bit b set iff any element with bit b  |
  |            | appears in at least one structure     |
  +--------------------------------------------------+
  Any LINEAR operation supports contribution counting.

Self-Test

[ ] Derive the formula for "number of subarrays containing index $i$ " in a 0-indexed array of size $n$ , from first principles.
[ ] Explain the contribution technique as an order-of-summation swap—what is the outer sum, what is the inner, and how do you swap them?
[ ] Describe the "sum of subarray minimums" problem setup: what is each element's contribution, what determines the range over which it is the minimum, and what data structure computes those ranges efficiently?
[ ] State why contribution technique works for sums but not for "sum of squares of subarray sums."
[ ] Name the data structure typically paired with contribution technique when the contribution range depends on nearest greater/smaller elements.
[ ] For the pair-sum pattern, explain why sorting is required and what coefficient each sorted element $a_{i}$ receives.
[ ] Compute by hand the sum of (max - min) over all subarrays of [2, 1, 3], using contribution decomposition (not brute force).

Practice Problems

#	Problem	Technique	Rating
1	CSES 2402—Sum of All Substrings	Digit position contribution	~CF 1300
2	CF 817D—Imbalanced Array	Sum of (max−min) via monotone stack	CF 1400
3	CF 1355C—Count Triangles	Sorted pair counting	CF 1500
4	LC 907—Sum of Subarray Minimums	Monotone stack contribution	~CF 1500
5	LC 2104—Sum of Subarray Ranges	Max and min contribution	~CF 1500
6	CF 1879D—Sum of XOR Functions	Bit decomposition	CF 1700
7	AtCoder ABC 140E—Second Sum	Second-max contribution	~CF 1700
8	CF 280C—Game on Tree	Linearity of expectation	CF 2100

Rating Progression

CF 1200: Sum of all subarray sums—each element $a_{i}$ appears in $(i + 1) (n - i)$ subarrays.
CF 1500: Sum of subarray min/max using monotone stack to find each element's contribution range; pair-sum with sorted coefficients.
CF 1800: Bit decomposition + contribution (sum of XOR over all pairs); expected value via linearity of expectation on trees.
CF 2100: Second-order contributions (second max/min in subarrays); contribution on tree paths with Euler tour + LCA.

Before You Code Checklist

[ ] Identified what "answer per subset/subarray" is being summed, and what each individual element contributes to it.
[ ] Derived the closed-form count of how many subsets/subarrays each element participates in (combinatorial coefficient).
[ ] For min/max contributions, identified the correct monotone stack approach to find left/right boundaries.
[ ] Checked for double-counting: does my contribution formula count each pair/subarray exactly once?
[ ] Verified the formula on a small example by hand (brute force $n \leq 4$ ) before coding.

What Would You Do If...?

You need the sum of $gcd$ over all pairs—can you still use contribution technique, and what number-theoretic tool helps count how many pairs have a specific $gcd$ ?
The problem asks for the sum of second-largest elements across all subarrays—how does the contribution boundary change compared to the largest element?
Your contribution formula works for subarrays but the problem asks about subsequences—what changes in the counting?

The Mistake That Teaches

A contestant computed "sum of max over all subarrays" using a monotone stack, but used <= instead of < when finding the right boundary for equal elements. Equal elements were double-counted—both copies claimed ownership of overlapping subarrays—and the total was inflated. Only large tests with duplicate values exposed the bug. The lesson: the strict/non-strict boundary asymmetry is not an implementation detail; it is the invariant that makes the count correct. Use strict < on one side and <= on the other, and every subarray gets assigned to exactly one representative maximum.

Debug This

Bug 1:

cpp

// Sum of all subarray sums
long long total = 0;
for (int i = 0; i < n; i++) {
    total += a[i] * (i + 1) * (n - i + 1);  // Bug here
}

Answer

The right factor should be (n - i), not (n - i + 1). Element a[i] (0-indexed) appears in subarrays starting at any of 0..i and ending at any of i..n-1, giving $(i + 1) \times (n - i)$ subarrays.

Bug 2:

cpp

// Sum of subarray minimums using monotone stack
// left[i] = number of subarrays where a[i] is the min, extending left
// right[i] = ... extending right
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] > a[i]) st.pop();
    left[i] = st.empty() ? i + 1 : i - st.top();
    st.push(i);
}
// Same logic for right[], but also uses '>' for both directions
// Bug: duplicate values are double-counted

Answer

When elements are equal, using > for both left and right boundaries causes overlapping ownership. One direction must use >= (strictly pop on equal) and the other > (keep equal elements on stack), ensuring each subarray's minimum is attributed to exactly one index.

Bug 3:

cpp

// Sum of all pair absolute differences (sorted array)
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < n; i++) {
    ans += a[i] * (2 * i - n);  // Bug: missing cast
}

Answer

a[i] is int and (2*i - n) is int—their product can overflow 32-bit int before being added to the long long result. Cast explicitly: ans += (long long)a[i] * (2 * i - n);. Also verify the coefficient: each sorted $a_{i}$ is added $i$ times (as the larger element) and subtracted $(n - 1 - i)$ times (as the smaller element), giving coefficient $(2 i - n + 1)$ .

A useful mnemonic: "Don't count the answers—count how much each element gives." The underlying principle is linearity of summation (and its probabilistic cousin, linearity of expectation), both classical results that competitive programming borrowed wholesale. The technique gained its modern contest form through Codeforces editorials in the 2010s, particularly for subarray min/max problems solved via monotone stack—but the summation swap is older than algorithms competition itself.

What to Solve Next

Divide and Conquer—the next core technique; merge-sort-based counting is a natural partner to contribution.
Greedy—when contributions reveal a clear ordering, a greedy approach often follows.
Practice Ladder—drill contribution problems by rating.

Contribution Technique ​

Contents ​

Intuition ​

Visual Walkthrough ​

The Invariant ​

What the Code Won't Teach You ​

When to Reach for This ​

C++ STL Reference ​

Implementation ​

Pattern A—Sum of Absolute Differences over All Pairs ​

Pattern B—Sum of (max − min) over All Subarrays ​

Pattern C—Expected Number of Distinct Values (Linearity of Expectation) ​

Operations Reference ​

Problem Patterns & Tricks ​

Pair Sum After Sorting ​

Subarray Max/Min via Monotone Stack ​

Bit-by-Bit Contribution ​

Linearity of Expectation ​

Position-Weighted Subarray Contribution ​

Edge Contribution on Trees ​

Contest Cheat Sheet ​

Gotchas & Debugging ​

Overflow ​

Equal elements in monotone stack ​

Off-by-one in boundaries ​

Modular arithmetic ​

Forgetting to sort ​

Contribution ≠ Frequency ​

Mental Traps ​

Self-Test ​

Practice Problems ​

Further Reading ​

Rating Progression ​

Before You Code Checklist ​

What Would You Do If...? ​

The Mistake That Teaches ​

Debug This ​

What to Solve Next ​

Contribution Technique

Contents

Intuition

Visual Walkthrough

The Invariant

What the Code Won't Teach You

When to Reach for This

C++ STL Reference

Implementation

Pattern A—Sum of Absolute Differences over All Pairs

Pattern B—Sum of (max − min) over All Subarrays

Pattern C—Expected Number of Distinct Values (Linearity of Expectation)

Operations Reference

Problem Patterns & Tricks

Pair Sum After Sorting

Subarray Max/Min via Monotone Stack

Bit-by-Bit Contribution

Linearity of Expectation

Position-Weighted Subarray Contribution

Edge Contribution on Trees

Contest Cheat Sheet

Gotchas & Debugging

Overflow

Equal elements in monotone stack

Off-by-one in boundaries

Modular arithmetic

Forgetting to sort

Contribution ≠ Frequency

Mental Traps

Self-Test

Practice Problems

Further Reading

Rating Progression

Before You Code Checklist

What Would You Do If...?

The Mistake That Teaches

Debug This

What to Solve Next