Cartesian Tree DP

When the Tree Does the Thinking

The real power of the Cartesian Tree shows up when a problem asks you to reason about ALL subarrays and their minimums (or maximums) simultaneously. Instead of iterating over subarrays, you recurse over the tree.

The tree gives you a natural decomposition: every node splits its range into "left part" and "right part," with the node itself as the extremum. You solve the left and right parts independently, then combine at the node. That's tree DP.

Problem: Yet Another Array Counting Problem

This is a Codeforces problem (CF 1748D). Here's the setup:

Given an array A of length N and an integer M, count the number of arrays B of length N with values in [1, M] such that: for every subarray, the position of the maximum in B is the same as the position of the maximum in A.

If there are ties for the maximum, we take the leftmost position. So the "position of the maximum" is well-defined.

At first glance this looks terrifying. You'd need to check every subarray of both A and B and compare their max positions. That's not tractable directly.

The Cartesian Tree Insight

Here's the key observation: saying "every subarray has its maximum at the same position in A and B" is the same as saying A and B have the same max-Cartesian Tree structure.

Why? The Cartesian Tree is completely determined by the relative ordering of elements — specifically, which element is the maximum (or minimum) in each subarray. If two arrays agree on the position of the maximum for every subarray, their Cartesian Trees are identical.

So the problem becomes: count arrays B with values in [1, M] whose max-Cartesian Tree has the same shape as A's.

This is a tree DP problem. Build A's max-Cartesian Tree, then count valid assignments on the tree.

Setting Up the DP

Build the max-Cartesian Tree of A. (Note: this problem uses maximums, so pop elements smaller than the current one.) Each node u covers some contiguous range of the array where u is the position of the maximum.

Define:

dp[u][j] = number of valid arrays for the subtree rooted at u,
           where the value assigned to node u is at most j.

Values range from 1 to M, so j goes from 0 to M.

Base case: dp[u][0] = 0 for all nodes. You can't assign a value of 0 (values start at 1).

The Transition

For a node u with left child L and right child R:

If we assign value exactly j to node u, then:

The left child's subtree must use values in [1, j-1]. (The left child must be strictly less than u to ensure u is the maximum of its range.) The number of ways is dp[L][j-1].
Same for the right child: dp[R][j-1] ways.
These are independent, so multiply them.

The number of ways with node u getting value exactly j is:

dp[L][j-1] * dp[R][j-1]

And dp[u][j] counts all valid arrays where u's value is at most j, so:

dp[u][j] = dp[u][j-1] + dp[L][j-1] * dp[R][j-1]

The first term (dp[u][j-1]) accounts for values 1 through j-1. The second term adds the new possibilities when u's value is exactly j.

If a child doesn't exist (say L = -1), treat dp[L][j] = 1 for all j. An empty subtree has exactly one way to be filled: do nothing.

Leaf Nodes

For a leaf node (no children), the transition simplifies:

dp[u][j] = dp[u][j-1] + 1 * 1 = dp[u][j-1] + 1

So dp[u][j] = j. A leaf can take any value from 1 to j. That makes sense — there are no children to constrain it, just the upper bound from the parent.

Walkthrough: A = [3, 1, 2], M = 4

First, build the max-Cartesian Tree:

Maximum of [3, 1, 2] is 3 at index 0. Root = 0.
Left of 0: empty. Right of 0: [1, 2].
Maximum of [1, 2] is 2 at index 2. Node 2 is right child of 0.
Left of 2: [1] at index 1. Right of 2: empty.

Tree:

  0 (val 3)
    \
    2 (val 2)
    /
  1 (val 1)

Now compute the DP. Process in postorder: 1, 2, 0.

Node 1 (leaf):

j	dp[1][j]
0	0
1	1
2	2
3	3
4	4

Node 2 (left child = 1, right child = none):

dp[2][j] = dp[2][j-1] + dp[1][j-1] * 1

j	dp[1][j-1]	dp[2][j-1]	dp[2][j]
0	-	-	0
1	0	0	0
2	1	0	1
3	2	1	3
4	3	3	6

Node 0 (left child = none, right child = 2):

dp[0][j] = dp[0][j-1] + 1 * dp[2][j-1]

j	dp[2][j-1]	dp[0][j-1]	dp[0][j]
0	-	-	0
1	0	0	0
2	0	0	0
3	1	0	1
4	3	1	4

Answer: dp[0][4] = 4.

Let's verify. We need arrays B of length 3 with values in [1, 4] where the max-positions match A = [3, 1, 2]. In A, the max of the whole array is at index 0, the max of [1, 2] is at index 2, and so on.

So B[0] must be the strict maximum of the array, B[2] > B[1], and all values in [1, 4]. The valid arrays are: [2,1,1] — wait, let me think more carefully. B[0] > B[1] and B[0] > B[2], and B[2] > B[1]. So B[0] > B[2] > B[1].

With values in [1, 4] and strict inequalities: we need three distinct values in decreasing order assigned to positions 0, 2, 1. That's C(4, 3) = 4 ways. Matches!

Cartesian Tree DP — dp table beside each node showing transitions for A=[3,1,2], M=4

