假设我有一个数组，我必须回答查询，比如找到从索引i到j的所有元素的总和，现在我可以在root树上执行此操作，就像回答从节点i到j的路径的此类查询一样（仅限于从i到j）存在的路径 .
我知道如何找到LCA使用范围最小查询，我们将其分解为线性数组然后使用段树但我无法修改它以进行求和查询 . 我怎么做？
这取决于您的处理要求：您是否有复杂性限制，或者目标是在午餐时间之前使用可维护的代码？
如果是后者，采取简单的方法：
在树中找到两个节点 .
从第一个节点开始，遍历回根，将路径成本求和，保持每个节点的部分和 .
从第二个节点开始，也是朝向根的遍历和求和（仅完全求和，无部分） .
当遇到's an ancestor of the first one, you'找到LCA的节点时 .
将当前总和添加到第一个节点的LCA部分和 . 完成 .
第一学期的数据结构学生很容易理解这个算法 . 通过对LCA的一致性检查，它是 O （log（n）^ 2） - 不错，但不是LCA的线性前期工作和恒定时间查询返回的最佳值 .
如果您需要更快的算法，那么我建议您扩充LCA预处理算法，以便每个节点还计算其每个祖先的部分和的散列列表（例如Python字典） . 完成后，您可以对LCA进行恒定时间计算，并对每个部分和进行恒定时间查找 .
1 回答
这取决于您的处理要求：您是否有复杂性限制，或者目标是在午餐时间之前使用可维护的代码？
如果是后者，采取简单的方法：
在树中找到两个节点 .
从第一个节点开始，遍历回根，将路径成本求和，保持每个节点的部分和 .
从第二个节点开始，也是朝向根的遍历和求和（仅完全求和，无部分） .
当遇到's an ancestor of the first one, you'找到LCA的节点时 .
将当前总和添加到第一个节点的LCA部分和 . 完成 .
第一学期的数据结构学生很容易理解这个算法 . 通过对LCA的一致性检查，它是 O （log（n）^ 2） - 不错，但不是LCA的线性前期工作和恒定时间查询返回的最佳值 .
如果您需要更快的算法，那么我建议您扩充LCA预处理算法，以便每个节点还计算其每个祖先的部分和的散列列表（例如Python字典） . 完成后，您可以对LCA进行恒定时间计算，并对每个部分和进行恒定时间查找 .