Python基于欧拉游程+稀疏表RMQ实现LCA时右子树查询结果错误

问题根源 #

你的实现核心错误出在稀疏表的存储逻辑和RMQ返回值设计：

• 当前你构建稀疏表时存储的是节点深度值，但LCA算法要求RMQ返回的是「深度最小的节点在欧拉序列中的下标」，而非深度值本身
• 你直接将RMQ返回的深度值作为下标去euler数组取值，自然会得到错误的节点结果

修改方案 #

需要调整稀疏表的构建逻辑、RMQ查询逻辑，让稀疏表存储下标，比较时用下标对应的深度值，最终返回最小深度对应的下标：

1. 修改build_sparse_table方法 #

存储下标而非深度值，比较时通过下标取高度数组的值对比：

def build_sparse_table(self, height_array):
    n = len(height_array)
    for i in range(n):
        # 存下标，不是高度值
        self.pre_process_array[i][0] = i
        
    j = 1
    while (1 << j) <= n:
        i = 0
        while (i + (1 << j) - 1) < n:
            left = self.pre_process_array[i][j-1]
            right = self.pre_process_array[i + (1 << (j-1))][j-1]
            # 比较两个下标对应的高度值，存更小的那个的下标
            if height_array[left] < height_array[right]:
                self.pre_process_array[i][j] = left
            else:
                self.pre_process_array[i][j] = right
            i += 1
        j += 1

2. 修改rmq方法 #

返回最小深度对应的下标，而非深度值：

def rmq(self, l, h):
    j = int(math.log2(h - l + 1))
    left = self.pre_process_array[l][j]
    right = self.pre_process_array[h - (1 << j) + 1][j]
    # 返回高度更小的那个下标
    return left if self.height[left] <= self.height[right] else right

3. 补充find_LCA边界处理 #

当两个输入值相等时直接返回该值：

def find_LCA(self, val1, val2):
    if val1 >= len(self.index) or val2 >= len(self.index) or self.index[val1] == -1 or self.index[val2] == -1:
        return -1
    # 两值相等直接返回
    if val1 == val2:
        return val1
    if self.index[val1] > self.index[val2]:
        return self.euler[self.rmq(self.index[val2], self.index[val1])]
    else:
        return self.euler[self.rmq(self.index[val1], self.index[val2])]

注意事项 #

代码开头需要导入math模块，否则会报错。

测试验证 #

修改后运行驱动代码：

• l.find_LCA(6,7) 返回3，符合预期
• l.find_LCA(3,7) 返回3，符合预期
• 原有正确用例l.find_LCA(8,9)返回4、l.find_LCA(4,3)返回1保持正常

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