My O(n) solution:

collect following 4 parameters at each of n steps:

1. number of nodes
2. distance of diagonal (top left most node and bottom right most node)
3. sum of distances between right most bottom node and every other node
4. sum of distances between each pair of nodes.

Initially (before first step) there is 1 node, and other values are zeros. Calculate values for current step from previous step values in O(1).