二维线段树——区间最值系列

二维线段树——区间最值系列

最近这几天学习了一下二维线段树，二维线段树主要有两种写法，四分树和树套树，暂时还没写过四分树，因为这个东西确实不常用，而且不好写也不好调。

树套树的写法思路其实不难，首先我们知道，我们通常的线段树的操作都是在线段上进行的，即一维的，当推广到二维上，即矩阵时，我们就把它叫做二维线段树。

二维线段树其实就是我们再操作时先找到对应x轴的区间（即第一维），之后再找到对应y轴的区间（即第二维），进行相应的操作。

其实就是我们先给x轴上的每个点维护一颗线段树，然后我们再在x轴上的每个点里面再维护一颗线段树记录y轴。其实就是线段树的每一个节点又同时是一颗线段树，很明显的树套树做法。当然挺好理解的，就是码量挺大的，而且空间花销很大，很容易MLE。

给出我的二维线段树（维护子矩阵最值和子矩阵求和和支持单点修改）的代码实现（可以当做模板来用）：

/*注意空间问题二维线段树求区间最值问题（可修）。给你一个n*n的初始矩阵，支持三种操作    单点修改某个位置的值（或者加上一个值）查询子矩阵最小值和最大值，或者查询子矩阵的和测试题目：hdu 4819 && poj 1195
*/
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1024 + 5;
ll MAX[N << 2][N << 2], minV, maxV,MIN[N<<2][N<<2];//维护最值
ll a[N<<2][N<<2];//初始矩阵
ll SUM[N<<2][N<<2],sumV;//维护求和
int n;
void pushupX(int deep, int rt)
{MAX[deep][rt] = max(MAX[deep << 1][rt], MAX[deep << 1 | 1][rt]);MIN[deep][rt] = min(MIN[deep << 1][rt], MIN[deep << 1 | 1][rt]);SUM[deep][rt] = SUM[deep<<1][rt]+SUM[deep<<1|1][rt];
}
void pushupY(int deep, int rt)
{MAX[deep][rt] = max(MAX[deep][rt << 1], MAX[deep][rt << 1 | 1]);MIN[deep][rt] = min(MIN[deep][rt << 1], MIN[deep][rt << 1 | 1]);SUM[deep][rt]=SUM[deep][rt<<1]+SUM[deep][rt<<1|1];
}
void buildY(int ly, int ry, int deep, int rt, int flag)
{//y轴范围ly,ry;deep,rt;标记flagif (ly == ry){if (flag!=-1)MAX[deep][rt] = MIN[deep][rt] = SUM[deep][rt] = a[flag][ly];elsepushupX(deep, rt);return;}int m = (ly + ry) >> 1;buildY(ly, m, deep, rt << 1, flag);buildY(m + 1, ry, deep, rt << 1 | 1, flag);pushupY(deep, rt);
}
void buildX(int lx, int rx, int deep)
{//建树x轴范围lx,rx;deepif (lx == rx){buildY(1, n, deep, 1, lx);return;}int m = (lx + rx) >> 1;buildX(lx, m, deep << 1);buildX(m + 1, rx, deep << 1 | 1);buildY(1, n, deep, 1, -1);
}
void updateY(int Y, int val, int ly, int ry, int deep, int rt, int flag)
{//单点更新y坐标;更新值val;当前操作y的范围ly,ry;deep,rt;标记flagif (ly == ry){if (flag) //注意读清楚题意，看是单点修改值还是单点加值MAX[deep][rt] = MIN[deep][rt] = SUM[deep][rt] = val;else pushupX(deep, rt);return;}int m = (ly + ry) >> 1;if (Y <= m)updateY(Y, val, ly, m, deep, rt << 1, flag);elseupdateY(Y, val, m + 1, ry, deep, rt << 1 | 1, flag);pushupY(deep, rt);
}
void updateX(int X, int Y, int val, int lx, int rx, int deep)
{//单点更新范围x,y;更新值val;当前操作x的范围lx,rx;deepif (lx == rx){updateY(Y, val, 1, n, deep, 1, 1);return;}int m = (lx + rx) >> 1;if (X <= m)updateX(X, Y, val, lx, m, deep << 1);elseupdateX(X, Y, val, m + 1, rx, deep << 1 | 1);updateY(Y, val, 1, n, deep, 1, 0);
}
void queryY(int Yl, int Yr, int ly, int ry, int deep, int rt)
{//询问区间y轴范围y1,y2;当前操作y的范围ly,ry;deep,rtif (Yl <= ly && ry <= Yr){minV = min(MIN[deep][rt], minV);maxV = max(MAX[deep][rt], maxV);sumV += SUM[deep][rt];return;}int m = (ly + ry) >> 1;if (Yl <= m)queryY(Yl, Yr, ly, m, deep, rt << 1);if (m < Yr)queryY(Yl, Yr, m + 1, ry, deep, rt << 1 | 1);
}
void queryX(int Xl, int Xr, int Yl, int Yr, int lx, int rx, int rt)
{//询问区间范围x1,x2,y1,y2;当前操作x的范围lx,rx;rtif (Xl <= lx && rx <= Xr){queryY(Yl, Yr, 1, n, rt, 1);return;}int m = (lx + rx) >> 1;if (Xl <= m)queryX(Xl, Xr, Yl, Yr, lx, m, rt << 1);if (m < Xr)queryX(Xl, Xr, Yl, Yr, m + 1, rx, rt << 1 | 1);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]);buildX(1,n,1);int m;scanf("%d",&m);while(m--){int opt;scanf("%d",&opt);if(opt==1){ //单点修改int x,y,val;scanf("%d%d%d",&x,&y,&val);updateX(x,y,val,1,n,1);}else if(opt==2){//查询子矩阵最值，以及和minV=INF,maxV=-INF,sumV=0;//注意初始化int x1,y1,x2,y2;//注意看清楚给范围的方式以及下标是从0开始还是从1开始scanf("%d%d%d%d",&x1,&y1,&x2,&y2);queryX(x1,x2,y1,y2,1,n,1);printf("%lld %lld %lldn",sumV,minV,maxV);}}return 0;
}
/*
2 
2 2
2 2
3
2 1 1 2 2
1 1 1 5
2 1 1 2 2
*/

下面给出一个我自己拉的在virtual judge上的二维线段树专题的链接：