توضیح الگوریتم:

برای حل این سوال میتوان از داده ساختار درخت داده ها (segment tree) استفاده کرد.

در ابتدا درخت داده ای میسازیم که در هر راس آن مجموع بازه ی متناظر با آن راس نوشته شده است. میدانیم به راحتی میتوانیم مجموع یک بازه را در $O(lgn)$ به وسیله ی درخت داده ها بدست آوریم. این مقدار را برای راس شماره ی $i$ ام $tree_i$ بگیرید. ولی مشکل اصلی ما در واقع در هنگام آپدیت کردن درخت است. زیرا ممکن است بازه ی وروردی بسیار بزرگ باشد و مدت زمان زیادی برای آپدیت کردن آن طول بکشد. برای این کار آرایه ای از جفت های مرتب طراحی میکنیم که عضو $i$ام آن مرتبط با راس شماره ی $i$ درخت است. چون در هر آپدیت کردن، ما قادر به آپدیت کردن کل درخت نیستیم پس میتوانیم درون این جفت اعدادی را ذخیره کنیم که نشان دهنده ی مقداری باشد که ما باید به زیر درختی که ریشه ی آن راس مورد نظر است اضافه کنیم. (در واقع این مقدار را ذخیره میکنیم و در هنگامی که نیاز به آن داشتیم اضافه میکنیم)

در ابتدای کار تمام جفت های این آرایه $(0,0)$ هستند. فرض کنید جفت $(x,y)$ متناظر به یک راس $i$ درخت است. مقدار $x$ برابر با مقدار ثابتی است که باید به کل اعداد بازه ی متناظر اضافه شود و $y$ برابر با تعداد دفعاتی است که ما باید از اول این بازه شروع کنیم و به عضو $j$ام بازه $j$ تا اضافه کنیم.

حال چگونه مقدار ذخیره شده در آرایمان را اضافه کنیم؟ اگر در راس $i$ باشیم و طول بازه ی متناظر با راس $i$ برابر با $len$ باشد، و همچنین جفت متانظر به راس $i$ ، $(x,y)$ باشد، آنگاه به $tree_i$ مقدار زیر اضافه میگردد:

$\frac {len \times(len+1)}{2} \times y + len \times x$

بعد از این کار ما قادر نیستیم تمام زیر درخت را آپدیت کنیم در نتیجه میتوانیم جفت های متناظر به بچه های این راس را تغییر دهیم تا در هنگامی که به آنها نیازی داشتیم آنها را نیز آپدیت کنیم. اگر جفت متناظر به بچه ی سمت راست راس مورد نظر $(x_1,y_1)$ و جفت متناظر به بچه ی سمت راست این راس $(x_2,y_2)$ باشد، آنگاه این جفت ها به ترتیب به صورت زیر تغییر میکنند ($mid$ همان وسط بازه ی $i$ است. یا در واقع تعداد اعضای بازه ی متناظر با بچه ی سمت راست):

بچه ی سمت راست : $(x_1+x , y_1+y)$

بچه ی سمت چپ: $(x_2+x+mid \times y , y_2+y)$

دقت کنید مقدار $x_2$ به این دلیل $mid \times y$ اضافه شد چون شروع بازه ی سمت چپ با شروع بازه ی پدر یکسان نیست و در ابتدا باید به همه ی اعضای این بازه مقدار $mid \times y$ اضافه شود.

این عمل را ، عمل شیفت تعریف میکنیم .(یعنی اضافه کردن مقدار ذخیره ی شده ی راس $i$ به $tree_i$ و سپس آپدیت کردن جفت های بچه های آن راس)

حال میتوانیم در هنگام آپدیت کردن وقتی به یک بازه رسیدیم عمل شیف را روی آن انجام دهیم.

اما کار اصلی را هنگامی که میخواهیم مجموع اعضای یک بازه را چاپ کنیم انجام میدهیم. در اینجا هنگامی که از ریشه شروع میکنیم تا به بازه ی مورد نظر برسیم، به هر راسی که میرسیم عمل شیف را روی آن راس انجام میدهیم. در نتیجه مقدار نهایی $tree_i$ بدست می آید و ما وقتی به راس های پایین تر میرویم در واقع آنهایی را شیف میدهیم که لازم داریم، پس عملات های ما زیاد طول نمیکشد و میتوانیم در $O(lgn)$ مجموع اعضای بازه ی خواسته شده را چاپ کنیم.

حال پس در نهایت الگوریتم ما در زمان مناسب و در پیچیدگی زمانی $O(qlgn+n)$ صورت میگیرد.

توضیحات کد:

در کد تابع build درخت را میسازد، تابع update وظیفه ی آپدیت کردن بازه را دارد، تابع query مجموع بازه را به عنوان خروجی میدهد و در نهایت تابع shift عمل شیف کردن را انجام میدهد.

مشاهده ی کد (C++)