درخت Fenwick یا Binary Indexed Tree جمع‌هایِ بخشی را نگه می‌دارد تا پس ازتغییرِ یک مقدار،لازم نباشد همهٔprefixها ازنو ساخته شوند. این تمرین هشت عددِ صحیح،چهار point-add ویک setِ صریح دارد؛ پس ازهرمرحله،تمامِ جمع‌هایِ پیشوند وبازه با sumِ آرایهٔمرجع کنترل می‌شوند. هیچ دادهٔزنده یا وعدهٔسرعتِ عملیاتی درکار نیست.
مقدارِ خام با خانهٔدرخت یکی نیست
آرایهٔاصیل[۳،−۱،۴،۲،۰،۵،−۲،۱] است. اندیسِ بیرونی از۰تا۷ واندیسِ درخت از۱تا۸ است؛ خانهٔصفرِ درخت دراین قرارداد استفاده نمی‌شود. مقدارِ tree[i] جمعِ یک قطعه است که طولِ آن lowbitِ i،یعنی i&−i است. درمختصاتِ بیرونی،آن قطعه [i−lowbit(i)،i) است.
برایِ نمونه،خانهٔ۴درخت جمعِ چهار مقدارِ اول یعنی۸،خانهٔ۶ جمعِ مقدارهایِ اندیسِ ۴و۵ یعنی۵ وخانهٔ۸ مجموعِ همه یعنی۱۲را دارد. جدولِ اولیهٔدرخت[۰،۳،۲،۴،۸،۰،۵،−۲،۱۲] است. این عددها را با آرایهٔخام جابه‌جا گزارش نمی‌کنیم؛ نامِ هر نمایش درJSON روشن است.
prefixِ هفت چگونه ازچند قطعه ساخته می‌شود؟
prefix(end) دراین ابزار جمعِ بازهٔنیمه‌بازِ[۰،end) را می‌دهد. برایِ end=7 ازخانهٔ۷درخت شروع می‌کنیم وهر بار lowbit را کم می‌کنیم:۷→۶→۴→۰. با جمعِ خانه‌هایِ ۷،۶و۴،هفت مقدارِ اول پوشش داده می‌شوند؛ هرقطعه یک بار می‌آید ومقدارِ هشتم داخلِ بازه نیست.
prefixِ صفر،جمعِ خالی وصفر است. برایِ بازهٔ[ l,r ) نیز prefix(r)−prefix(l) می‌گیریم. ابتدا و انتهایِ برابر،مثلاً[۳،۳)،بازهٔخالی است وکد آن را واقعاًآزمایش می‌کند. قراردادِ«انتها خارج ازبازه» را با شمارهٔآخرینِ عضو یکی نگیریم.
یک تغییر به کدام خانه‌ها می‌رود؟
در point-add،اندیسِ بیرونی را یک واحد زیاد می‌کنیم ودرهرگام lowbit را به اندیسِ داخلی اضافه می‌کنیم. تغییرِ اندیسِ ۰ به خانه‌هایِ ۱،۲،۴و۸ می‌رود؛ تغییرِ اندیسِ ۳ فقط۴و۸ را اصلاح می‌کند. این‌ها همان قطعه‌هایی‌اند که مقدارِ تغییرکرده را پوشش می‌دهند.
| اندیسِ بیرونی | delta | خانه‌هایِ داخلیِ اصلاح‌شده |
|---|---|---|
| ۰ | +۲ | ۱،۲،۴،۸ |
| ۳ | −۳ | ۴،۸ |
| ۷ | +۴ | ۸ |
| ۲ | −۴ | ۳،۴،۸ |
هرچهار تغییر واقعاً اجرا وپس ازهرکدام آرایهٔمرجع نیز با همان delta عوض می‌شود. تغییرِ درخت به‌تنهایی شاهدِ درست‌بودن نیست؛ جمعِ مستقلِ آرایه باید همان پاسخ را بدهد. مبدأِ اندیسِ صفر به‌دلیلِ تبدیلِ+1 واردِ حلقهٔداخلیِ صفر نمی‌شود؛ وگرنه lowbitِ صفر پیشرفتی ایجاد نمی‌کرد.
setِ مقدارِ تازه را با addِ آن اشتباه نگیریم
بعد ازچهار تغییر،می‌خواهیم مقدارِ اندیسِ ۴ را۷کنیم. delta برابرِ مقدارِ جدید منهایِ مقدارِ جاریِ آن خانه است؛ دراین fixture مقدارِ جاری۰ وdelta=7 است. کد،set_value وtranslated_delta را جدا ثبت می‌کند و مسیرِ داخلیِ ۵،۶و۸ را اصلاح می‌کند. اگر مقدارِ قبلی صفر نبود،دادنِ خودِ مقدارِ جدید به add همان عملیات نبود.
آرایهٔنهایی[۵،−۱،۰،−۱،۷،۵،−۲،۵] می‌شود. prefixِ ۷درآن۱۳وکلِ آرایه۱۸است. دفترِ coverageِ نهایی برایِ تمامِ هشت خانهٔدرخت،بازهٔبیرونی ومقدارِ ذخیره‌شده را نشان می‌دهد وهرکدام با sumِ مرجع کنترل می‌شود.
تمامِ بازه‌هایِ این مثال،نه فقط یک query
درهرمرحله۹prefix و۴۵بازهٔنیمه‌بازِ ممکنِ هشت عدد را بررسی می‌کنیم. مرحلهٔاول وپنج تغییر،جمعاً۳۲۴برابریِ واقعی دارند. اندیسِ منفی،اندیسِ ۸وبولینِ True نیز درسه آزمونِ update رد می‌شوند. همهٔداده‌ها صحیح ومحدودند؛ عملکردِ اعشاری،هم‌زمانی یا ورودیِ عمومیِ بزرگ سنجیده نشده است.
وجودِ مقدارِ منفی برایِ جمعِ این دامنه مجاز است،اما جست‌وجویِ رتبه برفرضِ prefixِ یکنواخت مسئلهٔدیگری است ودرکد نداریم. پنجرهٔSQL عضویتِ aggregate دریک snapshot و Lag وRolling زمانِ دسترسیِ داده را می‌سنجند؛ اینجا نگهداریِ جمع پس ازتغییرِ مقدار اجرا می‌شود. ادامه در مبانی هوش مصنوعی؛ کدِ Python۳٫۱۲٫۱۴ روشِ گزارش‌گیری،فشرده‌سازی یا زیرساختِ محصولِ اپرا را اعلام نمی‌کند.
فایل تمرین و منبع
کد مستقلِ تمرینِ محدود · تمام خروجیِ واقعیِ همین تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.