我们要计算：∑i=2N∑j=1i−1(Ai−Aj)2\sum_{i=2}^{N} \sum_{j=1}^{i-1} (A_i - A_j)^2∑i=2N ∑j=1i−1 (Ai −Aj )2
第一步：理解双重求和
双重求和的意思是：
* 对于每个 i 从 2 到 N
* 对于每个 j 从 1 到 i-1
* 计算 (Ai−Aj)2(A_i - A_j)^2(Ai −Aj )2
比如 N=3 时：
* i=2, j=1: (A2−A1)2(A_2 - A_1)^2(A2 −A1 )2
* i=3, j=1: (A3−A1)2(A_3 - A_1)^2(A3 −A1 )2
* i=3, j=2: (A3−A2)2(A_3 - A_2)^2(A3 −A2 )2
第二步：展开平方公式
(Ai−Aj)2=Ai2−2AiAj+Aj2(A_i - A_j)^2 = A_i^2 - 2A_iA_j + A_j^2 (Ai −Aj )2=Ai2 −2Ai Aj +Aj2
所以原问题变成：
∑i=2N∑j=1i−1(Ai2−2AiAj+Aj2)\sum_{i=2}^{N} \sum_{j=1}^{i-1} (A_i^2 - 2A_iA_j + A_j^2) i=2∑N j=1∑i−1 (Ai2 −2Ai Aj +Aj2 )
第三步：分离求和项
把求和拆成三部分：
1. ∑i=2N∑j=1i−1Ai2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_i^2 i=2∑N j=1∑i−1 Ai2
2. −2∑i=2N∑j=1i−1AiAj-2 \sum_{i=2}^{N} \sum_{j=1}^{i-1} A_iA_j −2i=2∑N j=1∑i−1 Ai Aj
3. ∑i=2N∑j=1i−1Aj2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_j^2 i=2∑N j=1∑i−1 Aj2
第四步：逐项分析（重点！）
第一项分析：
∑i=2N∑j=1i−1Ai2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_i^2 i=2∑N j=1∑i−1 Ai2
对于固定的 i，内层求和 ∑j=1i−1Ai2\sum_{j=1}^{i-1} A_i^2∑j=1i−1 Ai2 就是 (i-1) 个 Ai2A_i^2Ai2 相加：
∑j=1i−1Ai2=(i−1)×Ai2\sum_{j=1}^{i-1} A_i^2 = (i-1) \times A_i^2 j=1∑i−1 Ai2 =(i−1)×Ai2
所以第一项 = $$\sum_{i=2}^{N} (i-1) \times A_i^2$$
举例说明：
假设数组 A = [2, 8, 4]
* i=2: (2-1)×8² = 1×64 = 64
* i=3: (3-1)×4² = 2×16 = 32
第一项总和 = 64 + 32 = 96
第二项分析：
−2∑i=2N∑j=1i−1AiAj=−2∑i=2N[Ai×(∑j=1i−1Aj)]-2 \sum_{i=2}^{N} \sum_{j=1}^{i-1} A_iA_j = -2 \sum_{i=2}^{N} [A_i \times (\sum_{j=1}^{i-1} A_j)] −2i=2∑N j=1∑i−1 Ai Aj =−2i=2∑N [Ai ×(j=1∑i−1 Aj )]
这里 ∑j=1i−1Aj\sum_{j=1}^{i-1} A_j∑j=1i−1 Aj 就是 A₁ 到 Aᵢ₋₁ 的和，也就是前缀和！
举例说明：
A = [2, 8, 4]
* i=2: A₂×(A₁) = 8×2 = 16
* i=3: A₃×(A₁+A₂) = 4×(2+8) = 4×10 = 40
第二项总和 = -2×(16+40) = -2×56 = -112
第三项分析：
∑i=2N∑j=1i−1Aj2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_j^2 i=2∑N j=1∑i−1 Aj2
对于固定的 j，Aj2A_j^2Aj2 会被累加多少次？
* A₁² 出现在：i=2 时(j=1), i=3 时(j=1), ..., i=N 时(j=1)
* 所以 A₁² 被累加了 (N-1) 次
* A₂² 出现在：i=3 时(j=2), i=4 时(j=2), ..., i=N 时(j=2)
* 所以 A₂² 被累加了 (N-2) 次
更一般地：Aj2A_j^2Aj2 被累加了 (N-j) 次
所以第三项 = $$\sum_{j=1}^{N-1} (N-j) \times A_j^2$$
举例说明：
A = [2, 8, 4]
* j=1: (3-1)×2² = 2×4 = 8
* j=2: (3-2)×8² = 1×64 = 64
第三项总和 = 8 + 64 = 72
第五步：合并结果
总答案 = 第一项 + 第二项 + 第三项
= 96 + (-112) + 72 = 56
对于每个位置 i，计算它与前面所有数的平方差和：
对于第 i 个元素 Aᵢ：
* 它与前面 i-1 个元素的平方差和 = $$\sum_{j=0}^{i-1} (A_i - A_j)^2$$
* 展开：$$\sum_{j=0}^{i-1} (A_i^2 - 2A_iA_j + A_j^2)$$
* = $$(i-1)A_i^2 - 2A_i(\sum_{j=0}^{i-1} A_j) + (\sum_{j=0}^{i-1} A_j^2)$$
数组 A = [1, 3, 5, 7]
方法1：暴力计算
* (3-1)² = 4
* (5-1)² = 16, (5-3)² = 4
* (7-1)² = 36, (7-3)² = 16, (7-5)² = 4
总和 = 4 + 16+4 + 36+16+4 = 80
方法2：公式计算
维护前缀和 prefix_sum，前缀平方和 prefix_sum_sq
i=0: A₀=1
* 贡献 = 0 (前面没有元素)
* prefix_sum = 1, prefix_sum_sq = 1
i=1: A₁=3
* 贡献 = 1×3² + 1 - 2×3×1 = 9+1-6 = 4
* prefix_sum = 1+3=4, prefix_sum_sq = 1+9=10
i=2: A₂=5
* 贡献 = 2×5² + 10 - 2×5×4 = 50+10-40 = 20
* prefix_sum = 4+5=9, prefix_sum_sq = 10+25=35
i=3: A₃=7
* 贡献 = 3×7² + 35 - 2×7×9 = 147+35-126 = 56
* prefix_sum = 9+7=16, prefix_sum_sq = 35+49=84
