فرض کنید آرایه $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)$ جواب دهیم.

• https://en.wikipedia.org/wiki/Fenwick_tree