Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$
Let $A = \sum_{i=1}^n A_i$. We have
$$
\begin{align*}
A^3 &amp;= \sum_{i=1}^n A_i^3 + 3\sum_{i=1}^n \sum_{j \neq i} A_i^2 A_j + 6 \sum_{i &lt; j &lt; k} A_i A_j A_k \\ &amp;=
\sum_{i=1}^n A_i^3 + 3 \sum_{i=1}^n A_i^2 (A - A_i) + 6 \sum_{i &lt; j &lt; k} A_i A_j A_k.
\end{align*}
$$
This gives a linear time algorithm.

More generally, the theory of symmetric polynomials ensures that every symmetric polynomial can be computed in linear time, since it is a polynomial in the quantities $B_d := \sum_{i=1}^n A_i^d$. For example,
$$
\sum_{i&lt;j&lt;k} A_i A_j A_k = \frac{B_1^3+2B_3-3B_1B_2}{6}.
$$