درخت فنویک

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

فرض کنید آرایه a به اندازه n که در ابتدا همه مقادیر آن برابر 0 هستند به ما داده شده است، می خواهیم اعمال زیر را روی این آرایه انجام دهیم:

  • به درایه i-ام، x واحد اضافه کن.
  • مجموع اعداد درایه i-ام تا درایه j-ام را به دست بیاور.

یک راه حل ساده برای این مسئله با استفاده از آرایه، به این صورت است که دستور 1 را در (1)O و دستور 2 را در O(n) انجام می دهد. پس اگر m دستور داشته باشیم، در بدترین حالت (زمانی که همه دستورها از نوع دوم باشند)، به زمان O(n*m) احتیاج داریم. با استفاده از داده ساختار درخت فنویک (یا درخت اندیس داده شده دودویی) می توان هر دستور را در O(log n) و در نتیجه کل دستورها را در O(m log n) انجام داد. به طور کلی این اعمال توسط درخت بازه‌ها هم در این زمان انجام می شوند، اما مزیت درخت فنویک در کم بودن حافظه(دقیقاً به اندازه n)، کوتاه بودن کد و همچنین سهولت پیاده سازی آن در ابعاد بیشتر است.

تعریف می کنیم:

  • مجموع درایه‌های اول تا i-ام(فراوانی تراکمی درایه i-ام): c[i]
  • مجموع درایه‌های i-ام تا j-ام: sum[i...j]

یک راه کند دیگر[ویرایش]

این راه حل زمانی که همه دستورهای نوع دوم بعد از دستورات نوع اول باشند، m دستور را در O(n+m) انجام می دهد.

به وضوح: sum[i...j] = c_i - c_{j-1}

بعد از این که همه دستورات نوع اول، مانند راه قبل در O(1) انجام شدند، به صورت پویا مقادیر آرایه c را در O(n) محاسبه میکنیم. بنابر تعریف c[i] = c[i-1] + a[i]  :c

void initialize(){
	c[0] = 0;
	for(int i=1; i<=n; i++)
		c[i] = c[i-1] + a[i];
}

بعد از این مقدار دهی هم مانند بالا می توانیم مقادیر sum را از روی c به دست بیاوریم. پس کل دستورات را در O(n+m) انجام می دهیم. اما اگر دستورات نوع دوم بعد از نوع اول نباشند، بعد از هر دستور نوع اول باید مقادیر آرایه c را به روز کنیم، پس باز هم زمان اجرا در بدترین حالت از O(n*m) می شود.

درخت فنویک[ویرایش]

ساختار[ویرایش]

ایده اصلی این درخت این است که هر عدد طبیعی را می توان به صورت جمع تعدادی از توان‌های ۲ نوشت. به همین ترتیب مجموع یک بازه را می توان به صورت جمع تعدادی زیربازه بدون اشتراک از آن بازه نوشت.

فرض کنید r کوچکترین عددی باشد که بیت r-ام عدد x برابر 1 باشد. تعریف می کنیم:

tree[x] = sum[x-2^r+1 ... x]

tree[0] = 0

(a[i] = عدد i ام آرایه ورودی و c[i] = جمع اولین عدد تا iامین عدد ارایه و tree[i] = جمع اعدادی که در بازه ی نسبت داده شده به عدد i در ارایه قرار دارند.)

مثال: Fenwick tree 162.jpg

پیدا کردن آخرین بیت 1[ویرایش]

فرض کنید می خواهیم کوچکترین بیت عدد P که برابر 1 است را به دست آوریم، P را می توان به صورت x1y نوشت که x برابر بیت‌های قبل از آخرین 1 و y برابر تعدادی 0 است. می خواهیم عدد P- را محاسبه کنیم:

((q)¯ مکمل دوی q میباشد.)

P = (x1y)¯ + 1 = x¯0y¯ + 1 = x¯0(0...0)¯ + 1 = x¯0(1...1) + 1 = x¯1(0...0) = x¯1y- حال اگر از عملگر "و" بیتی بین P , P- استفاده کنیم، خواهیم داشت:

(P & (-P) = (x1y) & (x¯1y) = (x&x¯)1(y&y) = (0…0)1(0…0

بدست آوردن آرایه c از روی آرایه tree[ویرایش]

برای بدست آوردن [c[x ابتدا متغیر sum را برابر [tree[x قرار می دهیم، سپس بیت آخر x را حذف می کنیم و sum را با[tree[x جمع می کنیم، همین کار را تکرار می کنیم تا x برابر 0 شود.

مثال: [c[15] = sum[15] + sum[14]+ sum[12] + sum[8

int c(int x){
	int sum = 0;
	for(; x> 0; x -= x & (-x))
		sum += tree[x];
	return sum;
}

به طور کلی می توانیم بگوییم که در درخت، راس x پدر تمام رئوسی است که با حذف بیت آخرشان به x تبدیل می شوند:

Fenwick tree-16.jpg

بنابر این می توان (c(x را در زمان O(log n) محاسبه کرد، در نتیجه می توان [sum[i...j و همچنین [a[i را نیز در O(log n) بدست آورد.([a[i] = sum[i...i)

به روز کردن مقادیر tree[ویرایش]

بعد از این که به درایه i-ام، مقدار val را اضافه می کنیم، باید به همه [tree[j هایی که i در بازه j قرار می گیرد، مقدار val را اضافه کنیم. برای این کار ابتدا به [tree[i، این مقدار را اضافه میکنیم، سپس کوچکترین بیت 1 در i را به آن اضافه می کنیم و تا زمانی که i<=n باشد این کار را ادامه می دهیم.

void update(int i, int val){
	for(; i<=n; i += i & (-i))
		tree[i] += val;
}

به این ترتیب می توانیم به هر دو دستور در O(log n) جواب دهیم.

پیاده سازی در دو بعد[ویرایش]

به وسیله توابع زیر می توان درخت فنویک را در دو بعد پیاده سازی کرد.

int c(int x, int y){
	int sum = 0;
	for(; x> 0; x -= x & (-x))
		for(int i=y; i> 0 ; i -= i & (-i))
			sum += tree[x][i];
	return sum;
}
 
void update(int x, int y, int val){
	for(; x<=n; x += x & (-x))
		for(int i=y; i<=n; i += i & (-i))
			tree[x][i] += val;
}

کاربرد ها[ویرایش]

درخت فنویک در مسائلی که به فراوانی تراکمی مربوط می شوند مورد استفاده قرار می گیرد.


منابع[ویرایش]

جستارهای وابسته[ویرایش]

مقاله ای در سایت تاپکدر

مقاله ای در سایت الگوریتمیست

مقاله اصلی فنویک

جستارهای وابسته[ویرایش]

درخت‌های بازه ای

درخت‌های قرمز سیاه

داده ساختار ها