درخت فنویک

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

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

یک درخت فنویک که اعداد ۱ تا ۵ به ترتیب در آن درج می شوند.

یک راه حل ساده برای این مسئله با استفاده از آرایه، به این صورت است که دستور ۱ را در (۱)O و دستور ۲ را در $O(n)$ انجام می‌دهد. پس اگر m دستور داشته باشیم، در بدترین حالت (زمانی که همه دستورها از نوع دوم باشند)، به زمان $O(n*m)$ احتیاج داریم. با استفاده از داده ساختار درخت فنویک (یا درخت اندیس داده شده دودویی) می‌توان هر دستور را در $O(logn)$ و در نتیجه کل دستورها را در $O(mlogn)$ انجام داد. به‌طور کلی این اعمال توسط درخت بازه‌ها هم در این زمان انجام می‌شوند، اما مزیت درخت فنویک در کم بودن حافظه (دقیقاً به اندازه 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 برابر ۱ باشد. تعریف می‌کنیم:

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

$tree[0]=0$

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

مثال:

پیدا کردن آخرین بیت ۱

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

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

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

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

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

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

مثال: [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 تبدیل می‌شوند:

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

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

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

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

به این ترتیب می‌توانیم به هر دو دستور در $O(logn)$ جواب دهیم.

پیاده‌سازی در دو بعد

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

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;
}

کاربردها

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

جستارهای وابسته

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

منابع

• مقاله‌ای از پیتر فنویک در سال ۱۹۹۴
• ویکی‌پدیای انگلیسی