加载中…
正文 字体大小:

二维线段树 之 矩形树(四分思想) 模板

(2011-06-20 23:45:50)
标签:

acm

二维线段树

矩形树

模板

教育

分类: 数据结构

线段树处理的是线性统计问题,而我们往往会遇到一些平面统计问题和空间统计问题。因此我们需要推广线段树,使它变成能解决平面问题的矩形树和能解决空间问题的方块树

将一维线段树改成二维线段树,有两种方法。一种就是给原来线段树中的每个结点都加多一棵线段树,即树中有树。如下图:

二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板

    例如在主线段树的结点[1,2]中,线段[3,4]表示的就是矩形(1,3,2,4) {注:本文用(x1,y1,x2,y2)表示左下角顶点坐标为(x1,y1),右上角顶点坐标为(x2,y2)的矩形}。容易算出,用这种方法构造一棵矩形(x1,y1,x2,y2)的线段树需要的空间为O(2(x2-x1)*2(y2-y1)),即空间复杂度为O(4*Long_x*Long_y),其中Long_xLong_y分别表示矩形的长和宽。相应地,时间复杂度为二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板


。其中n为操作数。由于这种线段树有两层,处理起来较麻烦。

//时间分析:每次操作,对外层树的操作:O(log2N) ,对内层树的操作:O(log2N)..矩形为N*M..即单次操作:O(log2N*log2N)).

    另一种方式是直接将原来线段树结点中的线段变成矩形。即每个结点代表一个矩形。因此矩形树用的是四分的思想,每个矩形分割为4个子矩形。矩形(x1,y1,x2,y2)4个儿子分别为

二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 (x1,y1,二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 ,二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 )

(二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 ,y1,x2,二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 )

(x1,二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 ,二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 ,y2)

(二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 ,二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板 ,x2,y2)

    例如下图就是一棵以矩形(1,1,4,3)

为根的矩形树:






二维线段树 <wbr>之 <wbr>矩形树(四分思想) <wbr>模板

易知,以(x1,y1,x2,y2)为根的矩形树的空间复杂度也是O(2*Long_x*Long_y)。但由于它只有一层,处理起来比第一种方法方便。而且在这种矩形树中,标记思想依然适用。而第一种方法中,标号思想在主线段树上并不适用,只能在第二层线段树上使用。但是这种方法的时间复杂度可能会达到O(n*Long_x)。比起第一种来就差了不少。

//时间分析: 对于N*N的矩形,要对其中的一个单位矩形进行操作..第一次操作时的矩形面积为N*N,第二次操作时,矩形面积为1/4*N*N..第k次操作时,矩形面积为(1/4)^(k-1)*N*N....直到矩形面积为(1/4)^n * N*N == 1..解这个方程,得 n = logN..(10为底).即O(logN)..而第一种方法,其单次操作为:O(logN*logM)..2为底...每一种方法快半个数量级...

//四分思想,最坏情况,会退化...如果全部更新到叶子,复杂度就退化到了O(n)

对于N*N的矩形树,更新一个叶结点的值,遍历的深度为O(log2N)...所以时间复杂度为O(log2N).....

对于多维的问题,第一种方法几乎不可能使用。因此我们可以仿照第二种方法。例如对于n维的问题。我们构造以(a1,a2,a3,….,an,b1,b2,b3,….,bn)为根的线段树,其中(a1,a2,a3….,an)表示的是左下角的坐标,(b1,b2,b3,….,bn)表示的是右上角的坐标。构造的时候用的就不是二分,四分了,而是2n分,构造出一棵2n叉树。结点的个数变为2n×(b1-a1)×(b2-a2)×………×(bn-an)

 

以上转载自xuemao大牛的论文

 

const int maxn = 1000*1000*1.5;

//2D line tree

struct node

{

    short x1,y1,x2,y2;    //(a,b)--(c,d)    

    float max;

    int *ch;

};

 

node tree[maxn];  //空间:O(N*M * 2)  //实际上,1.4*N*M就足够了

 

