درخت‌های پاره‌خطی یک بعدی

فرض کنید آرایه‌ای از عناصر و تعدادی دستور روی بازه‌هایی از آرایه داریم. یکی از رویکردهای متداول در مقابل چنین مسائلی تقسیم کردن بازه‌های موجود به تعداد کمتری بازه است که در هر یک از آن‌ها اطلاعاتی در مورد بازه‌های متناظر ذخیره شده است.

درخت پاره‌خطی یا درخت بازه، درختی است که هر رأس آن متعلق به یک بازه از آرایه است و رأس ریشه آن متناظر با بازه شامل کل آرایه یعنی $[0, n)$ می‌باشد.

هر رأس، ۰ یا ۲ بچه دارد که آن‌ها را بچه راست و چپ می‌نامیم. اگر بازه متناظر با رأس $x$،بازه‌ی $[l, r)$ باشد و بیشتر از یک عنصر در بازه‌ی آن باشد، بازه‌ی متناظر با بچه‌های آن بازه‌های $[l, mid)$ و $[mid, r)$ خواهند بود که $mid=[(l+r)/2]$. بنابراین ارتفاع درخت از $O(log(n))$ خواهد بود

اندیس ریشه‌ی درخت را ۱ در نظر می‌گیریم و اندیس بچه‌های چپ و راست رأس $x$ را به ترتیب $2x$ و $2x+1 $در نظر می‌گیریم. حال برای افراز بازه‌ی داده شده مانند $L = [x, y)$ به بازه‌های درخت بازه‌ای، به این گونه عمل می‌کنیم که بازه‌هایی از درخت که به طور کامل درون L قرار دارند ولی بازه پدر آن‌ها به طور کامل درون L قرار نداشته باشند عضوی از افراز L خواهند بود. به عبارتی دیگر بازه $J=[l, r)$ با بازه پدر $K=[a, b)$ عضو افراز L است اگر و تنها اگر $x ≤ l ≤ r ≤ y$ و در عین حال، $a < l$ یا $r < b$.

Split.cpp

vector<int> s;
void split(int x,int y, int id = 1,int l = 0, int r = n){//	id is the index of the node
	if(x >= r or l >= y)	return ;	// in this case, intersect of [l,r) and [x,y) is empty
	if(x <= l && r <= y){
		s.push_back(id); 
		return ;
	}
	int mid = (l+r)/2;
	split(x,y,id * 2,l,mid);
	split(x,y,id * 2 + 1,mid,r);
}

به عنوان مثال اگر آرایه‌ای به طول n داشته باشیم و دو نوع دستور به ترتیب زیر داشته باشیم

۱- مجموع عناصر موجود در بازه $[l, r)$ را حساب کند.

۲- تغییر مقدار عنصر شماره $p$.

در ابتدا باید درخت بازه‌ای مربوطه را به نحوی بسازیم و مقداردهی اولیه کنیم که برای بازه‌ی با اندیس i در $s[i]$ مقدار مجموع بازه‌ی مربوط به $i$ را ذخیره کنیم.

Build.cpp

	void build(int id = 1,int l = 0,int r = n){
	if(r - l < 2){	//	l + 1 == r
		s[id] = a[l];
		return ;
	}
	int mid = (l+r)/2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid, r);
	s[id] = s[id * 2] + s[id * 2 + 1];
}

بنابراین پیش از اجرای دستورات باید تابع build یک بار صدا شود.

حال برای اجرای دستور نوع دوم کافیست بازه‌های شامل اندیس $p$ را به‌روز رسانی کنیم.

Modify.cpp

void modify(int p,int x,int id = 1,int l = 0,int r = n){
	s[id] += x - a[p];
	if(r - l < 2){	//	l = r - 1 = p
		a[p] = x;
		return ;
	}
	int mid = (l + r)/2;
	if(p < mid)
		modify(p, x, id * 2, l, mid);
	else
		modify(p, x, id * 2 + 1, mid, r);
}

همچنین برای اجرای دستور محاسبه‌ی مجموع بازه‌ی $[l, r)$ کافیست مقدار ذخیره شده برای برای بازه‌هایی که در افراز $[l, r)$ وجود دارند را با هم جمع کنیم که به صورت زیر قابل انجام است.

sum1.cpp

int sum(int x,int y,int id = 1,int l = 0,int r = n){
	if(x >= r or l >= y)	return 0;
	if(x <= l && r <= y)	return s[id];
	int mid = (l+r)/2;
	return sum(x, y, id * 2, l, mid) +
	       sum(x, y, id * 2 + 1, mid, r);
}

