ساختمان داده

مسائل جست و جوی بازه ای - range query

در هنر خطاطی تاکید می شود که یکی از راه های یادگیری خوش نویسی مشاهده آثار زیباست (مثلاً آثار میرعماد) ، به طور کلی یکی از راه های لمس بهتر هنر درک ، مشاهده و تعمق در آثار هنری است ( البته این یک گام از هزاران گام است) ، الگوریتم و ریاضیات نیز اگر به بعد هنری آن ها نگاه کنیم از این قاعده مستثنی نیستند ، گاهی اوقات شما یک مسئله خاص را حل  می کنید ولی می بینید شخص دیگری به روش بهتر ، زیباتر و تحسین برانگیز تری آن را حل کرده است 

BIT ، ساختمان داده ای ساده ولی قدرتمند

BIT کلمه ای است که از حروف اول binary indexed tree گرفته شده است و ساختمان داده ای ساده ، سریع و قدرتمند است که در رابطه با مسائلی که با فراوانی تجمعی سر و کار دارند به کار می رود ، این ساختمان داده اولین بار در مقاله ای با عنوان A New Data Structure for Cumulative Frequency Tables توسط peter m. fenwick ارائه شد که به همین دلیل بسیاری آن را با عنوان fenwick tree نیز میشناسند.

در این آموزش با این ساختمان داده جذاب آشنا می شویم.

قبل از آشنایی با این ساختمان داده بهتر است یک مسئله ساده و یک راه حل ابتدایی برای آن ببینیم.

مسئله :

اشتراک در RSS - ساختمان داده