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

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

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

ساختار

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

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

  • $tree[x] = sum[x-2^r+1…x]$
  • $tree[0] = 0$

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

پیدا کردن آخرین بیت $1$

اگر عدد $p$ را به صورت مکمل-۲ نمایش دهیم، ارزش آخرین بیت یک آن برابر است با: $p & -p$

بدست آوردن آرایه $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$ تبدیل می‌شوند.

بنابر این می‌توان $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]$، این مقدار را اضافه میکنیم، سپس کوچکترین بیت $1$ در $i$ را به آن اضافه می‌کنیم و تا زمانی که $i⇐n$ باشد این کار را ادامه می‌دهیم. 

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

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