The Golden Rules of Function Addition: When Shapes Survive

In mathematics and algorithm design—particularly in areas like optimization, dynamic programming, and computational geometry—knowing the "shape" of a function is crucial. Is it shaped like a bowl (convex)? Is it shaped like a hill (concave)? Is it constantly rising (monotonic increasing)?

When dealing with complex problems, we often have to combine simpler functions through addition. The critical question becomes: If I add two functions with known properties, does the resulting function keep those properties?

Knowing the answers can be the difference between a slow \(O(N^2)\) algorithm and a lightning-fast \(O(N)\) or \(O(N \log N)\) solution.

Part 1: The Theory (Thumb Rules)

Since we must distinguish between Curve (continuous) and Discrete, it is helpful to look at this through the lens of Difference Arrays (slopes). In discrete math/algorithms, the shape of the function is defined by how the "slope" changes.

1. Vertical Addition (Point-wise)

This applies when you are adding the values of two functions at the same index: \(H(x) = F(x) + G(x)\).

The Golden Rule: You can add "like" to "like".

Function F	Function G	Result (F + G)	Why?
Convex (\(\cup\))	Convex (\(\cup\))	Convex	Sum of increasing slopes is still increasing.
Concave (\(\cap\))	Concave (\(\cap\))	Concave	Sum of decreasing slopes is still decreasing.
Increasing	Increasing	Increasing	Positive slope + Positive slope = Positive.
Decreasing	Decreasing	Decreasing	Negative slope + Negative slope = Negative.
Linear	Convex	Convex	Tilting a cup doesn't stop it from being a cup.
Linear	Concave	Concave	Tilting a hill doesn't stop it from being a hill.

Note on "Discrete": Strictly speaking, discrete functions follow these rules if the domain is contiguous (like array indices \(0, 1, 2...\)). If \(F\) has increasing differences (convex) and \(G\) has increasing differences, \(F+G\) must have increasing differences. Exceptions happen if your domain has gaps or if you are doing modulo arithmetic.

2. Horizontal Addition (Convolution / Merging)

This applies specifically to algorithm problems (like Knapsack or Resource Allocation) where you are splitting a budget between two functions.

Operation: \(H(k) = \max_{0 \le i \le k} (F(i) + G(k-i))\) This is often called the \((\max, +)\) Convolution.

Function F	Function G	Optimization Goal	Resulting H	Complexity Benefit
Concave	Concave	Maximize	Concave	You can merge them in \(O(N)\) using two pointers or the "SMAWK" property.
Convex	Convex	Minimize	Convex	You can merge them in \(O(N)\). This is the basis of the Slope Trick.
Convex	Concave	Any	Unknown	No guarantee. You usually need \(O(N^2)\) or WQS Binary Search if applicable.

3. Special Cases & Summary

Linear is Neutral: A linear function (straight line) is both Convex and Concave. You can add it to anything without changing the original shape (it just rotates/shears the graph).
Negation Flips: If \(F(x)\) is Convex, then \(-F(x)\) is Concave.
- Rule: Maximize Convex \(\leftrightarrow\) Minimize Concave.
The "V" Shape: A function like \(|x|\) is Convex. Adding two \(|x|\) style functions results in a function that is still Convex (it will look like a polygon bowl).

Cheat Sheet: 1. Convex + Convex = Convex (Safe for Min-Cost flows, Slope Trick). 2. Concave + Concave = Concave (Safe for Knapsack optimizations, D&C optimization). 3. Linear functions never break the convexity/concavity of what they are added to. 4. Monotonicity is only preserved if both functions go in the same direction.

Part 2: Applied Sorcery – The 12 Optimizations

Here is where you actually use these rules to crush time limits in competitive programming.

1. Slope Trick (The "Convex + Convex" Masterpiece)

The Rule: Convex + Convex = Convex.
The Scenario: You have a DP that looks like \(dp[i] = \min ( dp[i-1] + \text{cost}(x) )\).
The Shape: If \(dp[i-1]\) is convex and your cost function (like \(|x - a_i|\)) is convex, the result is convex.
The Magic: Instead of storing the array of DP values (which is slow), you only store the points where the slope changes (using a Priority Queue). Because the sum is still convex, we can simply "push" new slope change points into our heap.
Complexity: Reduces \(O(N^2)\) to \(O(N \log N)\).

