c++ - treap 如何帮助更新这个有序队列？

Question

我无法理解 solution到 problem在 HackerRank 上。请参阅下面的解决方案代码，显然是由 Kimiyuki Onaka 提供的。

问题是:给定一个唯一数字的列表，以及 m 类型的查询，“将当前第 i 到第 j 个元素 (l,r) 移到开头", 返回数字的最终排列。

Onaka 建议使用 treap 数据结构(一种同时保持优先级和二进制搜索的结构)可以帮助在 O(m log n) 中解决它。由于我不精通 C++，我尝试过但未能概念化如何使用 treap。我的理解是，要解决您需要 log 时间访问当前 ith 到 jth 元素和 log 当前第一个元素的时间更新的问题/s 和总体顺序。但我看不出如何将其概念化。

理想情况下，我想要一个关于如何完成的解释。或者，只是解释 Onaka 的代码在做什么。

谢谢!

#include <iostream>
#include <tuple>
#include <random>
#include <memory>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

template <typename T>
struct treap {
    typedef T value_type;
    typedef double key_type;
    value_type v;
    key_type k;
    shared_ptr<treap> l, r;
    size_t m_size;
    treap(value_type v)
            : v(v)
            , k(generate())
            , l()
            , r()
            , m_size(1) {
    }
    static shared_ptr<treap> update(shared_ptr<treap> const & t) {
        if (t) {
            t->m_size = 1 + size(t->l) + size(t->r);
        }
        return t;
    }
    static key_type generate() {
        static random_device device;
        static default_random_engine engine(device());
        static uniform_real_distribution<double> dist;
        return dist(engine);
    }
    static size_t size(shared_ptr<treap> const & t) {
        return t ? t->m_size : 0;
    }
    static shared_ptr<treap> merge(shared_ptr<treap> const & a, shared_ptr<treap> const & b) { // destructive
        if (not a) return b;
        if (not b) return a;
        if (a->k > b->k) {
            a->r = merge(a->r, b);
            return update(a);
        } else {
            b->l = merge(a, b->l);
            return update(b);
        }
    }
    static pair<shared_ptr<treap>, shared_ptr<treap> > split(shared_ptr<treap> const & t, size_t i) { // [0, i) [i, n), destructive
        if (not t) return { shared_ptr<treap>(), shared_ptr<treap>() };
        if (i <= size(t->l)) {
            shared_ptr<treap> u; tie(u, t->l) = split(t->l, i);
            return { u, update(t) };
        } else {
            shared_ptr<treap> u; tie(t->r, u) = split(t->r, i - size(t->l) - 1);
            return { update(t), u };
        }
    }
    static shared_ptr<treap> insert(shared_ptr<treap> const & t, size_t i, value_type v) { // destructive
        shared_ptr<treap> l, r; tie(l, r) = split(t, i);
        shared_ptr<treap> u = make_shared<treap>(v);
        return merge(merge(l, u), r);
    }
    static pair<shared_ptr<treap>,shared_ptr<treap> > erase(shared_ptr<treap> const & t, size_t i) { // (t \ t_i, t_t), destructive
        shared_ptr<treap> l, u, r;
        tie(l, r) = split(t, i+1);
        tie(l, u) = split(l, i);
        return { merge(l, r), u };
    }
};

typedef treap<int> T;
int main() {
    int n; cin >> n;
    shared_ptr<T> t;
    repeat (i,n) {
        int a; cin >> a;
        t = T::insert(t, i, a);
    }
    int m; cin >> m;
    while (m --) {
        int l, r; cin >> l >> r;
        -- l;
        shared_ptr<T> a, b, c;
        tie(a, c) = T::split(t, r);
        tie(a, b) = T::split(a, l);
        t = T::merge(T::merge(b, a), c);
    }
    repeat (i,n) {
        if (i) cout << ' ';
        shared_ptr<T> u;
        tie(t, u) = T::erase(t, 0);
        cout << u->v;
    }
    cout << endl;
    return 0;
}

Answer 1

也许在处理示例输入时数据结构的一些图片会有所帮助。

首先，将六个数字“1 2 3 4 5 6”插入到树丛中。每一个都与一个随机生成的 double 相关联，这决定了它是高于还是低于其他节点。 treap 总是有序的，因此节点的所有左子节点都在它之前，而它的所有右子节点都在它之后。

然后我们开始将间隔移动到开头。 treap 被分成三个部分——一个包含前 l-1 个节点，一个包含间隔中的节点，以及最后一个节点。然后它们以不同的顺序重新合并。

首先移动区间[4,5]:

现在treap的顺序是4, 5, 1, 2, 3, 6。(根4排在第一位，因为它没有左 child ；3之前是它的左 child 2，它之前是它自己的左 child child 5；然后是 5 的右 child 1；然后是 2，然后是 3，然后是 6。)节点跟踪每个子树的大小 (m_size)。

给定 [3,4]，我们首先调用 split(t,4) ，它应该返回一对:一个 treap 包含前 4 个元素，另一个包含其余元素。

根节点(4)的左子树下没有4个东西，所以用split(t->r, 3)递归.这个节点 (3) 在它的左子树下确实有 3 个东西，所以它电话 split(t->l, 3) .现在我们在节点 (2)。它调用split(t->r, 0) ,但它没有右 child ，因此返回一对空指针。因此，我们从节点 (2) 返回 (2) 中未更改的子树和一个 nullptr。向上传播，节点(3)将其左子节点设置为空，并返回来自 (2) 的子树，以及 (3) 本身的子树(现在只有两个元素，(3) 和 (6)。)最后，在节点 (4) 处，我们将右子节点设置为 (2)，并返回 (4) 处的树(根据需要，现在有四个元素)和以 (3) 为根的二元素树。

接下来调用split(a,2) , 其中a是上次调用的第一个四元素树。

同样，根 (4) 没有左 child ，所以我们递归 split(t->r, 1) .

节点 (2) 有一个大小为 2 的左子树，所以它调用 split(t->l, 1) .

节点 (5) 没有左 child ，所以它调用 split(t->r, 0) .

在叶 (1) 处，0 <= size(t->l)是空洞的真实:它从 split(t->l, 0) 得到一对空指针并返回一对(null，(1))。

在 (5) 处，我们将右 child 设置为 null，并返回一对 ((5), (1))。

在 (2) 处，我们将左 child 设置为 (1)，并返回一对 ((5), (2)->(1))。

最后，在 (4) 处，我们将右 child 设置为 (5)，并返回一对 ((4)->(5), (2)->(1))。

最后移动区间 [2,3](由元素 2 和 4 组成):

最后按顺序弹出节点，产生 2、4、1、5、3、6。

也许您想查看给定不同输入的树状态。我放了一份 treap 代码，“用工具”生成图片，on GitHub .运行时，它会生成一个文件 trees.tex；然后运行 ​​pdflatex trees产生像上面那样的图片。(或者，如果您愿意，我很乐意为不同的输入制作图片:如果您没有的话，这比安装整个 TeX 发行版要容易。)