Complexity

The DP table has O(N * M) entries. Each entry takes O(1) to compute (one addition, one multiplication). So the total time is O(N * M), which is fast enough for the typical constraints (N, M up to 2 * 10^5 — but wait, N * M could be 4 * 10^10. That's too much).

This part is tricky, so let's break it down. The key observation is that you don't need the full dp[u][j] table for every node. You only need dp[u][j-1] when computing the parent's transition. And the DP values for a leaf are just j, so you don't need to store them explicitly.

The actual implementation uses the fact that each node only needs the dp array of its children. Process in postorder, and once a node's children are done, you can combine them and free the children's arrays. The total work is O(N * M) in the worst case, but the constraints for CF 1748D are N, M up to 2 * 10^5 with the guarantee that the total is manageable (they set it up so that N * M doesn't blow up, or you use a compressed approach).

For the standard version: compute dp[u][j] for all j from 1 to M, bottom-up. Store each node's dp as a vector of size M+1.

The General Pattern

The "Yet Another Array Counting" problem illustrates a broader pattern:

Whenever you need to reason about "for every possible subarray, who is the min/max and what happens in the left/right parts," build the Cartesian Tree and do tree DP.

The tree naturally partitions the problem. Each node's range is split into "stuff to the left of the extremum" and "stuff to the right." The left and right parts are independent (they don't interact except through the node). So you solve them separately and combine.

This pattern shows up in many guises:

Counting arrays with the same Cartesian structure (what we just did)
Assigning weights/costs where the extremum of each range plays a special role
Visibility problems where elements "see" each other based on intervening minimums or maximums
Range decomposition problems where you split at the extremum and recurse

Constellation 3 (JOISC 2020) — The Idea

Here's a harder example to show the pattern's reach. In the Constellation 3 problem, you have a histogram-like structure and need to remove "stars" (marked cells) at minimum cost such that each column's visible region contains at most one star.

The key insight: the visibility of a star is determined by the histogram bars that block it. When you build the Cartesian Tree of the histogram heights, each subtree corresponds to a "valley" — a region bounded by taller bars on each side.

Stars within a subtree can only be seen from within that subtree (the taller bars on each side block the view). So the problem decomposes into independent subproblems, one per subtree.

At each node, you decide: keep the most expensive star in this valley and remove all others in the subtree, or pass some stars up to the parent's decision. This is a tree DP where each node merges the solutions from its left and right subtrees.

The depth of a node in the Cartesian Tree determines how "enclosed" its valley is — deeper nodes are in narrower, more hemmed-in valleys. This connects back to the contribution technique from Chapter 3: the number of subarrays an element dominates is related to its subtree size, and the nesting of valleys is captured by the tree's depth structure.

Depth and Domination

Speaking of depth, here's a useful way to think about what depth means in a Cartesian Tree.

The depth of node i equals the number of elements on the path from i to the root. Each of these ancestors is the minimum of a strictly larger range containing i. So depth counts the number of "nested minimums" above i.

In a sorted array (like [1, 2, 3, 4, 5]), the Cartesian Tree degenerates into a chain — every node is on the right spine, and depth equals index. The root is 1 (the global min), its right child is 2, and so on.

In a random array, the expected depth is O(log N) (the Cartesian Tree of a random permutation is a random binary search tree, which has logarithmic expected height).

When the depth is small, tree DP is fast. When the tree is balanced, subtree sizes halve at each level, and many DP formulations become O(N log N). The worst case is a chain (sorted input), which gives O(N^2) tree DP — but you can often handle this with segment trees or other tricks.

Putting It Together

Here's the recipe for Cartesian Tree DP problems:

Identify the extremum. Is the problem about minimums or maximums of subarrays? That tells you whether to build a min- or max-Cartesian Tree.
Build the tree. O(N), using the monotonic stack construction from Lesson 1.
Define the DP state. What do you need to compute for each subtree? Usually it's some function of the subtree's range and the node's value.
Write the transition. Combine the left and right children's DP values at the node. The node itself contributes its own value as the extremum of the range.
Compute in postorder. Process children before parents, bottom-up.

The Cartesian Tree turns "iterate over all subarrays" into "recurse over a tree," which is almost always more structured and often more efficient.

Try It

The starter code builds a max-Cartesian Tree for the "Yet Another Array Counting" problem. Fill in the DP.

Test with:

3 4
3 1 2

Expected output: 4

Try N = 4, M = 3, A = [2, 4, 1, 3]:

Max-Cartesian Tree: root at index 1 (value 4), left child = 0 (value 2), right subtree = [1, 3] with root at index 3 (value 3), left child = 2 (value 1).
Count arrays B in [1, 3] with the same max-Cartesian structure.
Expected output: 6

Verify by hand if you want the practice.

Problems

Problem	Link	Difficulty
LC 654 — Maximum Binary Tree	leetcode.com/problems/maximum-binary-tree	Medium
LC 998 — Maximum Binary Tree II	leetcode.com/problems/maximum-binary-tree-ii	Medium
LC 768 — Max Chunks To Make Sorted II	leetcode.com/problems/max-chunks-to-make-sorted-ii	Hard