درخت فنویک

این راه حل زمانی که همه دستورهای نوع دوم بعد از دستورها نوع اول باشند، m دستور را در ${\displaystyle O(n+m)}$

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

بعد از این که همه دستورها نوع اول، مانند راه قبل در ${\displaystyle O(1)}$

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

بعد از این مقدار دهی هم مانند بالا می‌توانیم مقادیر sum را از روی c به دست بیاوریم. پس کل دستورها را در ${\displaystyle O(n+m)}$

ساختار

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

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

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

${\displaystyle tree[0]=0}$

(${\displaystyle a[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 را در زمان ${\displaystyle O(logn)}$

به روز کردن مقادیر 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;
}

به این ترتیب می‌توانیم به هر دو دستور در ${\displaystyle 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;
}

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

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

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