درخت فنویک
فرض کنید آرایه a به اندازه n که در ابتدا همه مقادیر آن برابر ۰ هستند به ما داده شده‌است، می‌خواهیم اعمال زیر را روی این آرایه انجام دهیم: یک راه حل ساده برای این مسئله با استفاده از آرایه، به این صورت است که دستور ۱ را در (۱)O و دستور ۲ را در formula_1 انجام می‌دهد. پس اگر m دستور داشته باشیم، در بدترین حالت (زمانی که همه دستورها از نوع دوم باشند)، به زمان formula_2 احتیاج داریم. با استفاده از داده ساختار درخت فنویک (یا درخت اندیس داده شده دودویی) می‌توان هر دستور را در formula_3 و در نتیجه کل دستورها را در formula_4 انجام داد. به‌طور کلی این اعمال توسط درخت بازه‌ها هم در این زمان انجام می‌شوند، اما مزیت درخت فنویک در کم بودن حافظه (دقیقاً به اندازه n)، کوتاه بودن کد و همچنین سهولت پیاده‌سازی آن در ابعاد بیشتر است.
تعریف می‌کنیم:
این راه حل زمانی که همه دستورهای نوع دوم بعد از دستورها نوع اول باشند، m دستور را در formula_7 انجام می‌دهد.
به وضوح: formula_8
بعد از این که همه دستورها نوع اول، مانند راه قبل در formula_9 انجام شدند، به صورت پویا مقادیر آرایه c را در formula_1 محاسبه می‌کنیم. بنابر تعریف formula_11 :c void initialize(){ c[0] = 0; for(int i=1; i<=n; i++) c[i] = c[i-1] + a[i];
بعد از این مقدار دهی هم مانند بالا می‌توانیم مقادیر sum را از روی c به دست بیاوریم. پس کل دستورها را در formula_7 انجام می‌دهیم. اما اگر دستورها نوع دوم بعد از نوع اول نباشند، بعد از هر دستور نوع اول باید مقادیر آرایه c را به روز کنیم، پس باز هم‌زمان اجرا در بدترین حالت از formula_2 می‌شود.
ایده اصلی این درخت این است که هر عدد طبیعی را می‌توان به صورت جمع تعدادی از توان‌های ۲ نوشت. به همین ترتیب مجموع یک بازه را می‌توان به صورت جمع تعدادی زیربازه بدون اشتراک از آن بازه نوشت.
فرض کنید r کوچکترین عددی باشد که بیت r-ام عدد x برابر ۱ باشد. تعریف می‌کنیم:
formula_14
formula_15
مثال: فرض کنید می‌خواهیم کوچکترین بیت عدد P که برابر ۱ است را به دست آوریم، P را می‌توان به صورت x1y نوشت که x برابر بیت‌های قبل از آخرین ۱ و y برابر تعدادی ۰ است. می‌خواهیم عدد P- را محاسبه کنیم:
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[x ابتدا متغیر sum را برابر [tree[x قرار می‌دهیم، سپس بیت آخر x را حذف می‌کنیم و sum را با[tree[x جمع می‌کنیم، همین کار را تکرار می‌کنیم تا x برابر ۰ شود.
مثال: [c[15] = sum[15] + sum[14]+ sum[12] + sum[8 int c(int x){ return sum;
به‌طور کلی می‌توانیم بگوییم که در درخت، راس x پدر تمام رئوسی است که با حذف بیت آخرشان به x تبدیل می‌شوند:
بنابر این می‌توان (c(x را در زمان formula_3 محاسبه کرد، در نتیجه می‌توان [sum[i...j و همچنین [a[i را نیز در formula_3 بدست آورد.([a[i] = sum[i...i)
بعد از این که به درایه i-ام، مقدار val را اضافه می‌کنیم، باید به همه [tree[jهایی که i در بازه j قرار می‌گیرد، مقدار val را اضافه کنیم. برای این کار ابتدا به [tree[i، این مقدار را اضافه می‌کنیم، سپس کوچکترین بیت ۱ در i را به آن اضافه می‌کنیم و تا زمانی که i<=n باشد این کار را ادامه می‌دهیم. void update(int i, int val){
به این ترتیب می‌توانیم به هر دو دستور در formula_3 جواب دهیم.
به وسیله توابع زیر می‌توان درخت فنویک را در دو بعد پیاده‌سازی کرد. 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;
درخت فنویک در مسائلی که به فراوانی تراکمی مربوط می‌شوند مورد استفاده قرار می‌گیرد.