درخت Fenwick / BIT
Fenwick Treeدرخت Fenwick / BIT یک ساختمان داده از دسته ساختمان داده است. این ساختمان داده، مقادیر و ارتباط بین آن‌ها را طوری سازمان‌دهی می‌کند که عملیات مهم هزینه قابل‌پیش‌بینی داشته باشند.
اول این مفهوم را در ذهن نگه دار
درخت Fenwick / BIT یک ساختمان داده از دسته ساختمان داده است. این ساختمان داده، مقادیر و ارتباط بین آن‌ها را طوری سازمان‌دهی می‌کند که عملیات مهم هزینه قابل‌پیش‌بینی داشته باشند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم درخت Fenwick / BIT ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع update/query O(log n) است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای درخت Fenwick / BIT هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
update/query O(log n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای درخت Fenwick / BIT در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی update/query O(log n) و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
درخت Fenwick / BIT چه مسئله‌ای را حل می‌کند؟
درخت Fenwick / BIT یک ساختمان داده از دسته ساختمان داده است. این ساختمان داده، مقادیر و ارتباط بین آن‌ها را طوری سازمان‌دهی می‌کند که عملیات مهم هزینه قابل‌پیش‌بینی داشته باشند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا update/query O(log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.