Q-tree.cpp

#include <bits/stdc++.h>

using namespace std;

#define Max 506
#define INF (1 << 30)
int P[Max][Max]; // container for 2D grid

/* 2D Segment Tree node */
struct Point {
	int x, y, mx;
	Point() {}
	Point(int x, int y, int mx) : x(x), y(y), mx(mx) {}

	bool operator < (const Point& other) const {
		return mx < other.mx;
	}
};

struct Segtree2d {
	Point T[2 * Max * Max];
	int n, m;

	// initialize and construct segment tree
	void init(int n, int m) {
		this->n = n;
		this->m = m;
		build(1, 1, 1, n, m);
	}

	// build a 2D segment tree from data [ (a1, b1), (a2, b2) ]
	// Time: O(n logn)
	Point build(int node, int a1, int b1, int a2, int b2) {
		// out of range
		if (a1 > a2 or b1 > b2)
			return def();

		// if it is only a single index, assign value to node
		if (a1 == a2 and b1 == b2)
			return T[node] = Point(a1, b1, P[a1][b1]);

		// split the tree into four segments
		T[node] = def();
		T[node] = maxNode(T[node], build(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2));
		T[node] = maxNode(T[node], build(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2));
		T[node] = maxNode(T[node], build(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2));
		T[node] = maxNode(T[node], build(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2));
		return T[node];
	}

	// helper function for query(int, int, int, int);
	Point query(int node, int a1, int b1, int a2, int b2, int x1, int y1, int x2, int y2) {
		// if we out of range, return dummy
		if (x1 > a2 or y1 > b2 or x2 < a1 or y2 < b1 or a1 > a2 or b1 > b2)
			return def();

		// if it is within range, return the node
		if (x1 <= a1 and y1 <= b1 and a2 <= x2 and b2 <= y2)
			return T[node];

		// split into four segments
		Point mx = def();
		mx = maxNode(mx, query(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, x1, y1, x2, y2));
		mx = maxNode(mx, query(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, x1, y1, x2, y2));
		mx = maxNode(mx, query(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, x1, y1, x2, y2));
		mx = maxNode(mx, query(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, x1, y1, x2, y2));

		// return the maximum value
		return mx;
	}

	// query from range [ (x1, y1), (x2, y2) ]
	// Time: O(logn)
	Point query(int x1, int y1, int x2, int y2) {
		return query(1, 1, 1, n, m, x1, y1, x2, y2);
	}

	// helper function for update(int, int, int);
	Point update(int node, int a1, int b1, int a2, int b2, int x, int y, int value) {
		if (a1 > a2 or b1 > b2)
			return def();

		if (x > a2 or y > b2 or x < a1 or y < b1)
			return T[node];

		if (x == a1 and y == b1 and x == a2 and y == b2)
			return T[node] = Point(x, y, value);

		Point mx = def();
		mx = maxNode(mx, update(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, x, y, value));
		mx = maxNode(mx, update(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, x, y, value));
		mx = maxNode(mx, update(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, x, y, value));
		mx = maxNode(mx, update(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, x, y, value));
		return T[node] = mx;
	}

	// update the value of (x, y) index to 'value'
	// Time: O(logn)
	Point update(int x, int y, int value) {
		return update(1, 1, 1, n, m, x, y, value);
	}

	// utility functions; these functions are virtual because they will be overridden in child class
	virtual Point maxNode(Point a, Point b) {
		return max(a, b);
	}

	// dummy node
	virtual Point def() {
		return Point(0, 0, -INF);
	}
};

/* 2D Segment Tree for range minimum query; a override of Segtree2d class */
struct Segtree2dMin : Segtree2d {
	// overload maxNode() function to return minimum value
	Point maxNode(Point a, Point b) {
		return min(a, b);
	}

	Point def() {
		return Point(0, 0, INF);
	}
};

// initialize class objects
Segtree2d Tmax;
Segtree2dMin Tmin;


/* Drier program */
int main(void) {
	int n, m;
	// input
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &P[i][j]);

	// initialize
	Tmax.init(n, m);
	Tmin.init(n, m);

	// query
	int x1, y1, x2, y2;
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

	cout << Tmax.query(x1, y1, x2, y2).mx;
	Tmin.query(x1, y1, x2, y2).mx;

	// update
	int x, y, v;
	scanf("%d %d %d", &x, &y, &v);
	Tmax.update(x, y, v);
	Tmin.update(x, y, v);

	return 0;
}