线段树套线段树

我的第一颗树套树

       树套树的思路估计都这样子了，树套树分为外树和内树，也可以分为第一维树和 第二维树，我这里把他们叫做x树和y树，即x树为外树，y树为内树。我们描述时 用内外，代码用xy。
       首先树套树，顾名思义，给出定义，树套树是一棵节点是树的树。
       于是作为一棵树,他有这些函数：
             建树build，更新update，查询query
       一个一个来说

建树

       建树先建外层树，递归建树，递归出口为当前外树所代表的只有一行， 他是叶子结点树，这时调用建内层树，并退出函数，回溯时，意味着此时 是非叶子节点树，意味着外树所代表的不止一行， 意味着此节点树的儿子 节点树以经建立完成，此时我们调用建 内层树，
       建树建内层树，依旧递归，和一维线段树相比，只是递归出口有所区别， 建内层树时，如果该树为叶子节点树，直接处理，但是当他为非叶节点树 的时候要注意，此时不能直接对当前节点（不是节点树，是节点树的递归 出口所对应的节点）修改值，而是借助上诉结论“意味着此节点树的儿子 节点树以经建立完成”，我们可以通过跨越树来更新值，
       这里有点难以理解，其实仔细的想想，我们建立的虽然说是一颗二维的 二叉树，两颗内树之间的关系确并不是我们想象的那么简单，举个例子， 如果mi[i][j]记录了外树节点树i对应的内树节点j的数据，那么mi[i][j]只能 由mi[i][j<<1]和mi[i][j<<1|1]推过来吗,这里显然不对,如果细心点,我们会发现 我们建立的并不是简单的二维树,它更是一个超级复杂的图,我们站在更高的 角度上看,mi[i<<1][j]和mi[i<<1|1][j]又何尝不能作为mi[i][j]的后继呢?
       于是我们就有了通过mi[i<<1][j]和mi[i<<1|1][j]来更新值的做法,跨越树,用另一棵树 来更新自己,ok? 于是建树完成.

更新

       和建树是一样的

查询

       查询的话就简单很多了，不需要跨越树就能完成，这个的依据是区间的可加性


这只是一颗单点修改，区间最值查询的树

#define pii pair<int,int>
struct segment{
    static const int maxn=1000;
    int ma[maxn<<2][maxn<<2],mi[maxn<<2][maxn<<2];
    int tmp[maxn][maxn];
    int lenx,leny;
    //x为行 y为列
    
    void build(int n){
        lenx=leny=n;
        build_x(1,n,1);
    }
    void build_x(int x1,int x2,int rtx){
        if(x1==x2){
            build_y(x1,x2,1,leny,rtx,1);
            return;
        }
        int midx=(x1+x2)>>1;
        build_x(x1,midx,rtx<<1);
        build_x(midx+1,x2,rtx<<1|1);
        
        build_y(x1,x2,1,leny,rtx,1);
    }
    void build_y(int x1,int x2,int y1,int y2,int rtx,int rty){
        if(y1==y2){
            if(x1==x2){
                mi[rtx][rty]=tmp[x1][y1];
                ma[rtx][rty]=tmp[x1][y1];
            }else{
                mi[rtx][rty]=min(mi[rtx<<1][rty],mi[rtx<<1|1][rty]);
                ma[rtx][rty]=max(ma[rtx<<1][rty],ma[rtx<<1|1][rty]);
            }
            return;
        }
        int midy=(y1+y2)>>1;
        build_y(x1,x2,y1,midy,rtx,rty<<1);
        build_y(x1,x2,midy+1,y2,rtx,rty<<1|1);
        
        mi[rtx][rty]=min(mi[rtx][rty<<1],mi[rtx][rty<<1|1]);
        ma[rtx][rty]=max(ma[rtx][rty<<1],ma[rtx][rty<<1|1]);
    }
    
    
    void update(int x,int y,int d){
        update_x(x,y,d,1,lenx,1);
    }
    void update_x(int x,int y,int d,int x1,int x2,int rtx){
        if(x1==x2){
            update_y(y,d,x1,x2,1,leny,rtx,1);
            return;
        }
        int midx=(x1+x2)>>1;
        if(x<=midx)update_x(x,y,d,x1,midx,rtx<<1);
        else update_x(x,y,d,midx+1,x2,rtx<<1|1);
        update_y(y,d,x1,x2,1,leny,rtx,1);
    }
    void update_y(int y,int d,int x1,int x2,int y1,int y2,int rtx,int rty){
        if(y1==y2){
            if(x1==x2){
                mi[rtx][rty]=d;
                ma[rtx][rty]=d;
            }else{
                mi[rtx][rty]=min(mi[rtx<<1][rty],mi[rtx<<1|1][rty]);
                ma[rtx][rty]=max(ma[rtx<<1][rty],ma[rtx<<1|1][rty]);
            }
            return;
        }
        int midy=(y1+y2)>>1;
        if(y<=midy)update_y(y,d,x1,x2,y1,midy,rtx,rty<<1);
        else update_y(y,d,x1,x2,midy+1,y2,rtx,rty<<1|1);
        mi[rtx][rty]=min(mi[rtx][rty<<1],mi[rtx][rty<<1|1]);
        ma[rtx][rty]=max(ma[rtx][rty<<1],ma[rtx][rty<<1|1]);
    }
    
    
    pii query(int qx1,int qx2,int qy1,int qy2){
        return query_x(qx1,qx2,qy1,qy2,1,lenx,1);
    }
    pii getpii(pii a,pii b){
        return pii(min(a.first,b.first),max(a.second,b.second));
    }
    pii query_x(int qx1,int qx2,int qy1,int qy2,int x1,int x2,int rtx){
        if(qx1<=x1&&x2<=qx2){
            return query_y(qy1,qy2,1,leny,rtx,1);
        }
        
        pii ret=pii(2e9,0);
        int midx=(x1+x2)>>1;
        if(midx>=qx1)ret=getpii(ret,query_x(qx1,qx2,qy1,qy2,x1,midx,rtx<<1));
        if(midx+1<=qx2)ret=getpii(ret,query_x(qx1,qx2,qy1,qy2,midx+1,x2,rtx<<1|1));
        return ret;
    }
    pii query_y(int qy1,int qy2,int y1,int y2,int rtx,int rty){
        if(qy1<=y1&&y2<=qy2){
            return pii(mi[rtx][rty],ma[rtx][rty]);
        }
        
        pii ret(2e9,0);
        int midy=(y1+y2)>>1;
        if(midy>=qy1)ret=getpii(ret,query_y(qy1,qy2,y1,midy,rtx,rty<<1));
        if(midy+1<=qy2)ret=getpii(ret,query_y(qy1,qy2,midy+1,y2,rtx,rty<<1|1));
        return ret;
    }
}tree;