2. WQS Binary Search (Alien's Trick)

The Rule: Linear + Concave = Concave.
The Scenario: "Choose exactly \(k\) items to maximize profit," but the DP state \(dp[i][k]\) is too slow.
The Shape: The function of "max profit vs \(k\) items" is often Concave.
The Magic: We "tilt" the function by adding a linear penalty cost \(\lambda \cdot k\). Since Linear + Concave = Concave, the structural property doesn't break; it just shifts the peak. We binary search for the \(\lambda\) that makes the peak appear exactly at \(k\).
Complexity: Reduces \(O(NK)\) to \(O(N \log (\text{Range}))\).

3. Convex Hull Trick (CHT) & Li Chao Tree

The Rule: The minimum of a set of Linear functions forms a Convex Hull.
The Scenario: \(dp[i] = \min_{j < i} (dp[j] + b[j] \cdot a[i])\). This is basically adding a bunch of lines \(y = mx + c\).
The Shape: The lower envelope (minimum) of a set of lines always forms a Convex shape.
The Magic: Since we know the boundary is convex, we don't need to check all lines. We can use binary search (or a deque if sorted) to find the optimal line immediately.
Complexity: Reduces \(O(N^2)\) to \(O(N \log N)\) or \(O(N)\).

4. Divide and Conquer Optimization

The Rule: Concavity (Monge Property) implies Monotonic Decisions.
The Scenario: Partitioning an array into \(k\) subarrays to minimize cost: \(dp[i][k] = \min_{j < i} (dp[j][k-1] + Cost(j, i))\).
The Shape: If the \(Cost(j, i)\) matrix satisfies the Quadrangle Inequality (a form of concavity), the optimal splitting point for \(dp[i]\) moves monotonically to the right.
The Magic: We don't need to search all \(j\) for every \(i\). We only search between the bounds defined by the previous answers.
Complexity: Reduces \(O(N^2 k)\) to \(O(Nk)\).

5. The Distance Transform (Parabolic Envelope)

The Rule: The lower envelope of uniform parabolas is computable in linear time.
The Scenario: You have a DP relation involving a squared term: \(dp[i] = \min_{j < i} (dp[j] + (i-j)^2)\).
The Shape: The function \((i-j)^2\) is convex. When you "add" these shifted parabolas together, the "lower envelope" maintains a structure that allows for monotonic optimization.
The Magic: We maintain the "active" parabolas in a deque. Since parabolas intersect at most once, we can discard "overshadowed" parabolas efficiently.
Complexity: Reduces \(O(N^2)\) to \(O(N)\).

6. Min-Cost Max-Flow (MCMF)

The Rule: The cost vs. flow function is Convex.
The Scenario: You want to send \(K\) units of flow at the minimum cost.
The Intuition: You always use the cheapest edge available first. Once that saturates, you use the next cheapest. This means the "marginal cost" (slope) to send the next unit is always non-decreasing.
The Magic: Because of this convexity, we don't need complex global optimizations. We can simply repeatedly find the shortest path (Dijkstra/SPFA) in the residual graph to push the next unit of flow. The "greedy" path is the optimal path.

7. Knuth Optimization (Interval DP)

The Rule: Quadrangle Inequality on Intervals implies bounded decision points.
The Scenario: Merging intervals (e.g., Matrix Chain Multiplication): \(dp[i][j] = \min_{k} (dp[i][k] + dp[k][j]) + Cost(i, j)\).
The Shape: If \(Cost(i, j)\) satisfies the Quadrangle Inequality (2D concavity), then the optimal split point \(opt[i][j]\) is "sandwiched" between the optimal points of its sub-intervals: \(opt[i][j-1] \le opt[i][j] \le opt[i+1][j]\).
Complexity: Reduces \(O(N^3)\) to \(O(N^2)\).

8. Ternary Search

The Rule: Convex/Concave functions are Unimodal (one peak/valley).
The Scenario: You have a function \(F(x)\) that is expensive to compute, and you need the optimum.
The Magic: If you have proven (using the sum rules) that your function is a sum of Convex functions, you don't need calculus. You can simply run Ternary Search to find the minimum. This is often used inside WQS Binary Search.

9. SMAWK Algorithm

The Rule: Total Monotonicity (Matrix Concavity).
The Scenario: Finding the minimum value in every row of a large, implicitly defined matrix.
The Shape: If the matrix is "totally monotone" (meaning the position of the minimum value moves to the right as you go down rows), you can delete rows/columns that can never contain a minimum.
The Magic: This is a more aggressive version of D&C Optimization that can solve the problem in strict linear time.
Complexity: Reduces \(O(N \log N)\) to \(O(N)\).

10. Submodularity (Min-Cut Project Selection)

The Rule: Diminishing Returns (Discrete Concavity).
The Scenario: "Project Selection" problems where you choose a subset of items to maximize profit minus cost.
The Intuition: Adding an element to a smaller set adds more value than adding it to a larger set (\(f(A) + f(B) \ge f(A \cup B) + f(A \cap B)\)).
The Magic: Because the profit structure follows "diminishing returns" (submodularity), these problems map perfectly to Min-Cut/Max-Flow. If the structure were Convex (Supermodular), it would be NP-Hard (Max-Cut).

11. Monotonic Queue Optimization (Sliding Window)

The Rule: "Newer and Larger" dominates "Older and Smaller".
The Scenario: \(dp[i] = \max_{i-k \le j < i} (dp[j] + \text{val}[j]) + \text{current}[i]\).
The Shape: The "candidate" elements in the deque always form a strictly decreasing sequence.
The Magic: Since we only want the max, if a new value is larger than the back of the deque, the back is useless (it's smaller AND older). We pop it. The deque remains strictly monotonic, allowing \(O(1)\) query.
Complexity: Reduces \(O(N^2)\) to \(O(N)\).

12. Ternary Huffman (Two-Queue Merge)

The Rule: Increasing + Increasing = Increasing.
The Scenario: Merging sorted weights to form a Huffman tree.
The Magic: Instead of using one Priority Queue (\(O(N \log N)\)), we use two Queues (one for original weights, one for created sums). When you sum the two smallest weights, the result is naturally larger than what you just popped but smaller than what's coming later. The second queue stays monotonic naturally.
Complexity: Reduces \(O(N \log N)\) to \(O(N)\).