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