2D RMQ范围树(2D RMQ Range Tree)

你好我试图实施RMQ-ING二维范围内的树，这里是我的代码，我认为这是不够高效，有什么我可以做optimation。

LS包含排序的每个节点上的ÿ名单

RT包含段树

p.fi.fi含有x坐标

p.fi.se包含y坐标

p.se包含点的ID

LOC包含每个内径×节点和y节点

    vector<pii> ls[400005];
    vector<int> rt[400005];
    pair<pii,int> p[100005];

    vector<pii> loc[100005];

    inline void merge(int id,vector<pii> &res,vector<pii> &a,vector<pii> &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]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
            else if (lb >= sb) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
            else
            {
                if (a[la] < b[lb]) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
                else {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
            }
        }
    }


    inline void build_x(int n,int l,int r)
    {
        if (l == r)
        {
            ls[n].clear();
            ls[n].pb(mp(p[l].fi.se,p[l].se));
            rt[n].assign(SIZE(ls[n])<<2,0);
            loc[p[l].se].pb(mp(n,0));
            return;
        }
        int m = (l+r)>>1;
        build_x((n<<1),l,m);
        build_x((n<<1)+1,m+1,r);
        ls[n].clear();
        merge(n,ls[n],ls[(n<<1)],ls[(n<<1)+1]);
        rt[n].assign(SIZE(ls[n])<<2,0);
    }

    inline int query_y(int nx,int n,int l,int r,int ly,int ry)
    {
        if (ly > ls[nx][r].fi || ry < ls[nx][l].fi) return 0;
        if (ly <= ls[nx][l].fi && ls[nx][r].fi <= ry)
        {
            return rt[nx][n];
        }
        int res = 0;
        int m = (l+r)>>1;
        if (ly <= ls[nx][m].fi) MAX(res,query_y(nx,(n<<1),l,m,ly,min(ls[nx][m].fi,ry)));
        if (ls[nx][m+1].fi <= ry) MAX(res,query_y(nx,(n<<1)+1,m+1,r,max(ls[nx][m+1].fi,ly),ry));
        return res;
    }


    inline int query_x(int n,int l,int r,int lx,int rx,int ly,int ry)
    {
        if (lx > p[r].fi.fi || rx < p[l].fi.fi) return 0;
        if (lx <= p[l].fi.fi && p[r].fi.fi <= rx)
        {
            return query_y(n,1,0,SIZE(ls[n])-1,ly,ry);
        }
        int res = 0;
        int m = (l+r)>>1;
        if (lx <= p[m].fi.fi) MAX(res,query_x((n<<1),l,m,lx,min(p[m].fi.fi,rx),ly,ry));
        if (p[m+1].fi.fi <= rx) MAX(res,query_x((n<<1)+1,m+1,r,max(p[m+1].fi.fi,lx),rx,ly,ry));
        return res;
    }

    int nx;

    inline void update_y(int n,int l,int r,int fy,int v)
    {
        if (l == r)
        {
            MAX(rt[nx][n],v);
            return;
        }
        int m = (l+r)>>1;
        if (fy <= m) update_y((n<<1),l,m,fy,v);
        else update_y((n<<1)+1,m+1,r,fy,v);
        rt[nx][n] = max(rt[nx][(n<<1)],rt[nx][(n<<1)+1]);
    }

我很抱歉，如果代码是一个烂摊子，因为这是我第一次实施范围树

我目前的实施运行约4秒，但我需要它来运行不到3秒，这是我全面实施

谢谢 ：）

文章来源: 2D RMQ Range Tree