Proofs: Range min-max tree

Correctness of the range min-max tree searches full

This proof shows: correctness.

Let $E$ be the excess of $P$, with $E(-1) = 0$. For a tree node $v$ with range $[s, t]$, the stored values are $e(v) = E(t) - E(s-1)$, $m(v) = \min_{s \le k \le t} (E(k) - E(s-1))$ and $M(v) = \max_{s \le k \le t} (E(k) - E(s-1))$; padding leaves have empty ranges, $m = +\infty$ and $M = -\infty$.

Lemma 1 (the build). If $v$ has children $\ell$ over $[s, q]$ and $r$ over $[q+1, t]$, then $e(v) = e(\ell) + e(r)$, $m(v) = \min(m(\ell), e(\ell) + m(r))$ and $M(v) = \max(M(\ell), e(\ell) + M(r))$. For $k$ in $[q+1, t]$, $E(k) - E(s-1) = (E(q) - E(s-1)) + (E(k) - E(q)) = e(\ell) + (E(k) - E(q))$, so the minimum over the right half, relative to $E(s-1)$, is $e(\ell) + m(r)$; the rest is immediate. Padding values are neutral for $\min$ and $\max$.

Lemma 2 (discrete continuity). Let $c = E(s-1)$. An integer $x$ equals $E(k)$ for some $k$ in $[s, t]$ if and only if $c + m(v) \le x \le c + M(v)$. Necessity is the definition of $m$ and $M$. For sufficiency, the values $E(s), \ldots, E(t)$ change by exactly $\pm 1$ from one to the next, and they include $c + m(v)$ and $c + M(v)$; the walk between these two indices passes through every integer between them.

FWDSEARCH. Let $t^* = E(i) + d$ and let $k_0$ be the block of $i$. Line L2 checks every position after $i$ in block $k_0$, in order, so it returns the first occurrence if it lies there.

Otherwise, consider the climb. Let $v_0$ be the leaf of $k_0$ and $v_1, v_2, \ldots$ its ancestors. Claim: at the start of each iteration with current node $v$, (a) $c = E(\text{end of the range of } v)$, and (b) no position after $i$ and up to the end of the range of $v$ has excess $t^*$. Initially $c$ is set to the excess at the end of block $k_0$, and (b) is what line L2 established. If $v$ is a right child, the range of its parent ends where the range of $v$ ends, so moving up keeps (a) and (b). If $v$ is a left child with right sibling $u$, the range of $u$ starts right after the range of $v$, so $c$ is the excess just before $u$. By Lemma 2, $u$ contains a position with excess $t^*$ if and only if the test of line L5 succeeds. If it does, every position from after $i$ to the end of $v$ is excluded by (b), so the first occurrence after $i$ lies in $u$, and DESCEND is called with the correct $c$. If it does not, the range of the parent ends where $u$ ends, line L6 adds $e(u)$ to make $c$ the excess there, and (b) extends to the range of the parent. If the root is reached, (b) covers all of $P$ after $i$, so there is no occurrence, and line L8 returns none.

DESCEND. Claim: at each step, $c$ is the excess just before the range of $v$, and the first occurrence of $t^*$ in the range of the node first passed to DESCEND lies in the range of $v$. Initially this holds by the above. At an internal $v$ with children $\ell$ and $r$, Lemma 2 tells whether $\ell$ contains an occurrence; if it does, the first occurrence in $v$ is in $\ell$, which starts with the same $c$. If not, it is in $r$, and $c + e(\ell)$ is the excess just before $r$. At a leaf, line L12 scans in order and returns the first occurrence, which exists by the claim.

BWDSEARCH. The mirror argument: scanning the block of $i$ leftward finds the last occurrence before $i$ there; on the climb, $c$ is the excess at the end of the stretch to the left of what has been excluded, the left sibling $u$ starts with excess $c - e(u)$, and by Lemma 2 the test $c - e(u) + m(u) \le t^* \le c - e(u) + M(u)$ decides whether $u$ contains an occurrence; the descent prefers right children and scans the leaf from its end, keeping $c$ equal to the excess at the end of the current range. If the root is reached with no occurrence in $[0, i-1]$, the only remaining candidate is the virtual position $-1$, whose excess is 0.

FINDCLOSE, FINDOPEN, ENCLOSE. For an opening parenthesis at $i$, every position strictly inside its pair has excess at least $E(i)$, and its matching close is the first position after $i$ with excess $E(i) - 1$, which is $\text{fwdsearch}(i, -1)$. For a closing parenthesis at $j$ with match $i$, $E(i - 1) = E(j)$ and every $k$ with $i \le k < j$ has $E(k) > E(j)$, so $i - 1 = \text{bwdsearch}(j, 0)$. For an opening parenthesis at $i$ with $E(i) = h \ge 2$, the enclosing pair opens at the greatest $k < i$ with $E(k) = h - 1$ and $P[k] = ($; the position $k - 1$ then has excess $h - 2$, and no position in $[k, i-1]$ does, because the pair opened at $k$ is still open there, so $k - 1 = \text{bwdsearch}(i, -2)$. If $h = 1$, no position before $i$ has excess $-1$, and none is returned.

RMQ. The partial blocks are scanned exactly, and the canonical nodes of the full blocks are folded left to right with $c$ equal to the excess before each, so by the definition of $m$ the fold gives the minimum $\mu$ over $[i, j]$. If $E(i) > \mu$, every position in $[i, j]$ before the first one with excess $\mu$ has excess above $\mu$, and the first such position after $i$ is $\text{fwdsearch}(i, \mu - E(i))$, which lies in $[i, j]$ because $\mu$ is reached there. $\blacksquare$