درخت بازه‌ها

درخت‌ها قسمت بزرگی از داده‌ساختارهای علم کامپیوتر را پوشش می‌دهند. درخت در حالت کلی به گراف هم‌بندی گفته می‌شود که دور ندارد.

درخت ریشه‌دار درختی است، که در آن بین رأس‌ها رابطهٔ پدر و فرزندی وجود دارد (ساختاری شبیه شجره‌نامه دارد).

درخت بازه‌ها، درختی ریشه‌دار است که هر رأس غیر برگ آن دقیقاً دو فرزند دارد. در این درخت هر رأس نشان‌دهندهٔ یک بازه است. برگ‌ها در این درخت نشان‌دهندهٔ بازه‌هایی به طول یک هستند. رئوس غیر برگ همگی دو فرزند دارند؛ اگر بازهٔ نسبت‌داده‌شده به فرزندان چپ و راست به ترتیب ${\displaystyle [a,b)}$

اردر همهٔ کارها در این داده‌ساختار (${\displaystyle log(n}$

۱- اگر p برابر P و q برابر Q باشد بازه پیدا شده و عمل مورد نظر را انجام بده (پایان جستجو).

۲- اگر بازهٔ مورد نظر با هر دو فرزند تداخل داشت: به دنبال ${\displaystyle [p,mid)}$

۳- اگر بازهٔ مورد نظر فقط با یکی از فرزندان تداخل داشت: به دنبال ${\displaystyle [p,q)}$

به نظر می‌رسد ممکن است حالت دوم تکرار شود و تمام رئوس را پیمایش کنیم، در صورتی که به سادگی می‌توان دریافت اگر یک بار حالت دوم رخ دهد (هر دو فرزند را پیمایش کنیم) آنگاه در هیچ مرحلهٔ دیگری لازم نیست هر دو انتهای بازه را بررسی کنیم. چرا که از یک طرف بازهٔ ما به ابتدا یا انتها چسبیده و اگر دو قسمت را بررسی کنیم یکی از دو قسمت درجا به شرط پایان می‌رسد.

void find(int p,int q,node x,int P,int Q){
	if(p==P && q==Q){
		//found and do the query
		return;
	}
	int mid=(P+Q)/2;
	if(q<=mid){
		find(p,q,x.left,P,mid);
	}else if(p>=mid){
		find(p,q,x.right,mid,Q);
	}else{
		find(p,mid,x.left,P,mid);
		find(mid,q,x.right,mid,Q);
	}
}

و این هم یک کد ساده که دو عمل تبدیل تمامی اعداد یک بازه به یک عدد و پیدا کردن بزرگترین عدد یک بازه را پشتیبانی می‌کند.

const int N = 1000 * 100 + 5;
class segment{
	int v[4*N], P[4*N], Q[4*N], mrk[4*N];
public:
	void build(int x,int p,int q){
		P[x] = p, Q[x] = q;
		if(p == q) return ;
		int m = (p + q)>> 1;
		build(x <<1,p,m);
		build((x <<1) + 1,m + 1,q);
	}
	inline void mpas(int x){
		if(mrk[x]){
			mrk[x] = 0;
			if(P[x] == Q[x]) return ;
			mrk[x <<1] = mrk[(x <<1) + 1] = 1;
			v[x <<1] = v[(x <<1) + 1] = v[x];
		}
	}
	void change(int x,int p,int q,int val){
		mpas(x);
		if(p <= P[x] && Q[x] <= q){
			mrk[x] = 1;
			v[x] = val;
			return ;
		}
		if(Q[x] <p || P[x]> q)
			return ;
		change(x <<1,p,q,val);
		change((x <<1) + 1,p,q,val);
		v[x] = max(v[x <<1],v[(x <<1) + 1]);
	}
	int find_max(int x,int p,int q){
		mpas(x);
		if(p <= P[x] && Q[x] <= q)
			return v[x];
		if(Q[x] <p || P[x]> q)
			return -INF;
		return max(find_max(x <<1,p,q), find_max((x <<1) + 1,p,q) );
	}
};

• درخت‌های بازه‌ای دوبعدی نیز وجود دارند. یعنی بازه‌های یک بعدی تبدیل به یک زیر مستطیل می‌شوند. در این حالت هر رأس نشان‌دهندهٔ یک مستطیل است که طول و عرض آن توانی از دو است. در حالت کلی می‌توان گفت درخت بازه‌ای دوبعدی یک درخت بازه‌ای معمولی است که هر رأس آن ریشهٔ یک درخت بازه‌ای است و هر راس دو پدر دارد.
• نوع دیگری درخت بازه‌ای به نام درخت فنویک هم وجود دارد.

1. ^  Segment Tree
2. ^  رأس‌هایی که درجهٔ آن‌ها یک است، برگ نامیده می‌شوند.
3. ^  Fenwick Tree

کتاب داده ساختارها و مبانی الگوریتم‌ها (دکتر قدسی)

دورهٔ المپیاد کامپیوتر ۱۷ (inoi 17)

• مقاله‌ای در مورد درخت بازه‌ها در TopCoder (به زبان انگلیسی)
• درس درخت بازه‌ها در خبرگاه المپیاد کامپیوتر (به زبان فارسی)
• http://www.algorithmist.com/index.php/Fenwick_tree