[uva 11297] Census: 二维线段树

写一个数据结构, 维护一个n*n矩阵, 支持单点修改, 子矩阵最值查询. (n ≤ 100) 所谓二维线段树就是先按行建线段树 (x树) , 每个结点[x1, x2]是一棵按列建的线段树 (y树), 其中[y1, y2]表示y1~y2列, 行x1~x2的信息. 也就是说, 把x1~x2行同一列的信息压为一个数.

代码会有点长, 因为要写两个build, 两个query, 两个modify.

• query: 在x树中分解区间, 查询分解出来的y树. y树的写法和一维线段树相同.

• modify: 在x树中找到对应的行, 修改该行的y树. x树中真包含该行的结点也需要修改, 由两个子区间的y树合并得到. 也可以仅在叶子处合并, 非叶子结点像普通一维线段树一样处理.

• build: 和modify相似, 只是不在x树中定位某个特定的点.

合并信息可以重载运算符 (比如+号), 使代码简洁. 引入bits/stdc++.h之后, y1会和cmath里的y1冲突, 所以需要define一下. 需要传的参数挺多, 虽然消灭全局变量比较安全......那就把它们装到namespace里.

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define y1 y1_
using namespace std;
const int N = 500, inf = 1e9 + 1;

int n, a[N+1][N+1];

namespace S {
	struct Data {
		int mn, mx;
		Data(int mn=inf, int mx=-1): mn(mn), mx(mx) {}
		Data operator+(const Data& d)
		{
			return Data(min(mn, d.mn), max(mx, d.mx));
		}
	} d[4*N][4*N], ans;
	int x, y, x1, y1, x2, y2;

	void build_c(Data* D, int o, int l, int r, Data* L=0, Data* R=0)
	{
		if (l == r)
			D[o] = L ? L[o] + R[o] : Data(a[x][l], a[x][l]);
		else {
			int m = (l+r)/2;
			build_c(D, o*2, l, m, L, R);
			build_c(D, o*2+1, m+1, r, L, R);
			D[o] = D[o*2] + D[o*2+1];
		}
	}

	void build_r(int o, int l, int r)
	{
		if (l == r)
			x = l, build_c(d[o], 1, 1, n);
		else {
			int m = (l+r)/2;
			build_r(o*2, l, m);
			build_r(o*2+1, m+1, r);
			build_c(d[o], 1, 1, n, d[o*2], d[o*2+1]);
		}
	}

	void query_c(Data* D, int o, int l, int r)
	{
		if (y1 <= l && r <= y2)
			ans = ans + D[o];
		else {
			int m = (l+r)/2;
			if (y1 <= m)
				query_c(D, o*2, l, m);
			if (y2 > m)
				query_c(D, o*2+1, m+1, r);
		}
	}

	void query_r(int o, int l, int r)
	{
		if (x1 <= l && r <= x2)
			query_c(d[o], 1, 1, n);
		else {
			int m = (l+r)/2;
			if (x1 <= m)
				query_r(o*2, l, m);
			if (x2 > m)
				query_r(o*2+1, m+1, r);
		}
	}

	void modify_c(Data* D, int o, int l, int r, Data* L=0, Data* R=0)
	{
		if (l == r)
			D[o] = L ? L[o] + R[o] : Data(a[x][y], a[x][y]);
		else {
			int m = (l+r)/2;
			if (y <= m)
				modify_c(D, o*2, l, m, L, R);
			else
				modify_c(D, o*2+1, m+1, r, L, R);
			D[o] = D[o*2] + D[o*2+1];
		}
	}

	void modify_r(int o, int l, int r)
	{
		if (l == r)
			modify_c(d[o], 1, 1, n);
		else {
			int m = (l+r)/2;
			if (x <= m)
				modify_r(o*2, l, m);
			else
				modify_r(o*2+1, m+1, r);
			modify_c(d[o], 1, 1, n, d[o*2], d[o*2+1]);
		}
	}
}

int main()
{
	using namespace S;
	scanf("%d", &n);
	For (i, 1, n) For (j, 1, n) scanf("%d", &a[i][j]);
	build_r(1, 1, n);
	int q;
	scanf("%d", &q);
	while (q--) {
		char op;
		int v;
		scanf(" %c", &op);
		if (op == 'q') {
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			ans = Data();
			query_r(1, 1, n);
			printf("%d %d\n", ans.mx, ans.mn);
		} else {
			scanf("%d%d%d", &x, &y, &v);
			a[x][y] = v;
			modify_r(1, 1, n);
		}
	}
	return 0;
}