前缀和在图最短距离统计中的原理与核心代码解析

一、目标规律先明确 #

对于n个顶点的无向链状图（线性图），有序顶点对(u≠v)的最短距离统计有明确规律：

• 距离为1的有序对数量：2*(n-1)（每个内部顶点对应2个相邻顶点，首尾各1个，合计2*(n-1)）。
• 距离每增加1，数量递减2：距离d的有序对数量为2*(n-d)（d≥1），当d>n-1时数量为0。

以n=4为例：

• 距离1：6个（(1,2),(2,1),(2,3),(3,2),(3,4),(4,3)）
• 距离2：4个（(1,3),(3,1),(2,4),(4,2)）
• 距离3：2个（(1,4),(4,1)）
• 距离4：0个（不存在这么长的距离）
  最终结果数组[6,4,2,0]正好对应上述数量（索引k对应距离k+1）。

二、result[n - i - 1] -= 2语句解析 #

这段代码是在构造差分数组，核心逻辑：

1. 初始化时，数组第一个元素设为2*(n-1)（距离1的数量），其余元素为0。
2. 我们需要让后续每个距离的数量比前一个少2，即差分数组中索引1到n-1的位置值为-2。
3. 循环变量i从0到n-2时，n - i -1会依次指向数组的最后一位、倒数第二位……直到索引1的位置，每次对这些位置减2，等价于给这些位置赋值为-2（初始为0）。
   • 比如n=4时，i=0→索引3，i=1→索引2，i=2→索引1，这三个位置最终变为-2，数组变为[6,-2,-2,-2]。

三、前缀和result[i + 1] += result[i]的原理 #

差分数组的前缀和，就是将“递减量”转化为实际的距离统计数量：

• 索引0的数值是距离1的数量（6）。
• 索引1的数值 = 距离1的数量 + 差分（6+(-2)=4），对应距离2的数量。
• 索引2的数值 = 距离2的数量 + 差分（4+(-2)=2），对应距离3的数量。
• 索引3的数值 = 距离3的数量 + 差分（2+(-2)=0），对应距离4的数量。
• 本质是通过累加，把“每个距离比前一个少2”的规律转化为每个距离的实际总数。

四、完整执行流程（以n=4为例） #

1. 初始化：创建数组[6,0,0,0]。
2. 构造差分：循环处理后数组变为[6,-2,-2,-2]。
3. 前缀和计算：
   • result[1] = -2 + 6 = 4
   • result[2] = -2 + 4 = 2
   • result[3] = -2 + 2 = 0
4. 最终结果：[6,4,2,0]，与示例完全一致。

补充 #

如果需要统计无序顶点对，只需将最终数组的每个元素除以2即可，比如n=4时结果为[3,2,1,0]。

内容的提问来源于stack exchange，提问作者inovramadani