-1

我正在学习段树（以范围最小查询为例）并且在理解查询段树的算法部分背后的原因时遇到了一些问题。

我理解构建段树的部分没有问题，我不明白为什么在这个函数中：

int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)
{
    // If segment of this node is a part of given range, then return the min of the segment
    if (qs <= ss && qe >= se)
        return st[index];    // this is the part I am struggling with

    // If segment of this node is outside the given range
    if (se < qs || ss > qe)
        return INT_MAX;

    // If a part of this segment overlaps with the given range
    int mid = getMid(ss, se);
    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1), RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}

如果该节点的段是给定范围的一部分，则返回该段的最小值。

4

2 回答 2

0

如果该节点的段是给定范围的一部分，那么您已经知道子段 [ss, se] 的答案（它是 st[index]），您无需再深入。

于 2015-01-18T06:51:23.003 回答
0

在查询中，您要查找 [qs,qe] 范围内的最小数字。

现在，就分段树而言，这可以表示为首先找到区间的中间，即 mid=(qs+qe)/2

逻辑是 [qs,qe] 范围内的最小值等于在 [qs,mid] 和 [mid+1,qe] 范围内找到最小值的最小值。

这是用你的代码写在以下几行中的：

int mid = getMid(ss, se);
    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1), RMQUtil(st, mid+1, se, qs, qe, 2*index+2));

于 2015-05-13T09:30:53.970 回答