int tol;

 

void maketree(int x1,int y1,int x2,int y2)  //时间:O(2*N*M) 空间:O(2*N*M)

{

    tol++;

    int k = tol;

    tree[k].x1 = x1;

    tree[k].y1 = y1;

    tree[k].x2 = x2;

    tree[k].y2 = y2;

    tree[k].max = 0.0;

 

    if(x1==x2 && y1 == y2) //c==d

    {

        tree[k].ch = 0;

        return;

    }

 

    tree[k].ch = new int[4];

 

    int midx = (x1+x2)/2;

    int midy = (y1+y2)/2;

 

    if(x1<=midx && y1 <= midy)  //左下

    {

        tree[k].ch[0] = tol+1;

        maketree(x1,y1,midx,midy);

    }

    else

        tree[k].ch[0] = 0;

 

    if(midx+1 <= x2 && midy+1 <= y2)  //右上

    {

        tree[k].ch[1] = tol+1;

        maketree(midx+1,midy+1,x2,y2);

    }

    else

        tree[k].ch[1] = 0;

   

    if(x1 <= midx && midy+1 <= y2)  //左上

    {

        tree[k].ch[2] = tol+1;

 

        maketree(x1,midy+1,midx,y2);   

    }

    else

        tree[k].ch[2] = 0;

 

    if(midx+1 <= x2 && y1 <= midy) //右下

    {

        tree[k].ch[3] = tol+1;

        maketree(midx+1,y1,x2,midy);

    }

    else

        tree[k].ch[3] = 0;

}

 

//时间:O(logN)//N*N的矩形

void insert(int x,int y,int L,int k) //这里,针对插入的是一个矩形[x,y]--[x,y]..一个单位正方形

{

    if(tree[k].x1 == tree[k].x2 && tree[k].y1 == tree[k].y2) //叶子结点  //

    {

        if(L > tree[k].max)

            tree[k].max = L;

        return;

    }

 

    int midx = (tree[k].x1+tree[k].x2)/2;

    int midy = (tree[k].y1+tree[k].y2)/2;

 

    if(x<=midx)

    {

        if(y<=midy)

            insert(x,y,L,tree[k].ch[0]);

        else

            insert(x,y,L,tree[k].ch[2]);

    }

    else  //x>midx

    {

        if(y<=midy)

            insert(x,y,L,tree[k].ch[3]);

        else

            insert(x,y,L,tree[k].ch[1]);

    }

   

    float m = tree[tree[k].ch[0]].max;

 

    for(int i=1; i<4; i++)

        m = max(m,tree[tree[k].ch[i]].max);

 

    tree[k].max = m;

}

 

 

inline bool corss(int x1,int y1,int x2,int y2,int k) //判断两矩形是否相交

{

    int x3 = tree[k].x1;

    int y3 = tree[k].y1;

    int x4 = tree[k].x2;

    int y4 = tree[k].y2;

 

    if(y2 < y3 || y4 < y1 || x4 < x1 || x2 < x3)

        return false;

    else

        return true;

}

 

//时间:O(logN)//N*N的矩形

float Query(int x1,int y1,int x2,int y2,int k)

{

    if(corss(x1,y1,x2,y2,k) == false || tree[k].max == 0)  //矩形不相交或 矩形内max==0 则直接返回0

        return 0;

 

    if(x1<=tree[k].x1 && y1<=tree[k].y1 && tree[k].x2 <= x2 && tree[k].y2 <= y2) //如果要查询的矩形覆盖了当前矩形..则返回当前矩形的max

        return tree[k].max;

 

    int midx = (tree[k].x1+tree[k].x2)/2;

    int midy = (tree[k].y1+tree[k].y2)/2;

 

    float m[4] = {0,0,0,0};

 

    for(int i=0; i<4; i++)

        m[i] = Query(x1,y1,x2,y2,tree[k].ch[i]);

 

    float mm = m[0];

 

    for(int i=1; i<4; i++)

        mm = max(mm,m[i]);

 

    return mm;

}

 

0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有