https://i.stack.imgur.com/2tUtb.png $$M = \left[ {\begin{array}{*{20}{c}} 1&2& \vdots &n \\ 1&2& \cdots &n \\ \vdots & \vdots & \vdots &n \\ 1&2& \cdots &n \end{array}} \right]$$
Imagine matrix M as above. Is there a way to calculate the sum of the lower triangular including the diagonal elements in O(1?)
Notice that that the sum of the lower triangle is equal to $$\frac{1}{2}\sum^n_{i=1} i^2 + i $$ This is because (from the bottom row to the top row) you are adding 1 through $n$ and then add 1 through $n-1$ and then 1 through $n-2$ and so on.
This sum can be split into two famous finite series: $$\frac{1}{2}(\sum^n_{i=1} i^2 + \sum^n_{i=1} i) = \frac{1}{2}(\frac{n(n+1)}{2} + \frac{n(n+1)(2n+1)}{6})$$.
Since this is just a equation, the sum can be calculate in $\mathcal{O}(1)$