二维线段树单点更新+区间最值模板（以UVA11297为例）

一时失言乱红尘 2022-04-22 03:38 230阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：给你一个n\*n的矩阵，有m个询问，q x1 y1 x2 y2 查询这个子矩阵的最大值和最小值，c x y v是将x，y点的值改成c。   分析：二维线段树裸题，留作板子。二维线段树就是在一棵线段树的每一个节点，都保存着另一棵线段树的根节点编号。注意更新操作，稍微有点复杂，给个图解。可以结合代码理解，代码在关键地方写了注释。（感谢xbb的指导） ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

##    代码： ##

#include<algorithm>
    #include<cstdio>
    using namespace std;
    const int N = 1500;
    const int inf=1e8;
    
    int n,q,mx[N][N],mi[N][N];
    int fg,xo,mians,mxans;
    
    void upd2(int l,int r,int o,int y,int v) {
        if(l==r) {///如果找到了二维下标
            if(fg) mi[xo][o]=v,mx[xo][o]=v;///如果此时正好找到了一维下标，就赋值
            else {///否则更新一维的情况
                mi[xo][o]=min(mi[2*xo][o],mi[2*xo+1][o]);
                mx[xo][o]=max(mx[2*xo][o],mx[2*xo+1][o]);
            }
            return ;
        }
        int m=(l+r)/2;
        if(y<=m) upd2(l,m,2*o,y,v);
        else upd2(m+1,r,2*o+1,y,v);
        mi[xo][o]=min(mi[xo][2*o],mi[xo][2*o+1]);///递归回来更新二维情况
        mx[xo][o]=max(mx[xo][2*o],mx[xo][2*o+1]);
    }
    
    ///更新一维，x为要更新的一维下标，y为要更新的二维下标
    void upd1(int l,int r,int o,int x,int y,int v) {
        if(l==r) {
            fg=1;///打上标记
            xo=o;
            upd2(1,n,1,y,v);
            return ;
        }
        int m=(l+r)/2;
        if(x<=m) upd1(l,m,2*o,x,y,v);
        else upd1(m+1,r,2*o+1,x,y,v);
        fg=0,xo=o;
        upd2(1,n,1,y,v);
    }
    
    void qy2(int l,int r,int o,int pre,int ly,int ry) {
        if(ly<=l&&ry>=r) {
            mians=min(mians,mi[pre][o]);
            mxans=max(mxans,mx[pre][o]);
            return ;
        }
        int m=(l+r)/2;
        if(ly<=m) qy2(l,m,2*o,pre,ly,ry);
        if(ry>m) qy2(m+1,r,2*o+1,pre,ly,ry);
    }
    
    void qy1(int l,int r,int o,int lx,int rx,int ly,int ry) {
        if(lx<=l&&rx>=r) {
            qy2(1,n,1,o,ly,ry);
            return ;
        }
        int m=(l+r)/2;
        if(lx<=m) qy1(l,m,2*o,lx,rx,ly,ry);
        if(rx>m) qy1(m+1,r,2*o+1,lx,rx,ly,ry);
    }
    
    int main() {
        scanf("%d",&n);
        int v;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&v),upd1(1,n,1,i,j,v);
        scanf("%d",&q);
        while(q--) {
            char op[2];
            scanf("%s",op);
            int x,y,x1,y1;
            if(op[0]=='q') {
                scanf("%d%d%d%d",&x,&y,&x1,&y1);
                mians=inf;
                mxans=0;
                qy1(1,n,1,x,x1,y,y1);
                printf("%d %d\n",mxans,mians);
            }else {
                scanf("%d%d%d",&x,&y,&v);
                upd1(1,n,1,x,y,v);
            }
        }
        return 0;
    }

[Link 1]: https://vjudge.net/problem/UVA-11297
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220422/dc55ffd698ff4bff9d33a6aa2f4e3da8.png