二维线段树模板

以你之姓@ 2022-04-22 02:26 241阅读 0赞

--------------------

## title: 二维线段树模板   date: 2018-10-31 15:21:44   tags:   \- 二维线段树   categories: “算法” ##

这个模板是根据HDU-4819编写的。功能是用二维线段树进行

二维点修改和区间查询最小者和最大值。

二维线段树的思想跟一维一样，只不过一维是二分二叉树，二维

是四分四叉树。具体实现看代码。

#include<bits/stdc++.h>
    using namespace std;
    const int LOGN = 10;
    const int MAXN = (1<<LOGN);
    const int MAXNODES = (3*(1<<(2*LOGN)) + 100);
    const int MAX_VAL = 0x3f3f3f3f;
    const int MIN_VAL = -0x3f3f3f3f;
    #define son(x) (p*4-2+x)
    //表示最大值，最小值信息的结构体
    struct dataInfo{
        short posx, posy;
        int val;
        dataInfo(){
            posx = posy = val = -1;
        }
    
        dataInfo(short _posx, short _posy, int _val){
            posx=_posx;
            posy=_posy;
            val=_val;
        }
    
    };
    //树的节点
    struct treeNode{
        dataInfo maxv, minv;
        void reset(){
            maxv = dataInfo(0, 0, INT_MIN);
            minv = dataInfo(0, 0, INT_MAX);
        }
    }nodes[MAXNODES];
    //得到节点的指针
    treeNode* getNode(int id){
        return &nodes[id];
    }
    //表示x、y的范围
    struct Interval{
        int l, r;
        Interval(){}
        Interval(int _l, int _r){
            l=_l; r=_r;
        }
        int mid(){
            return (l+r)>>1;
        }
        int len(){
            return r-l+1;
        }
        Interval left(){
            return Interval(l, mid());
        }
        Interval right(){
            return Interval(mid()+1, r);
        }
        bool isIntersectWith(Interval& tarI){//判断两区间是否相交
            return !(l>tarI.r || r<tarI.l);
        }
        bool isInclude(Interval& tarI){//是否包含tarI区间
            return l<=tarI.l && tarI.r<=r;
        }
        bool in(int v){//是否包含v点
            return l<=v && v<=r;
        }
    
    };
    //建树
    void build_segtree(int p, Interval xI, Interval yI){
        if(xI.len()<=0 || yI.len()<=0){
            return;
        }
        treeNode* now=getNode(p);
        now->reset();
        if(xI.len() == 1 && yI.len()==1){
            return;
        }
        //分别为左上、右上、左下、右下的矩形区间
        build_segtree( son(0), xI.left(), yI.left() );
        build_segtree( son(1), xI.right(), yI.left() );
        build_segtree( son(2), xI.left(), yI.right() );
        build_segtree( son(3), xI.right(), yI.right() );
    }
    //点修改
    bool insert_segtree(int p, Interval xI, Interval yI, int x, int y, int val){
        if(xI.len() <= 0 || yI.len()<=0){
            return false;
        }
        if(!xI.in(x) || !yI.in(y) ){
            return true;
        }
        treeNode *now = getNode(p);
        if(xI.len()==1 && yI.len()==1){
            now->maxv=now->minv =dataInfo(x, y, val);
            return true;
        }
    
        bool isvalid[4];
        isvalid[0]=insert_segtree( son(0), xI.left(), yI.left(), x, y, val);
        isvalid[1]=insert_segtree( son(1), xI.right(), yI.left(), x, y, val);
        isvalid[2]=insert_segtree( son(2), xI.left(), yI.right(), x, y, val);
        isvalid[3]=insert_segtree( son(3), xI.right(), yI.right(), x, y, val);
    
        now->reset();
    	
        for(int i=0; i<4; i++){
            if(!isvalid[i]) continue;//只对有效的区间修改
            treeNode *sonNode =getNode(son(i));
            now->maxv=sonNode->maxv.val > now->maxv.val?sonNode->maxv : now->maxv;
            now->minv=sonNode->minv.val < now->minv.val?sonNode->minv : now->minv;
        }
        return true;
    }
    
    void query_segtree(int p, Interval xI, Interval yI, Interval tarXI, Interval tarYI, treeNode& ans){
    
        if(xI.len()<=0 || yI.len()<=0){
            return;
        }
        if(!tarXI.isIntersectWith(xI) || !tarYI.isIntersectWith(yI) ){
            return;
        }
        treeNode *now=getNode(p);
    
        if(ans.maxv.val>=now->maxv.val && ans.minv.val<=now->minv.val){
            return;
        }
    
        if(tarXI.isInclude(xI) && tarYI.isInclude(yI)){
            ans.maxv.val=max(ans.maxv.val, now->maxv.val);
            ans.minv.val=min(ans.minv.val, now->minv.val);
            return;
        }
        query_segtree( son(0), xI.left(), yI.left(), tarXI, tarYI, ans );
        query_segtree( son(1), xI.right(), yI.left(), tarXI, tarYI, ans );
        query_segtree( son(2), xI.left(), yI.right(), tarXI, tarYI, ans );
        query_segtree( son(3), xI.right(), yI.right(), tarXI, tarYI, ans );
    }
    
    int main(){
        int T, n, tmp, cas=0;
        scanf("%d", &T);
    
        while(T--){
            scanf("%d", &n);
    
            build_segtree(1, Interval(1, n), Interval(1, n));
            int tmp;
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    scanf("%d", &tmp);
                    insert_segtree(1, Interval(1, n), Interval(1, n), i, j, tmp);
                }
            }
    
            int m, x, y, sz;
            scanf("%d", &m);
            printf("Case #%d:\n", ++cas);
            while(m--){
                scanf("%d%d%d", &x, &y, &sz);
                Interval XI, YI;
                XI.l=max(1, x-sz/2), XI.r=min(n, x+sz/2);
                YI.l=max(1, y-sz/2), YI.r=min(n, y+sz/2);
    
                treeNode ans; ans.reset();
    
                query_segtree( 1, Interval(1, n), Interval(1, n), XI, YI, ans);
    
                printf("%d\n", (ans.maxv.val+ans.minv.val)/2);
                insert_segtree(1, Interval(1, n), Interval(1, n), x, y, (ans.maxv.val+ans.minv.val)/2);
            }
    
        }
    
        return 0;
    }