انتشار با تأخیر:

حال فرض کنید عملیات دوم از نوع به‌روز رسانی بازه‌‌ای باشد، به گونه‌ای که تغییر داده شده باید بر روی یک بازه اعمال گردد و نه تنها یک عنصر. در این صورت به‌روز رسانی تمامی عناصر بازه داده شده به صورت جداگانه بهینه نخواهد بود. برای حل این مسأله از ترفند انتشار با تأخیر استفاده می‌کنیم؛ بدین‌ترتیب که تنها اطلاعات بازه‌هایی از درخت را به‌روز می‌کنیم که ماکسیمال بوده و کاملا در بازه داده شده باشند و تنها در صورت نیاز در آینده تغییرات را در سطوح پایین‌تر اعمال می‌کنیم. برای این کار آرایه‌ای به عنوان مثال با نام lazy در نظر می‌گیریم که $lazy[i]$ متناظر به رأس درخت با اندیس $i$ خواهد بود. بنابراین تابع build جهت ساخت و مقداردهی اولیه درخت همانند مثال قبل خواهد بود، اما به توابع دیگری جهت ذخیره و انتقال تغییرات نیاز خواهیم داشت.

تابعی جهت به‌روز رسانی یک رأس از درخت:

Update.cpp

void update(int id,int l,int r,int x){//	increase all members in this interval by x
	lazy[id] += x;
	s[id] += (r - l) * x;
}

تابعی جهت انتقال به‌روزرسانی‌ها از رأسی به بچه‌هایش:

Shift.cpp

void shift(int id,int l,int r){//pass update information to the children
	int mid = (l+r)/2;
	update(id * 2, l, mid, lazy[id]);
	update(id * 2 + 1, mid, r, lazy[id]);
	lazy[id] = 0;// passing is done
}

حال اگر دستور نوع دوم را به این صورت تعریف کنیم که بازه $[x, y)$ و مقدار $v$ داده شود تا به تمامی عناصر داخل بازه اضافه شود، تابع افزایش به صورت زیر خواهد بود:

Increase.cpp

void increase(int x,int y,int v,int id = 1,int l = 0,int r = n){
	if(x >= r or l >= y)	return ;
	if(x <= l && r <= y){
		upd(id, l, r, v);
		return ;
	}
	shift(id, l, r);
	int mid = (l+r)/2;
	increase(x, y, v, id * 2, l, mid);
	increase(x, y, v, id*2+1, mid, r);
	s[id] = s[id * 2] + s[id * 2 + 1];
}

و در نهایت جهت نمایش مجموع عناصر یک بازه به صورت زیر عمل می‌کنیم:

sum2.cpp

int sum(int x,int y,int id = 1,int l = 0,int r = n){
	if(x >= r or l >= y)	return 0;
	if(x <= l && r <= y)	return s[id];
	shift(id, l, r);
	int mid = (l+r)/2;
	return sum(x, y, id * 2, l, mid) +
	       sum(x, y, id * 2 + 1, mid, r);
}

در این مطلب یکی از رویکردها به مسائلی که دستورات آنها به صورت سوالاتی در مورد بازه‌های یک آرایه است و عملیات‌های آن‌ها نیز بر روی یک عنصر و یا یک بازه از آرایه انجام می‌شوند را ارائه دادیم که در آن عملیات از نوع افزایش مقادیر و سوالات در مورد مجموع عناصر بازه‌ها بود. اما این رویکرد در بسیاری از مسا‌ئل دیگر که انواع دیگری از عملیات‌ها و پرسش‌های بازه‌ای را مطرح می‌کنند قابل استفاده می‌باشند که بنابر شرایط مسأله نحوه ذخیره‌سازی و به‌روز رسانی اطلاعات در رئوس درخت تعیین خواهد شد.

تمامی توابع پیاده‌سازی شده به صورت پیمایش نخست ژرفا از رأس ریشه تا حداکثر یکی از برگ‌های درخت عمل می‌کنند و در هر رأسی که الگوریتم در دو شاخه ادامه می‌یابد یکی از شاخه‌ها یا به طور کامل درون بازه مطلوب است یا از ابتدا تا بخشی از آن است که در این صورت اطلاعات ذخیره شده در رئوس اجازه‌ی گسترش بیشتر را به الگوریتم نخواهد داد. بنابراین تمامی عملیات‌ها در $((O(log(n$ انجام می‌پذیرد.

• مساله شماره یک از spoj
• مسأله شماره دو از codeforces
• مسأله شماره سه از codeforces

• ویکی‌پدیا