treap如何帮助更新这个有序队列？ [英] How does a treap help to update this ordered queue?

问题描述

我无法理解此

然后我们开始将间隔移动到开始。 treap被分成三个部分 - 一个具有第一个l-1个节点，一个具有间隔中的节点，以及最后的节点。

首先，区间[4,5]被移动：

现在treap的顺序是4，5，1，2，3，6（根4先到，因为它没有左孩子; 3在它的左子节点2之前，其前面有自己的左子节点5;然后是5的右子节点1;然后2，然后3，然后6.）节点跟踪每个子树的大小（<$ c $

给定[3,4]，我们首先调用 split（t，4），它应该返回一个对：一个treap与前4个元素，另一个与其余的。

根节点没有在它的左子树下有4个东西，所以它递归与 split（t-> r，3）。
这个节点（3）在其左子树下有3个事物，所以它
调用 split（t-> l，3）。
现在我们在节点（2）。它调用 split（t-> r，0），
，但它没有一个正确的孩子，所以这返回一对空指针。
因此，从节点（2），我们从（2）返回未改变的子树和一个nullptr。
传播，节点（3）将其左子节点设置为空，并从（2）返回
子树，并且在（3）本身（现在只是两个元素， （6）。）
最后，在节点（4），我们设置右子树为（2），并返回树（4）（现在有四个元素，如果需要）和二元素 c code> a 是最后一次调用的第一个四元素树。

没有左孩子，所以我们递归与 split（t-> r，1）。

节点2）具有尺寸为2的左子树，所以它调用 split（t-> l，1）。

节点（5）没有左孩子，所以它调用 split（t-> r，0）。

$ b b

在叶（1）处， 0 <= size（t-> l）是真空的：它从 split（t-> l，0）并返回一个对（null，（1））。

（5），我们设置正确的孩子为空，并返回一对（（5），（1））。

左孩子到（1），并返回一对（（5），（2） - >（1））。 （5），并返回一对（（4） - >（5），（2） - >（1））。

最后，移动区间[2,3]（由元素2和4组成）：

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

也许你想看到树状态给出不同的输入。我把一个treap代码的副本，instrumented生成图片，在GitHub 。当运行时，它产生一个文件trees.tex;然后运行 pdflatex trees 生成类似上面的图片。
（或者如果你喜欢，我会很乐意为不同的输入制作图片：如果你没有它，安装一个整体的TeX发行版会更容易。）

I'm having trouble understanding this solution to a problem on HackerRank. Please see the solution code below, apparently by Kimiyuki Onaka.

The problem is: given a list of unique numbers, and m queries of the type, "move the current ith to jth elements (l,r) to the beginning", return the final arrangement of the numbers.

Onaka suggests that a treap data structure (one that maintains both priority and binary search) can help solve it in O(m log n). Since I'm not versed in C++, I've tried but failed to conceptualize how a treap could be used. My understanding is that to solve the problem you need log time access to the current ith to jth elements and log time update of the current first element/s and overall order. But I can't see how to conceptualize it.

Ideally, I'd like an explanation in words of how it could be done. Alternatively, just an explanation of what Onaka's code is doing.

Thanks!

#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;
}

解决方案

Perhaps some pictures of the data structure as it processes the sample input would be helpful.

First, the six numbers "1 2 3 4 5 6" are inserted into the treap. Each one is associated with a randomly generated double, which determines if it goes above or below other nodes. The treap is always ordered so that all of a node's left children come before it, and all its right children come after.

Then we start moving intervals to the beginning. The treap is split into three parts—one with the first l-1 nodes, one with the nodes in the interval, and the last nodes. Then they are re-merged in a different order.

First, the interval [4,5] is moved:

Now the treap's order is 4, 5, 1, 2, 3, 6. (The root 4 comes first, because it has no left child; 3 is preceded by its left child 2, which is preceded by its own left child 5; then comes 5's right child 1; then 2, then 3, then 6.) The nodes keep track of the size of each subtree (m_size).

Given [3,4], we first call split(t,4), which should return a pair: one treap with the first 4 elements, and another one with the rest.

The root node (4) does not have 4 things under its left subtree, so it recurses with split(t->r, 3). This node (3) does have 3 things under its left subtree, so it calls split(t->l, 3). Now we are at node (2). It calls split(t->r, 0), but it does not have a right child, so this returns a pair of null pointers. Thus from node (2) we return the unchanged subtree from (2), and a nullptr. Propagating up, node (3) sets its left child to null, and returns the subtree from (2), and the subtree at (3) itself (which is now just two elements, (3) and (6).) Finally, at node (4) we set the right subchild to (2), and return the tree at (4) (which now has four elements, as required) and the two-element tree rooted at (3).

Next a call is made to split(a,2), where a is the first, four-element, tree from the last call.

Again, the root (4) has no left child, so we recurse with split(t->r, 1).

The node (2) has a left subtree with size 2, so it calls split(t->l, 1).

The node (5) has no left child, so it calls split(t->r, 0).

At the leaf (1), 0 <= size(t->l) is vacuously true: it gets a pair of null pointers from split(t->l, 0) and returns a pair(null, (1)).

Up at (5), we set the right child to null, and return a pair((5), (1)).

Up at (2), we set the left child to (1), and return a pair((5), (2)->(1)).

Finally, at (4), we set the right child to (5), and return a pair((4)->(5), (2)->(1)).

Finally the interval [2,3] (consisting of the elements 2 and 4) is moved:

Finally the nodes are popped in order, yielding 2, 4, 1, 5, 3, 6.

Perhaps you'd like to see the tree states given different input. I put a copy of the treap code, "instrumented" to produce the pictures, on GitHub. When run, it produces a file trees.tex; then running pdflatex trees produces pictures like those above. (Or if you like, I'd be happy to make pictures for different input: that would be easier than installing a whole TeX distribution if you don't have it.)

这篇关于treap如何帮助更新这个有序队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！