Each row in the array below represents a set of terms in one of the sums. So $n=4$ in this example, and the first row contains the term of $c_{11}$, the second row the terms of $c_{12}$, and so on until the last row which contains the term of $c_{44}$.
$$
\begin{array}{ccccc}
a_1\\
a_1 & a_2\\
a_1 & a_2 & a_3\\
a_1 & a_2 & a_3 & a_4\\
\hline
& a_2\\
& a_2 & a_3\\
& a_2 & a_3 & a_4\\
\hline
& & a_3\\
& & a_3 & a_4\\
\hline
& & & a_4
\end{array}
$$
The best way to do the sum is by columns, not rows. So the first column has $4$ copies of $a_1$, which we can think of as $1$ group of $4$. The second column has six copies of $a_2$, which we can think of as $2$ groups of $3$: a group where $a_1$ is the element of lowest index and a group where $a_2$ is the element of lowest index. Similarly, the third column has $3$ groups of $2$ copies of $a_3$: a group with $a_1$ as the element of lowest index, a group with $a_2$ as the element of lowest index, and a group with $a_3$ as the element of lowest index. Finally, the fourth column has $4$ groups each with $1$ copy of $a_4$.
Therefore you get
$$
1\cdot4\cdot a_1+2\cdot3\cdot a_2+3\cdot2\cdot a_3+4\cdot1\cdot a_4.
$$
Added: I may have misinterpreted the question. I understood that there was an array, $[a_1, a_2, \ldots, a_n]$ and that the goal was to find the average of the sums
\begin{align}
&c_{1,1}=a_1\\
&c_{1,2}=a_1+a_2\\
&c_{1,3}=a_1+a_2+a_3\\
&\vdots\\
&c_{n-1,n-1}=a_{n-1}\\
&c_{n-1,n}=a_{n-1}+a_n\\
&c_{n,n}=a_n.
\end{align}
There are $\binom{n+1}{2}$ such sums, so the average would be
\begin{align}
\frac{1}{\binom{n+1}{2}}\sum_{1\le i\le j\le n}c_{ij}&=\frac{1}{\binom{n+1}{2}}\sum_{i=1}^n\sum_{j=i}^n\sum_{\ell=i}^j a_\ell\\
&=\frac{1}{\binom{n+1}{2}}\sum_{i=1}^n\sum_{\ell=i}^na_\ell\sum_{j=\ell}^n1\\
&=\frac{1}{\binom{n+1}{2}}\sum_{i=1}^n\sum_{\ell=i}^na_\ell(n+1-\ell)\\
&=\frac{1}{\binom{n+1}{2}}\sum_{\ell=1}^na_\ell(n+1-\ell)\sum_{i=1}^\ell 1\\
&=\frac{1}{\binom{n+1}{2}}\sum_{\ell=1}^na_\ell(n+1-\ell)\ell,
\end{align}
which is an $O(n)$ computation. These rearrangements of summation symbols are essentially the "sum by columns rather than by rows" idea in the example above.
It seems, however, that what was actually meant is that there is an array, $[b_1,b_2,\ldots,b_n]$ and that $c_{ij}$ is defined by
$$
c_{ij}=\sum_{\ell=1}^n b_\ell\theta(b_\ell-i)\theta(j-b_\ell),
$$
where
$$
\theta(m)=\begin{cases}0 & \text{if $m<0$}\\ 1 & \text{if $m\ge0$.}\end{cases}
$$
This could also be written as
$$
c_{ij}=\sum_{\ell=1}^nf(i,j,b_\ell),
$$
where
$$
f(i,j,k)=\begin{cases}k & \text{if $i\le k\le j$}\\ 0 & \text{otherwise.}\end{cases}
$$
This problem can be converted to the problem I solved in $O(n)$ time by initializing the array $[a_1,a_2,\ldots,a_n]$ so that every element is $0$. Then for each $b$ in $[b_1,b_2,\ldots,b_n]$ such that $1\le b\le n$, add $b$ to $a_b$. For example, if $n=4$ and $[b_1,b_2,b_3,b_4]=[6,4,2,2]$ then $[a_1,a_2,a_3,a_4]$ would, at the end of the process, equal $[0,4,0,4]=[0,2,0,1]\circ[1,2,3,4]$, where $\circ$ is the element-wise product. In general, at the end of the process we have
$$
[a_1,a_2,\ldots,a_n]=[m_1,m_2,\ldots,m_n]\circ[1,2,\ldots,n],
$$
where $m_k$ is the number of times $k$ appears in $[b_1,b_2,\ldots,b_n]$.
Now proceed using the previous algorithm, which, as was said, is also $O(n)$.
If we combine this with the previous formula, we get that the average is
$$
\frac{1}{\binom{n+1}{2}}\sum_{\ell=1}^nm_\ell\cdot\ell\cdot(n+1-\ell)\ell.
$$
It's not necessary to use the multiplicities $m_\ell$; you can instead sum over the individual $b_k$, using the function $f$ to omit those that might be out of the interval $[1,n]$:
$$
\frac{1}{\binom{n+1}{2}}\sum_{k=1}^nf(1,n,b_k)\cdot(n+1-b_k)b_k.
$$
This is manifestly an $O(n)$ calculation.