Use the same tree with \(\lambda=2\). Increase only the leaf cost at \(a_0\) from two to three. The exact subtree values change at \(a_0\), its parent \(a\), and the root \(r\). Every value in the \(b\) subtree remains untouched.
Reading the drawing
The upper row shows old node costs and the lower row the new costs. Only the named leaf, its parent and the root change. The other displayed node values are reused.
Drawing labels and data 22 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
- \(a0\)
- 2
- 3
- \(a1\)
- 2
- 2
- \(a\)
- 4
- 5
- \(b0\)
- 2
- 2
- \(b1\)
- 3
- 3
- \(b\)
- 5
- 5
- \(r\)
- 10
- 11
Top: old values. Bottom: new values. Only a0, a, and r change.
Why the update is local
A dynamic-programming value depends only on the local keep/split data and its children's values. A changed leaf can therefore affect its ancestors but not a disjoint sibling subtree. Recomputing the dependency closure yields the same global optimum as a fresh traversal. In this example, the root value increases from ten to eleven.
Strict gaps protect decisions
Before the update, the root keep score is 13 and its split score is 10, giving gap three. If each score changes by less than \(3/2\), their strict ordering is retained. Allowing exactly \(3/2\) in both directions can produce a tie, so the strict inequality in the stability statement matters.
The bound applies to the completed scores after child subproblems have been evaluated. Bounds on raw leaf perturbations must first be propagated to those scores. Shared caches, overlapping subproblems, or global rank constraints can introduce dependencies outside a tree and invalidate this simple locality argument.
Read this as
Local recompilation is exact because the model has local dependencies. The locality is a mathematical hypothesis, not an automatic property of every compiler optimization.