TAOCP 2.2.6 Exercise 4
In lexicographic order, the elements are stored as A[0,0],A[0,1],\ldots,A[0,n],A[1,1],A[1,2],\ldots,A[1,n],\ldots,A[n,n].
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 4. [**] [22] Show that if we store the upper triangular array A[j,k] for $0 \le j \le k \le n$ in lexicographic order of the indices, the allocation satisfies the condition of Eq. (8). Find a formula for LOC(A[J,K]) in this sense.
Verified: no
Solve time: 29s
In lexicographic order, the elements are stored as
$$ A[0,0],A[0,1],\ldots,A[0,n],A[1,1],A[1,2],\ldots,A[1,n],\ldots,A[n,n]. $$
Before the row beginning with index $J$, there are
$$ (n+1)+n+\cdots+(n-J+2) $$
stored elements. Since this is the sum of $J$ terms,
$$ (n+1)+n+\cdots+(n-J+2) =J(n+1)-\frac{J(J-1)}2. $$
Within row $J$, the element $A[J,K]$ is preceded by $K-J$ elements. Therefore
$$ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + J(n+1) -\frac{J(J-1)}2 +(K-J). $$
Hence
$$ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + Jn-\frac{J(J-1)}2 +K. $$
This has the form (8), namely
$$ \operatorname{LOC}(A[J,K]) = a_0+f_1(J)+f_2(K), $$
with
$$ a_0=\operatorname{LOC}(A[0,0]),\qquad f_1(J)=Jn-\frac{J(J-1)}2,\qquad f_2(K)=K. $$
Thus the lexicographic allocation of the upper triangular array satisfies condition (8). The address formula is
$$ \boxed{ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + Jn-\frac{J(J-1)}2 +K }. $$