Optimal BST - Why QI Holds

For Optimal BST, $cost(i,j) = \sum_{l=i}^{j} f_l$ (sum of frequencies). I'll verify QI: $cost(a,c) + cost(b,d) \leq cost(a,d) + cost(b,c)$. Left side: $\sum_{l=a}^{c} f_l + \sum_{l=b}^{d} f_l$.

The middle part $[b,c]$ is counted twice. Right side: $\sum_{l=a}^{d} f_l + \sum_{l=b}^{c} f_l$. The full span $[a,d]$ plus the middle $[b,c]$ again. Breaking into pieces: left = $\sum_{a}^{b-1} + 2\sum_{b}^{c} + \sum_{c+1}^{d}$. Right = same expression. They're equal! Since left = right, we have left $\leq$ right. QI holds.