implement 2d range tree c++

Question

I have been trying to understand range tree for some time, but i still can't understand it.

Can someone explain it to me with an implementation, because i want to use it to solve 2D RMQ, i know segment tree, and my teacher tell me range tree is similar to 2d segment tree, but i just can't think how the space complexity can be less than n^2 like 2d segment tree.

I'm not sure about this, but is it true that, it's like merge sort, so the memory will be less than n^2 using vector

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]);
}

Thanks :)

score 0 · Answer 1 · edited May 23 '17 at 12:16

0

Have you checked the usual cookie jars?

Such as Wikipedia, a former lecture of several I found on Google and in addition to a Stack Question?

I did not have the pleasure of learning it at University but it appears to be an interesting data structure.

edited May 23 '17 at 12:16

Community

1
1

answered Mar 27 '13 at 17:12

Mushy

2,535
10
33
54

@zeulb What specifically about a range tree do you not understand? – Mushy Mar 27 '13 at 20:03
i don't understand how it implemented, is it segment tree where on every node, there's a segment tree too ? – zeulb Mar 28 '13 at 05:58
@zeulb Just from reading the Wikipedia article, it appears that a range tree recursively constructs each dimension from a binary search tree. A binary search tree is just a binary tree (less than root push left-subtree, greater than or equal to the root push right-subtree); an ordered data structure allowing efficient storage and retrieval of data. The article mentions a segment tree and k-d and I would suggest that as a starting place. – Mushy Mar 28 '13 at 11:38
i tried making a range tree, here's my implementation, but it appears to be really slow http://stackoverflow.com/questions/15675417/2d-rmq-range-tree – zeulb Mar 28 '13 at 13:52

implement 2d range tree c++

1 Answers1

Linked