Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$
Let me try to sketch a method that counts the triplets by directly counting. Let me first assume that $a$ is sorted. I will also keep $x$ constant for this exposition (and iterate over $x$). For simplicity take $a[x]=0$, so the task is to count $(y,z)$ such that $a[y]+a[z]&lt;0$. We can count the pairs, but not by going over all $n^2$ of them, but by following the "boundary" between negative and positive pairs. This is like counting the number of negative elements in a two dimensional array that is increasing in both dimensions. This seems to be possible in linear time? (for fixed $x$) 

As an example we consider the following virtual two-dimensional array; i.e., it is not explicitly constructed, element $(y,z)$ just is $a[y]+a[z]$. We can count the elements $a[y]+a[z]&gt;9$ by "walking" along the "boundary".

$\begin{array}{c|ccccc}
a &amp; 1 &amp; 3 &amp; 4 &amp; 7 &amp; 8 \\\hline
1 &amp; 2 &amp; 4 &amp; 5 &amp; 8 &amp; 9 \\
3 &amp; 4 &amp; 6 &amp; 7 &amp; \color{green}{10}&amp; \color{green}{11}\\
4 &amp; 5 &amp; 7 &amp; 8 &amp; \color{green}{11}&amp; \color{green}{12}\\
7 &amp; 8 &amp; \color{green}{10}&amp; \color{green}{11}&amp; \color{green}{14}&amp; \color{green}{15}\\
8 &amp; 9 &amp; \color{green}{11}&amp; \color{green}{12}&amp; \color{green}{15}&amp; \color{green}{16}
\end{array}$