笔记

userId_undefined

Yuilice

2025-10-19 15:54:39

发布于：浙江

8阅读
0回复
0点赞

我们要计算：∑i=2N∑j=1i−1(Ai−Aj)2\sum_{i=2}^{N} \sum_{j=1}^{i-1} (A_i - A_j)^2

第一步：理解双重求和

双重求和的意思是：

  • 对于每个 i 从 2 到 N
  • 对于每个 j 从 1 到 i-1
  • 计算 (Ai−Aj)2(A_i - A_j)^2

比如 N=3 时：

  • i=2, j=1: (A2−A1)2(A_2 - A_1)^2
  • i=3, j=1: (A3−A1)2(A_3 - A_1)^2
  • i=3, j=2: (A3−A2)2(A_3 - A_2)^2

第二步：展开平方公式

(Ai−Aj)2=Ai2−2AiAj+Aj2(A_i - A_j)^2 = A_i^2 - 2A_iA_j + A_j^2

所以原问题变成：

∑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)

第三步：分离求和项

把求和拆成三部分：

  1. ∑i=2N∑j=1i−1Ai2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_i^2

  2. −2∑i=2N∑j=1i−1AiAj-2 \sum_{i=2}^{N} \sum_{j=1}^{i-1} A_iA_j

  3. ∑i=2N∑j=1i−1Aj2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_j^2

第四步：逐项分析（重点！）

第一项分析：

∑i=2N∑j=1i−1Ai2\sum_{i=2}^{N} \sum_{j=1}^{i-1} A_i^2

对于固定的 i，内层求和 ∑j=1i−1Ai2\sum_{j=1}^{i-1} A_i^2 就是 (i-1) 个 Ai2A_i^2 相加：

∑j=1i−1Ai2=(i−1)×Ai2\sum_{j=1}^{i-1} A_i^2 = (i-1) \times A_i^2

所以第一项 = $$\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)]

这里 ∑j=1i−1Aj\sum_{j=1}^{i-1} A_j 就是 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

对于固定的 j，Aj2A_j^2 会被累加多少次？

  • 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^2 被累加了 (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
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论