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

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

题目：点击打开链接题意：给你一个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;
}