**درخت پاره‌خطی دوبعدی**
مساله‌ای را در نظر بگیرید که در آن تغییر یک خانه‌ از ماتریس ۲ بعدی $n$ در $m$ و پرسش درمورد عنصر کمینه/بیشینه یک زیرماتریس از ماتریس اصلی را داشته باشیم. برای حل این مساله از درخت پاره‌خطی دوبعدی استفاده می‌کنیم.

**ساخت درخت پاره‌خطی دوبعدی**

برای ساخت این درخت، ابتدا روی $n$ سطر ماتریس یک درخت پاره‌خطی یک‌بعدی می‌سازیم که مقدار درون هرراس از این درخت، یک درخت پاره‌خطی یک‌بعدی دیگر با اندازه $m$ عنصر است.
<code c++>
void build_y (int vx, int lx, int rx, int vy, int ly, int ry) {
	if (ly == ry)
		if (lx == rx)
			t[vx][vy] = a[lx][ly];
		else
			t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
	else {
		int my = (ly + ry) / 2;
		build_y (vx, lx, rx, vy*2, ly, my);
		build_y (vx, lx, rx, vy*2+1, my+1, ry);
		t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
	}
}
 
void build_x (int vx, int lx, int rx) {
	if (lx != rx) {
		int mx = (lx + rx) / 2;
		build_x (vx*2, lx, mx);
		build_x (vx*2+1, mx+1, rx);
	}
	build_y (vx, lx, rx, 1, 0, m-1);
}
</code>

میزان حافظه استفاده شده در این داده ساختار‌ همچنان خطی است ولی حدود $16nm$ خانه از حافظه را می‌گیرد.

**عملیات محاسبه**

برای محاسبه عنصر کمینه/بیشینه، ابتدا زیرماتریس داده شده را به تعدادی بازه از سطرها در تبدیل می‌کنیم، هرکدام از این بازه‌ها مقدارشان یک درخت پاره‌خطی است، درون درخت‌ پاره‌خطی متناظر با هر بازه، بازه ستونی زیرماتریس را محاسبه می‌کنیم.
<code c++>
int sum_y (int vx, int vy, int tly, int try_, int ly, int ry) {
	if (ly > ry)
		return 0;
	if (ly == tly && try_ == ry)
		return t[vx][vy];
	int tmy = (tly + try_) / 2;
	return sum_y (vx, vy*2, tly, tmy, ly, min(ry,tmy))
		+ sum_y (vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
}
 
int sum_x (int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
	if (lx > rx)
		return 0;
	if (lx == tlx && trx == rx)
		return sum_y (vx, 1, 0, m-1, ly, ry);
	int tmx = (tlx + trx) / 2;
	return sum_x (vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
		+ sum_x (vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
}
</code> 

چون در ابتدا به $O(logn)$ بازه سطری تبدیل می‌شود و سپس هر بازه به ‌$O(logm)$ بازه ستونی، پس در کل در $O(logn.logm)$ انجام می‌شود.

**تغییر یک عنصر**

تغییر یک عنصر در درخت‌ پاره‌خطی دوبعدی تفاوت زیادی با تغییر آن در درخت پاره‌خطی یک‌بعدی ندارد. در واقع کافیست ابتدا بازه‌های سطری که شامل سطر عنصر تغییر یافته می‌باشند را پیدا کنیم که تعدادشان از $O(logn)$ است، سپس در هر کدام از این‌ها مقدار ستون عنصر تغییر یافته را تغییر دهیم که از $O(logm)$ است. پس در کل این پرسش‌ها نیز از $O(logn.logm)$ انجام می‌شوند.

<code c++>
void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
	if (ly == ry) {
		if (lx == rx)
			t[vx][vy] = new_val;
		else
			t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
	}
	else {
		int my = (ly + ry) / 2;
		if (y <= my)
			update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
		else
			update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
		t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
	}
}
 
void update_x (int vx, int lx, int rx, int x, int y, int new_val) {
	if (lx != rx) {
		int mx = (lx + rx) / 2;
		if (x <= mx)
			update_x (vx*2, lx, mx, x, y, new_val);
		else
			update_x (vx*2+1, mx+1, rx, x, y, new_val);
	}
	update_y (vx, lx, rx, 1, 0, m-1, x, y, new_val);
}
</code>