1

しばらくの間、範囲ツリーを理解しようとしてきましたが、まだ理解できません。

2D RMQを解決するためにそれを使用したいので、誰かが実装でそれを説明してもらえますか?複雑さは、2D セグメント ツリーのように n^2 未満にすることができます。

これについてはよくわかりませんが、マージソートのようなものなので、ベクターを使用するとメモリがn ^ 2未満になるというのは本当ですか

void merge(vector<int> &res,vector<int> &a,vector<int> &b)
{
    int la = 0;
    int lb = 0;
    int sa = SIZE(a);
    int sb = SIZE(b);
    while(la < sa || lb < sb)
    {
        if (la >= sa) {res.pb(b[lb]);lb++;}
        else if (lb >= sb) {res.pb(a[la]);la++;}
        else
        {
            if (a[la] < b[lb]) {res.pb(a[la]);la++;}
            else {res.pb(b[lb]);lb++;}
        }
    }
}

void build(int n,int l,int r)
{
    if (l == r)
    {
        rtree[n].pb(ar[l]);
        return;
    }
    int m = (l+r)/2;
    build(2*n,l,m);
    build(2*n+1,m+1,r);
    merge(rtree[n],rtree[2*n],rtree[2*n+1]);
}

ありがとう ：）

4

1 に答える 1

0

いつものクッキージャーはチェックしましたか？

ウィキペディアなど、Googleで見つけたいくつかの以前の講義と、スタックの質問に加えて?

大学でそれを学ぶ喜びはありませんでしたが、興味深いデータ構造のようです。

于 2013-03-27T17:12:14.610 に答える