急！一个 Splay 相关的问题

我在写 Splay 的时候不插入哨兵节点。当题目要求我找某段区间的时候，我特判一下区间的左右端点是否是 1 和 n。

如果左端点是 1 右端点是 n，我直接 return 当前的 root；如果左端点是 1，我把 r +1 splay 到 root，返回 root 的左儿子；如果右端点是 n，我把 l - 1 splay 到 root，返回 root 的右儿子；如果左右端点不是 1 和 n，我先把 l - 1 splay 到 root，再把 r + 1 splay 到 root 的右儿子，最后返回 root 的右儿子的左儿子。

代码大概长这样：

CPP

int find_interval(int l, int r)
{
    if(l == 1 && r == n)
        return rt;
    else if(l == 1)
    {
        kth(r + 1);
        return t[rt].son[0];
    }
    else if(r == n)
    {
        kth(l - 1);
        return t[rt].son[1];
    }
    else
    {
        kth(l - 1);
        kth_to_leaf(r + 1);
        return t[t[rt].son[1]].son[0];
    }
}

这个写法不是别人教我的，是我自己胡的，我自己感觉这玩意挺对的，之前也没出过问题。但是今天写这道题的时候，发现当 r == n 的时候我的 Splay 寄掉了。为了测试是不是自己其他地方的问题，我插入了哨兵节点，这样就保证不会存在 r == n 的情况，然后就过了。

我现在很慌，我不确定是不是我的 Splay 从我第一次写开始就是错的，还是因为这道题我在某个地方写挂而错的（但这样似乎说不过去，如果我真的写挂了的话插入哨兵节点也没理由能过），恳请各位大佬帮忙想想我这个 Splay 是不是对的，拜谢。

完整代码在二楼

急！一个 Splay 相关的问题

讨论操作

回复

相关推荐

急！一个 Splay 相关的问题