实现2D范围树C ++(implement 2d range tree c++)

我一直在试图理解范围树有一段时间了，但我仍然无法理解这一点。

可有人将其与实施给我解释一下，因为我想用它来解决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]);
}

谢谢 ：）

Answer 1:

你检查常用饼干罐？

如维基百科 ，一个前演讲的几个我在谷歌和除了发现堆栈问题 ？

我没有在大学学习它的乐趣，但它似乎是一个有趣的数据结构。

文章来源: implement 2d range tree c++