上面是借鉴的网上的写法，因为他将各种都进行了封装，所以比较好理解。自己感觉竞赛还是简练一点比较好，下面代码是自己修改的。

#include<bits/stdc++.h>
    using namespace std;
    const int N=810;
    #define son(x) (rt*4-2+x)
    
    struct node{
        int mx, mn;
        void reset(){
            mx=INT_MIN;
            mn=INT_MAX;
        }
    }tree[(N<<2)*(N<<2)];
    
    void build(int rt, int xl, int xr, int yl, int yr){
        if(xl>xr || yl>yr) return;
        tree[rt].reset();
        if(xl==xr&&yl==yr)
            return;
        int midx=(xl+xr)>>1, midy=(yl+yr)>>1;
        build(son(0), xl, midx, yl, midy);
        build(son(1), xl, midx, midy+1, yr);
        build(son(2), midx+1, xr, yl, midy);
        build(son(3), midx+1, xr, midy+1, yr);
    }
    //push_up完全可以放在跟新里面 写起来更简洁
    void push_up(int rt, int xl, int xr, int yl, int yr){
        node& now=tree[rt];
        now.reset();
        now.mx=max(now.mx, tree[son(0)].mx);
        now.mn=min(now.mn, tree[son(0)].mn);
        if(yl<yr){
            now.mx=max(now.mx, tree[son(1)].mx);
            now.mn=min(now.mn, tree[son(1)].mn);
        }
        if(xl<xr){
            now.mx=max(now.mx, tree[son(2)].mx);
            now.mn=min(now.mn, tree[son(2)].mn);
        }
        if(xl<xr && yl<yr){
            now.mx=max(now.mx, tree[son(3)].mx);
            now.mn=min(now.mn, tree[son(3)].mn);
        }
    }
    
    //point update
    void upd(int rt, int xl, int xr, int yl, int yr, int x, int y, int val){
        if(xl>xr || yl>yr) return;
    
        node& now=tree[rt];
        if(xl==xr&&xl==x && yl==yr&&yl==y){
            now.mx=val;
            now.mn=val;
            return;
        }
        int midx=(xl+xr)>>1, midy=(yl+yr)>>1;
    
        if(x<=midx && y<=midy){
            upd(son(0), xl, midx, yl, midy, x, y, val);
        }
        else if(x<=midx && y>midy){
            upd(son(1), xl, midx, midy+1, yr, x, y, val);
        }
        else if(x>midx && y<=midy){
            upd(son(2), midx+1, xr, yl, midy, x, y, val);
        }
        else{
            upd(son(3), midx+1, xr, midy+1, yr, x, y, val);
        }
    
        push_up(rt, xl, xr, yl, yr);
    }
    //interval query
    node query(int rt, int xl, int xr, int yl, int yr, int qxl, int qxr, int qyl, int qyr){
        node tmp; tmp.reset();
        if(xl>xr || yl>yr) return tmp;
        if(xl>qxr || qxl>xr || yl>qyr || qyl>yr) return tmp;
      
        if(qxl<=xl && xr<=qxr && qyl<=yl && yr<=qyr){
            return tree[rt];
        }
        int midx=(xl+xr)>>1, midy=(yl+yr)>>1;
        node ret; ret.reset();
        if(qxl<=midx && qyl<=midy){
            tmp=query(son(0), xl, midx, yl, midy, qxl, qxr, qyl, qyr);
            ret.mx=max(ret.mx, tmp.mx);
            ret.mn=min(ret.mn, tmp.mn);
        }
        if(qxl<=midx && qyr>midy){
            tmp=query(son(1), xl, midx, midy+1, yr, qxl, qxr, qyl, qyr);
            ret.mx=max(ret.mx, tmp.mx);
            ret.mn=min(ret.mn, tmp.mn);
        }
        if(qxr>midx && qyl<=midy){
            tmp=query(son(2), midx+1, xr, yl, midy, qxl, qxr, qyl, qyr);
            ret.mx=max(ret.mx, tmp.mx);
            ret.mn=min(ret.mn, tmp.mn);
        }
        if(qxr>midx && qyr>midy){
            tmp=query(son(3), midx+1, xr, midy+1, yr, qxl, qxr, qyl, qyr);
            ret.mx=max(ret.mx, tmp.mx);
            ret.mn=min(ret.mn, tmp.mn);
        }
    
        return ret;
    }
    
    int main(){
    
        int T, n, cas=0;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
    
            build(1, 1, n, 1, n);
            int tmp;
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    scanf("%d", &tmp);
                    upd(1, 1, n, 1, n, i, j, tmp);
                }
            }
    
            int m, x, y, sz;
            scanf("%d", &m);
            printf("Case #%d:\n", ++cas);
            while(m--){
                scanf("%d%d%d", &x, &y, &sz);
                int qxl=max(1, x-sz/2), qxr=min(n, x+sz/2);
                int qyl=max(1, y-sz/2), qyr=min(n, y+sz/2);
                node ans;
               
                ans=query(1, 1, n, 1, n, qxl, qxr, qyl, qyr);
                printf("%d\n", (ans.mn + ans.mx)>>1);
                upd(1, 1, n, 1, n, x, y, (ans.mn+ans.mx)/2);
               
            }
        }
    
        return 0;
    }