درخت فنویک

فرض کنید آرایه a به اندازه n که در ابتدا همه مقادیر آن برابر ۰ هستند به ما داده شده‌است، می‌خواهیم اعمال زیر را روی این آرایه انجام دهیم:
* به درایه i-ام، x واحد اضافه کن.
* مجموع اعداد درایه i-ام تا درایه j-ام را به دست بیاور.
یک راه حل ساده برای این مسئله با استفاده از آرایه، به این صورت است که دستور ۱ را در (۱)O و دستور ۲ را در 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


```cpp
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 در ارائه قرار دارند)

مثال:
پرونده:Fenwick tree 162.jpg

### پیدا کردن آخرین بیت ۱
فرض کنید می‌خواهیم کوچکترین بیت عدد 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


```cpp
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، این مقدار را اضافه می‌کنیم، سپس کوچکترین بیت ۱ در i را به آن اضافه می‌کنیم و تا زمانی که i
void update(int i, int val){
 for(; i
به این ترتیب می‌توانیم به هر دو دستور در O(log n) جواب دهیم.

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


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


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

## جستارهای وابسته
* درخت بازه‌ها

## منابع

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

رده:ساختار درختی
رده:اختراع‌های روسی
رده:اختراع‌های اتحاد شوروی