درخت رادیکالی (Sqrt Tree)¶
آرایه $a$ با $n$ عنصر و عملگر $\circ$ با خاصیت شرکت‌پذیری داده شده است: برای هر $x$، $y$ و $z$، رابطه $(x \circ y) \circ z = x \circ (y \circ z)$ برقرار است.
بنابراین، عملگرهایی مانند $\gcd$، $\min$، $\max$، $+$، $\text{and}$، $\text{or}$، $\text{xor}$ و غیره این شرایط را برآورده می‌کنند.
همچنین تعدادی پرس‌وجو به شکل $q(l, r)$ داریم. برای هر پرس‌وجو، باید حاصل $a_l \circ a_{l+1} \circ \dots \circ a_r$ را محاسبه کنیم.
درخت رادیکالی (Sqrt Tree) می‌تواند چنین پرس‌وجوهایی را در زمان $O(1)$ با پیش‌پردازش و حافظه $O(n \cdot \log \log n)$ پاسخ دهد.
توضیحات¶
ساخت تجزیه رادیکالی (sqrt decomposition)¶
بیایید یک تجزیه رادیکالی بسازیم. آرایه خود را به $\sqrt{n}$ بلاک تقسیم می‌کنیم که هر بلاک اندازه‌ای برابر با $\sqrt{n}$ دارد. برای هر بلاک، موارد زیر را محاسبه می‌کنیم:
- پاسخ پرس‌وجوهایی که در بلاک قرار دارند و از ابتدای بلاک شروع می‌شوند ($\text{prefixOp}$)
- پاسخ پرس‌وجوهایی که در بلاک قرار دارند و در انتهای بلاک تمام می‌شوند ($\text{suffixOp}$)
و یک آرایه اضافی محاسبه می‌کنیم:
- $\text{between}_{i, j}$ (برای $i \le j$) - پاسخ پرس‌وجویی که از ابتدای بلاک $i$ شروع شده و در انتهای بلاک $j$ تمام می‌شود. توجه کنید که $\sqrt{n}$ بلاک داریم، پس اندازه این آرایه $O(\sqrt{n}^2) = O(n)$ خواهد بود.
بیایید مثال را ببینیم.
برای مثال، فرض کنید عملگر $\circ$ همان $+$ باشد (جمع روی یک قطعه را محاسبه می‌کنیم) و آرایه $a$ به صورت زیر باشد:
{1, 2, 3, 4, 5, 6, 7, 8, 9}
این آرایه به سه بلاک تقسیم می‌شود: {1, 2, 3}، {4, 5, 6} و {7, 8, 9}.
برای بلاک اول، $\text{prefixOp}$ برابر با {1, 3, 6} و $\text{suffixOp}$ برابر با {6, 5, 3} است.
برای بلاک دوم، $\text{prefixOp}$ برابر با {4, 9, 15} و $\text{suffixOp}$ برابر با {15, 11, 6} است.
برای بلاک سوم، $\text{prefixOp}$ برابر با {7, 15, 24} و $\text{suffixOp}$ برابر با {24, 17, 9} است.
آرایه $\text{between}$ به این صورت است:
{
{6, 21, 45},
{0, 15, 39},
{0, 0, 24}
}
(فرض می‌کنیم که عناصر نامعتبر که در آنها $i > j$ است با صفر پر شده‌اند)
واضح است که این آرایه‌ها را می‌توان به راحتی در زمان و حافظه $O(n)$ محاسبه کرد.
با استفاده از این آرایه‌ها، از هم‌اکنون می‌توانیم به برخی پرس‌وجوها پاسخ دهیم. اگر پرس‌وجو در یک بلاک نگنجد، می‌توانیم آن را به سه بخش تقسیم کنیم: پسوند یک بلاک، سپس یک قطعه از بلاک‌های متوالی و در نهایت پیشوند یک بلاک. می‌توانیم با تقسیم پرس‌وجو به این سه بخش و اعمال عملگرمان روی مقداری از $\text{suffixOp}$، سپس مقداری از $\text{between}$ و در نهایت مقداری از $\text{prefixOp}$، به آن پاسخ دهیم.
اما اگر پرس‌وجوهایی داشته باشیم که به طور کامل در یک بلاک قرار می‌گیرند، نمی‌توانیم با استفاده از این سه آرایه به آنها پاسخ دهیم. بنابراین، باید کار دیگری انجام دهیم.
ساختن یک درخت¶
ما فقط نمی‌توانیم به پرس‌وجوهایی که کاملاً در یک بلاک قرار می‌گیرند پاسخ دهیم. اما چه می‌شود اگر همین ساختار توصیف شده در بالا را برای هر بلاک بسازیم؟ بله، می‌توانیم این کار را انجام دهیم. و این کار را به صورت بازگشتی انجام می‌دهیم تا به بلاک‌هایی با اندازه $1$ یا $۲$ برسیم. پاسخ برای چنین بلاک‌هایی را می‌توان به راحتی در $O(1)$ محاسبه کرد.
بنابراین، یک درخت به دست می‌آوریم. هر گره از این درخت نمایانگر یک قطعه از آرایه است. گره‌ای که یک قطعه از آرایه با اندازه $k$ را نشان می‌دهد، $\sqrt{k}$ فرزند دارد -- برای هر بلاک. همچنین هر گره شامل سه آرایه توصیف شده برای قطعه‌ای است که در بر می‌گیرد. ریشه درخت کل آرایه را نشان می‌دهد. گره‌هایی با طول قطعه $1$ یا $۲$ برگ هستند.
همچنین واضح است که ارتفاع این درخت $O(\log \log n)$ است، زیرا اگر یک رأس از درخت آرایه‌ای به طول $k$ را نشان دهد، فرزندان آن طولی برابر با $\sqrt{k}$ خواهند داشت. $\log(\sqrt{k}) = \frac{\log{k}}{2}$، بنابراین $\log k$ در هر لایه از درخت نصف می‌شود و در نتیجه ارتفاع آن $O(\log \log n)$ است. زمان ساخت و حافظه مورد نیاز $O(n \cdot \log \log n)$ خواهد بود، زیرا هر عنصر از آرایه دقیقاً یک بار در هر لایه از درخت ظاهر می‌شود.
اکنون می‌توانیم به پرس‌وجوها در $O(\log \log n)$ پاسخ دهیم. می‌توانیم در درخت به پایین حرکت کنیم تا به قطعه‌ای با طول $1$ یا $۲$ برسیم (پاسخ برای آن در زمان $O(1)$ قابل محاسبه است) یا به اولین قطعه‌ای برسیم که پرس‌وجوی ما به طور کامل در یک بلاک آن قرار نمی‌گیرد. برای نحوه پاسخ به پرس‌وجو در این حالت، به بخش اول مراجعه کنید.
خوب، اکنون می‌توانیم هر پرس‌وجو را در $O(\log \log n)$ انجام دهیم. آیا می‌توان سریع‌تر این کار را کرد؟
بهینه‌سازی پیچیدگی پرس‌وجو¶
یکی از واضح‌ترین بهینه‌سازی‌ها، جستجوی دودویی برای یافتن گره درختی است که به آن نیاز داریم. با استفاده از جستجوی دودویی، می‌توانیم به پیچیدگی $O(\log \log \log n)$ برای هر پرس‌وجو برسیم. آیا می‌توانیم حتی سریع‌تر عمل کنیم؟
پاسخ مثبت است. بیایید دو فرض زیر را در نظر بگیریم:
- اندازه هر بلاک توانی از دو است.
- تمام بلاک‌ها در هر لایه برابر هستند.
برای رسیدن به این هدف، می‌توانیم تعدادی عنصر صفر به آرایه خود اضافه کنیم تا اندازه آن به توانی از دو تبدیل شود.
وقتی از این روش استفاده می‌کنیم، اندازه برخی بلاک‌ها ممکن است برای تبدیل شدن به توانی از دو، دو برابر بزرگتر شوند، اما همچنان اندازه آنها $O(\sqrt{k})$ باقی می‌ماند و ما پیچیدگی خطی را برای ساخت آرایه‌ها در یک قطعه حفظ می‌کنیم.
اکنون، می‌توانیم به راحتی بررسی کنیم که آیا پرس‌وجو به طور کامل در یک بلاک با اندازه $2^k$ قرار می‌گیرد یا خیر. بیایید بازه پرس‌وجو، یعنی $l$ و $r$ (با اندیس‌گذاری از صفر) را به صورت دودویی بنویسیم. برای نمونه، فرض کنید $k=4, l=39, r=46$. نمایش دودویی $l$ و $r$ به این صورت است:
$l = 39_{10} = 100111_2$
$r = 46_{10} = 101110_2$
به یاد داشته باشید که یک لایه شامل قطعه‌هایی با اندازه برابر است و بلاک‌ها در یک لایه نیز اندازه برابری دارند (در مثال ما، اندازه آنها $2^k = 2^4 = 16$ است). بلاک‌ها کل آرایه را پوشش می‌دهند، بنابراین بلاک اول عناصر $(0 - 15)$ (در نمایش دودویی $000000_2 - 001111_2$) را پوشش می‌دهد، بلاک دوم عناصر $(16 - 31)$ (در نمایش دودویی $010000_2 - 011111_2$) و به همین ترتیب. می‌بینیم که اندیس‌های موقعیت‌هایی که توسط یک بلاک پوشش داده می‌شوند، ممکن است فقط در $k$ بیت آخر (در مثال ما، ۴ بیت) متفاوت باشند. در مورد ما، $l$ و $r$ به جز چهار بیت کم‌ارزش، بیت‌های برابری دارند، بنابراین در یک بلاک قرار می‌گیرند.
بنابراین، باید بررسی کنیم که آیا تفاوت آنها در بیش از $k$ بیت کم‌ارزش نیست (یا به عبارتی $l\ \text{xor}\ r$ از $2^k-1$ تجاوز نمی‌کند).
با استفاده از این مشاهده، می‌توانیم لایه‌ای را پیدا کنیم که برای پاسخ سریع به پرس‌وجو مناسب باشد. روش انجام این کار به شرح زیر است:
-
برای هر $i$ که از اندازه آرایه بزرگتر نیست، پرارزش‌ترین بیتی که برابر با ۱ است را پیدا می‌کنیم. برای انجام سریع این کار، از DP و یک آرایه پیش‌محاسبه شده استفاده می‌کنیم.
-
اکنون، برای هر $q(l, r)$، پرارزش‌ترین بیت $l\ \text{xor}\ r$ را پیدا می‌کنیم و با استفاده از این اطلاعات، به راحتی می‌توان لایه‌ای را انتخاب کرد که بتوانیم پرس‌وجو را به سادگی در آن پردازش کنیم. در اینجا نیز می‌توانیم از یک آرایه پیش‌محاسبه شده استفاده کنیم.
برای جزئیات بیشتر، کد زیر را ببینید.
بنابراین، با استفاده از این روش، می‌توانیم به هر پرس‌وجو در زمان $O(1)$ پاسخ دهیم. هورا! :)
به‌روزرسانی عناصر¶
همچنین می‌توانیم عناصر را در درخت رادیکالی به‌روزرسانی کنیم. هم به‌روزرسانی یک عنصر و هم به‌روزرسانی روی یک قطعه پشتیبانی می‌شود.
به‌روزرسانی یک عنصر¶
پرس‌وجوی $\text{update}(x, val)$ را در نظر بگیرید که انتساب $a_x = val$ را انجام می‌دهد. باید این پرس‌وجو را به اندازه کافی سریع انجام دهیم.
رویکرد ساده‌لوحانه¶
ابتدا، بیایید نگاهی بیندازیم که با تغییر یک عنصر، چه چیزهایی در درخت تغییر می‌کند. یک گره درخت با طول $l$ و آرایه‌های آن: $\text{prefixOp}$، $\text{suffixOp}$ و $\text{between}$ را در نظر بگیرید. به راحتی می‌توان دید که فقط $O(\sqrt{l})$ عنصر از $\text{prefixOp}$ و $\text{suffixOp}$ تغییر می‌کنند (فقط درون بلاکی که عنصر تغییر یافته در آن است). $O(l)$ عنصر در $\text{between}$ تغییر می‌کنند. بنابراین، $O(l)$ عنصر در گره درخت به‌روزرسانی می‌شوند.
به یاد داریم که هر عنصر $x$ دقیقاً در یک گره درخت در هر لایه وجود دارد. گره ریشه (لایه $۰$) طولی برابر با $O(n)$ دارد، گره‌های لایه $۱$ طولی برابر با $O(\sqrt{n})$، گره‌های لایه $۲$ طولی برابر با $O(\sqrt{\sqrt{n}})$ و غیره دارند. بنابراین پیچیدگی زمانی برای هر به‌روزرسانی $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$ است.
اما این خیلی کند است. آیا می‌توان سریع‌تر این کار را کرد؟
یک درخت رادیکالی درون درخت رادیکالی¶
توجه داشته باشید که گلوگاه فرآیند به‌روزرسانی، بازسازی آرایه $\text{between}$ در گره ریشه است. برای بهینه‌سازی درخت، بیایید از این آرایه خلاص شویم! به جای آرایه $\text{between}$، یک درخت رادیکالی دیگر برای گره ریشه ذخیره می‌کنیم. بیایید آن را $\text{index}$ بنامیم. این درخت همان نقش $\text{between}$ را ایفا می‌کند—به پرس‌وجوها روی قطعه‌هایی از بلاک‌ها پاسخ می‌دهد. توجه کنید که بقیه گره‌های درخت $\text{index}$ ندارند و آرایه‌های $\text{between}$ خود را حفظ می‌کنند.
یک درخت رادیکالی شاخص‌دار (indexed) است اگر گره ریشه‌اش دارای $\text{index}$ باشد. یک درخت رادیکالی با آرایه $\text{between}$ در گره ریشه‌اش بدون شاخص (unindexed) است. توجه داشته باشید که خود $\text{index}$ یک درخت بدون شاخص است.
بنابراین، الگوریتم زیر را برای به‌روزرسانی یک درخت شاخص‌دار داریم:
-
به‌روزرسانی $\text{prefixOp}$ و $\text{suffixOp}$ در $O(\sqrt{n})$.
-
به‌روزرسانی $\text{index}$. این درخت طولی برابر با $O(\sqrt{n})$ دارد و ما فقط باید یک آیتم را در آن به‌روزرسانی کنیم (که نمایانگر بلاک تغییر یافته است). بنابراین، پیچیدگی زمانی برای این مرحله $O(\sqrt{n})$ است. می‌توانیم از الگوریتم توصیف شده در ابتدای این بخش (رویکرد "کند") برای انجام این کار استفاده کنیم.
-
به گره فرزند که نمایانگر بلاک تغییر یافته است رفته و آن را با الگوریتم "کند" در $O(\sqrt{n})$ به‌روزرسانی می‌کنیم.
توجه داشته باشید که پیچیدگی پرس‌وجو همچنان $O(1)$ است: ما نیاز داریم که از $\text{index}$ در یک پرس‌وجو بیش از یک بار استفاده نکنیم، و این کار $O(1)$ زمان می‌برد.
بنابراین، پیچیدگی زمانی کل برای به‌روزرسانی یک عنصر $O(\sqrt{n})$ است. هورا! :)
به‌روزرسانی یک قطعه¶
درخت رادیکالی همچنین می‌تواند کارهایی مانند تخصیص یک مقدار به یک قطعه را انجام دهد. $\text{massUpdate}(x, l, r)$ به این معنی است که $a_i = x$ برای تمام $l \le i \le r$.
دو رویکرد برای انجام این کار وجود دارد: یکی از آنها $\text{massUpdate}$ را در $O(\sqrt{n}\cdot \log \log n)$ انجام می‌دهد و پیچیدگی پرس‌وجو را $O(1)$ نگه می‌دارد. رویکرد دوم $\text{massUpdate}$ را در $O(\sqrt{n})$ انجام می‌دهد، اما پیچیدگی پرس‌وجو به $O(\log \log n)$ تبدیل می‌شود.
ما از انتشار با تأخیر (lazy propagation) به همان روشی که در درخت‌های قطعه‌ای (segment trees) استفاده می‌شود، بهره می‌بریم: برخی گره‌ها را به عنوان lazy (تنبل) علامت‌گذاری می‌کنیم، به این معنی که در صورت لزوم آنها را push خواهیم کرد. اما یک تفاوت با درخت‌های قطعه‌ای وجود دارد: push کردن یک گره پرهزینه است، بنابراین نمی‌توان آن را در حین پرس‌وجوها انجام داد. در لایه ۰، push کردن یک گره $O(\sqrt{n})$ زمان می‌برد. بنابراین، ما در داخل پرس‌وجوها گره‌ها را push نمی‌کنیم، بلکه فقط بررسی می‌کنیم که آیا گره فعلی یا والد آن lazy است یا خیر، و هنگام انجام پرس‌وجوها این موضوع را در نظر می‌گیریم.
رویکرد اول¶
در رویکرد اول، می‌گوییم که فقط گره‌های لایه ۱ (با طول $O(\sqrt{n})$) می‌توانند lazy باشند. هنگام push کردن چنین گرهی، کل زیردرخت آن شامل خودش در $O(\sqrt{n}\cdot \log \log n)$ به‌روزرسانی می‌شود. فرآیند $\text{massUpdate}$ به شرح زیر انجام می‌شود:
-
گره‌های لایه ۱ و بلاک‌های متناظر با آنها را در نظر بگیرید.
-
برخی بلاک‌ها به طور کامل توسط $\text{massUpdate}$ پوشش داده می‌شوند. آنها را در $O(\sqrt{n})$ به عنوان lazy علامت‌گذاری کنید.
-
برخی بلاک‌ها به طور جزئی پوشش داده می‌شوند. توجه داشته باشید که حداکثر دو بلاک از این نوع وجود دارد. آنها را در $O(\sqrt{n}\cdot \log \log n)$ بازسازی کنید. اگر lazy بودند، این موضوع را در نظر بگیرید.
-
$\text{prefixOp}$ و $\text{suffixOp}$ را برای بلاک‌های پوشش داده شده جزئی در $O(\sqrt{n})$ به‌روزرسانی کنید (زیرا فقط دو بلاک از این نوع وجود دارد).
-
$\text{index}$ را در $O(\sqrt{n}\cdot \log \log n)$ بازسازی کنید.
بنابراین می‌توانیم $\text{massUpdate}$ را سریع انجام دهیم. اما انتشار با تأخیر چگونه بر پرس‌وجوها تأثیر می‌گذارد؟ آنها تغییرات زیر را خواهند داشت:
-
اگر پرس‌وجوی ما به طور کامل در یک بلاک lazy قرار گیرد، آن را محاسبه کرده و lazy را در نظر بگیرید. $O(1)$.
-
اگر پرس‌وجوی ما از چندین بلاک تشکیل شده باشد که برخی از آنها lazy هستند، فقط باید به lazy در بلاک‌های چپ‌ترین و راست‌ترین توجه کنیم. بقیه بلاک‌ها با استفاده از $\text{index}$ محاسبه می‌شوند، که از قبل پاسخ روی بلاک‌های lazy را می‌داند (چون بعد از هر تغییر بازسازی می‌شود). $O(1)$.
پیچیدگی پرس‌وجو همچنان $O(1)$ باقی می‌ماند.
رویکرد دوم¶
در این رویکرد، هر گره (به جز ریشه) می‌تواند lazy باشد. حتی گره‌های درون $\text{index}$ نیز می‌توانند lazy باشند. بنابراین، هنگام پردازش یک پرس‌وجو، باید به دنبال تگ‌های lazy در تمام گره‌های والد بگردیم، یعنی پیچیدگی پرس‌وجو $O(\log \log n)$ خواهد بود.
اما $\text{massUpdate}$ سریع‌تر می‌شود. این فرآیند به شکل زیر است:
-
برخی بلاک‌ها به طور کامل با $\text{massUpdate}$ پوشش داده می‌شوند. بنابراین، تگ‌های lazy به آنها اضافه می‌شود. این کار $O(\sqrt{n})$ است.
-
$\text{prefixOp}$ و $\text{suffixOp}$ را برای بلاک‌های پوشش داده شده جزئی در $O(\sqrt{n})$ به‌روزرسانی کنید (زیرا فقط دو بلاک از این نوع وجود دارد).
-
فراموش نکنید که index را به‌روزرسانی کنید. این کار $O(\sqrt{n})$ است (از همان الگوریتم $\text{massUpdate}$ استفاده می‌کنیم).
-
آرایه $\text{between}$ را برای زیردرخت‌های بدون شاخص به‌روزرسانی کنید.
-
به گره‌های نمایانگر بلاک‌های پوشش داده شده جزئی بروید و $\text{massUpdate}$ را به صورت بازگشتی فراخوانی کنید.
توجه داشته باشید که وقتی فراخوانی بازگشتی را انجام می‌دهیم، یک $\text{massUpdate}$ پیشوندی یا پسوندی انجام می‌دهیم. اما برای به‌روزرسانی‌های پیشوندی و پسوندی می‌توانیم حداکثر یک فرزند پوشش داده شده جزئی داشته باشیم. بنابراین، یک گره در لایه ۱، دو گره در لایه ۲ و دو گره در هر سطح عمیق‌تر را بازدید می‌کنیم. پس، پیچیدگی زمانی $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$ است. رویکرد در اینجا شبیه به به‌روزرسانی گروهی در درخت قطعه‌ای است.
پیاده‌سازی¶
پیاده‌سازی زیر از درخت رادیکالی می‌تواند عملیات زیر را انجام دهد: ساخت در $O(n \cdot \log \log n)$، پاسخ به پرس‌وجوها در $O(1)$ و به‌روزرسانی یک عنصر در $O(\sqrt{n})$.
SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);
inline int log2Up(int n) {
int res = 0;
while ((1 << res) < n) {
res++;
}
return res;
}
class SqrtTree {
private:
int n, lg, indexSz;
vector<SqrtTreeItem> v;
vector<int> clz, layers, onLayer;
vector< vector<SqrtTreeItem> > pref, suf, between;
inline void buildBlock(int layer, int l, int r) {
pref[layer][l] = v[l];
for (int i = l+1; i < r; i++) {
pref[layer][i] = op(pref[layer][i-1], v[i]);
}
suf[layer][r-1] = v[r-1];
for (int i = r-2; i >= l; i--) {
suf[layer][i] = op(v[i], suf[layer][i+1]);
}
}
inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int bSz = 1 << bSzLog;
int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
for (int i = 0; i < bCnt; i++) {
SqrtTreeItem ans;
for (int j = i; j < bCnt; j++) {
SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
ans = (i == j) ? add : op(ans, add);
between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
}
}
}
inline void buildBetweenZero() {
int bSzLog = (lg+1) >> 1;
for (int i = 0; i < indexSz; i++) {
v[n+i] = suf[0][i << bSzLog];
}
build(1, n, n + indexSz, (1 << lg) - n);
}
inline void updateBetweenZero(int bid) {
int bSzLog = (lg+1) >> 1;
v[n+bid] = suf[0][bid << bSzLog];
update(1, n, n + indexSz, (1 << lg) - n, n+bid);
}
void build(int layer, int lBound, int rBound, int betweenOffs) {
if (layer >= (int)layers.size()) {
return;
}
int bSz = 1 << ((layers[layer]+1) >> 1);
for (int l = lBound; l < rBound; l += bSz) {
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
build(layer+1, l, r, betweenOffs);
}
if (layer == 0) {
buildBetweenZero();
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
}
void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
if (layer >= (int)layers.size()) {
return;
}
int bSzLog = (layers[layer]+1) >> 1;
int bSz = 1 << bSzLog;
int blockIdx = (x - lBound) >> bSzLog;
int l = lBound + (blockIdx << bSzLog);
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
if (layer == 0) {
updateBetweenZero(blockIdx);
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
update(layer+1, l, r, betweenOffs, x);
}
inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
if (l == r) {
return v[l];
}
if (l + 1 == r) {
return op(v[l], v[r]);
}
int layer = onLayer[clz[(l - base) ^ (r - base)]];
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
int lBlock = ((l - lBound) >> bSzLog) + 1;
int rBlock = ((r - lBound) >> bSzLog) - 1;
SqrtTreeItem ans = suf[layer][l];
if (lBlock <= rBlock) {
SqrtTreeItem add = (layer == 0) ? (
query(n + lBlock, n + rBlock, (1 << lg) - n, n)
) : (
between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
);
ans = op(ans, add);
}
ans = op(ans, pref[layer][r]);
return ans;
}
public:
inline SqrtTreeItem query(int l, int r) {
return query(l, r, 0, 0);
}
inline void update(int x, const SqrtTreeItem &item) {
v[x] = item;
update(0, 0, n, 0, x);
}
SqrtTree(const vector<SqrtTreeItem>& a)
: n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
clz[0] = 0;
for (int i = 1; i < (int)clz.size(); i++) {
clz[i] = clz[i >> 1] + 1;
}
int tlg = lg;
while (tlg > 1) {
onLayer[tlg] = (int)layers.size();
layers.push_back(tlg);
tlg = (tlg+1) >> 1;
}
for (int i = lg-1; i >= 0; i--) {
onLayer[i] = max(onLayer[i], onLayer[i+1]);
}
int betweenLayers = max(0, (int)layers.size() - 1);
int bSzLog = (lg+1) >> 1;
int bSz = 1 << bSzLog;
indexSz = (n + bSz - 1) >> bSzLog;
v.resize(n + indexSz);
pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
build(0, 0, n, 0);
}
};