1685. Sum of Absolute Differences in a Sorted Array

T: O(n)
S: O(n)

```java
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n+1];
        for (int i = 0; i < n; i++) {
            prefixSum[i+1] = nums[i] + prefixSum[i];
        }
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = i*nums[i] - (prefixSum[i]) + (prefixSum[n] - prefixSum[i])  - (n-i)*(nums[i]);
        }
        return result;
    }
}

/*
T: O(n)
S: O(n)

[2,3,5]

result[i] = nums[i] - nums[0] + nums[i] - nums[1] + ... nums[i] - nums[i-1]
nums[i] - nums[i] + nums[i+1] - nums[i] + nums[i+2] -nums[i] + ... + nums[n-1] - nums[i]


nums[0] + nums[1] + ... + nums[i-1] -> prefix[i] - prefix[0] -> prefix[0] is 0, so = prefix[i]


-> nums[i] + nums[i+1]  + nums[i+2]  + ... + nums[n-1]  => (prefixSum[n] - prefixSum[i])
because there are i, i+1...n-1, 個數, 所以像是start from 0 index to n-1, so n-1-i+1 = n-i 個元素

i*nums[i] - (nums[0]+....nums[i-1])
(nums[i] + .... nums[n-1])- (n-i)*(nums[i])   // n-1-i-1 + 1 = n-i-1

i*nums[i] - (prefix[i])
+ (prefix[n] - prefix[i])  - (n-i)*(nums[i]) 

*/
```

另一種觀察

```java
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[0] += nums[i] - nums[0]; // sorted, so this is positive, no abs needs
        }
        for (int i = 1; i < n; i++) {
            result[i] = result[i-1] + i*(nums[i] - nums[i-1]) + (n-i)*(nums[i-1] - nums[i]);
        }
        return result;
    }
}

/*
T: O(n)
S: O(n)

觀察 diff 的關係, 如果我們能知到 result[i-1] -> 是不是可以推出 result[i]？
其實就加上和剪上 nums[i], nums[i-1] 之間的 diff

舉例來說：
[1,4,6,8,10]

if 6 diff for others is

5 2 0 2 4

then 8 is...

5+(8-6). 2+(8-6) 0+(8-6)    2 + (6-8)     4 + (6-8)
7          4         2.       0.           2

so become
             (5+2+0+2+4)
result[i] = result[i-1] + 3*(8-6) + 2*(6-8)

result[3] = result[2] + 3*(8-6) + 2*(6-8)

result[i] = result[i-1] + i*(nums[i] - nums[i-1]) + (n-i)*(nums[i-1] - nums[i])


another way is prefix, list all formula, then combine it, will see prefix usage!
*/
```

2121 也可以做一下