Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure. We wish to compute the value of all upper and rightmost cells $u_i$ and $r_i$ ($1\leq i\leq n$) when each cell of the table is filled recursively according to the equation $T(x,y)=T(x,y-1)+T(x-1,y)$ for each $x,y\geq 1$.
If we compute naively the $u_i,r_i$ by filling the table, or summing corresponding binomial coefficients, the complexity is $\Theta(n^2)$. Is this a lower bound for the problem or is there any way to compute all $u_i, r_i$ in $o(n^2)$? If so, does the technique extend to rectangular tables?