درخت رادیکالی (Sqrt Tree)¶
خب رفیق، فرض کن یه آرایه $a$ با $n$ تا عضو داریم و یه عملگر $\circ$ که خاصیت شرکتپذیری داره. خاصیت شرکتپذیری یعنی چی؟ یعنی فرقی نمیکنه اول کدوم دوتا رو با هم حساب کنی. مثلاً برای هر $x$, $y$ و $z$، این رابطه همیشه درسته: $(x \circ y) \circ z = x \circ (y \circ z)$.
خیلی از عملگرهایی که میشناسیم اینجوریان. مثلاً $\gcd$ (ب.م.م)، $\min$، $\max$، جمع (+)، and، or و 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}$ میشه. برای هر بلاک، این موارد رو پیشمحاسبه میکنیم:
- جواب کوئریهایی که داخل خود بلاک هستن و از اول بلاک شروع میشن (
prefixOp). - جواب کوئریهایی که داخل خود بلاک هستن و به آخر بلاک ختم میشن (
suffixOp).
و یه آرایه کمکی دیگه هم حساب میکنیم:
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}.
برای بلاک اول، prefixOp میشه {1, 3, 6} و suffixOp میشه {6, 5, 3}.
برای بلاک دوم، prefixOp میشه {4, 9, 15} و suffixOp میشه {15, 11, 6}.
برای بلاک سوم، prefixOp میشه {7, 15, 24} و suffixOp میشه {24, 17, 9}.
آرایه between هم این شکلی در میاد:
{
{6, 21, 45},
{0, 15, 39},
{0, 0, 24}
}
(فرض کردیم که عنصرهای نامعتبر که توشون $i > j$ هست رو با صفر پر کردیم)
حساب کردن این آرایهها کار سختی نیست و راحت توی زمان و حافظه $O(n)$ جمع میشه.
با همین چیزایی که تا الان ساختیم، میتونیم یه سری از کوئریها رو جواب بدیم. اگه یه کوئری توی یه بلاک جا نشه، میتونیم اون رو به سه تیکه بشکنیم: یه تیکه پسوندی از یه بلاک، یه تیکه که شامل چندتا بلاک کامل وسطه، و یه تیکه پیشوندی از یه بلاک دیگه. جواب نهایی هم میشه ترکیب جواب این سه تیکه: یعنی یه مقدار از suffixOp رو با یه مقدار از between و بعد با یه مقدار از prefixOp با عملگرمون ترکیب میکنیم و تمام.
اما یه مشکل داریم: اگه یه کوئری کلاً داخل یک بلاک بیفته چی؟ این آرایهها به دردمون نمیخورن. پس باید یه فکر دیگه بکنیم.
تبدیل به درخت¶
مشکل ما فقط با کوئریهاییه که کاملاً توی یه بلاک جا میشن. حالا اینجا یه ایده خفن مطرح میشه: چی میشه اگه همین ساختاری که گفتیم رو برای هر بلاک هم به صورت جداگونه بسازیم؟
آره! میتونیم این کار رو بکنیم. و این کار رو بازگشتی ادامه میدیم تا برسیم به بلاکهایی که اندازهشون ۱ یا ۲ هست. جواب کوئری برای این بلاکهای کوچولو رو میشه خیلی راحت تو زمان $O(1)$ حساب کرد.
پس اینجوری یه درخت درست میکنیم. هر گره (node) تو این درخت، نماینده یه تیکه از آرایه است. گرهای که یه بازه به طول $k$ رو نشون میده، $\sqrt{k}$ تا بچه داره – یعنی به ازای هر بلاکش یه بچه. هر گره همون سه تا آرایهای که گفتیم (prefixOp، suffixOp و between) رو برای تیکه خودش نگه میداره. ریشه درخت هم کل آرایه رو نشون میده. گرههایی که طول بازهشون ۱ یا ۲ هست، برگهای درخت حساب میشن.
یه نکته جالب دیگه اینه که ارتفاع این درخت میشه $O(\log \log n)$. چرا؟ چون اگه یه گره، آرایهای به طول $k$ داشته باشه، بچههاش طولشون میشه $\sqrt{k}$. لگاریتم $\sqrt{k}$ میشه نصف لگاریتم $k$ ($\log(\sqrt{k}) = \frac{\log{k}}{2}$). پس تو هر لایه از درخت که پایین میریم، لگاریتم اندازه نصف میشه، و در نتیجه ارتفاع کل درخت میشه $O(\log \log n)$. زمان ساخت و حافظهی مورد نیاز هم میشه $O(n \cdot \log \log n)$، چون هر عنصر آرایه دقیقاً یک بار توی هر سطح از درخت ظاهر میشه.
حالا با این ساختار درختی میتونیم کوئریها رو تو $O(\log \log n)$ جواب بدیم. کافیه تو درخت بیایم پایین تا یا به یه بازه با طول ۱ یا ۲ برسیم (که جوابش $O(1)$ هست)، یا به اولین گرهای برسیم که کوئری ما کاملاً داخل یکی از بلاکهاش قرار نمیگیره. اینکه تو این حالت چطوری جواب بدیم رو هم که تو بخش اول دیدیم.
خب، حالا میتونیم از این هم سریعتر باشیم؟
بهینهسازی کوئری و رسوندنش به $O(1)$¶
یه راه بهینهسازی واضح اینه که برای پیدا کردن گرهای که لازمش داریم، با باینری سرچ تو لایههای درخت بگردیم. این کار پیچیدگی کوئری رو به $O(\log \log \log n)$ میرسونه. ولی بازم جا برای بهتر شدن هست؟
معلومه که هست! بیا این دو تا فرض رو در نظر بگیریم:
- اندازه هر بلاک یه عدد توانی از ۲ باشه.
- همه بلاکها توی یه لایه مشخص، هماندازه باشن.
برای اینکه به این دو تا شرط برسیم، میتونیم آخر آرایهمون یه سری عنصر بیاثر (identity element) اضافه کنیم تا طولش به نزدیکترین عدد توانی از ۲ برسه.
وقتی این کار رو میکنیم، ممکنه اندازه بعضی بلاکها برای اینکه به توان ۲ برسن تا دو برابر بزرگتر شن، ولی هنوز اندازهشون از مرتبه $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$ و $r$ یکی باشن (یا به عبارت دیگه، $l \ \text{xor}\ r$ از $2^k-1$ بزرگتر نباشه).
با این ترفند، میتونیم دقیقاً لایهای از درخت رو پیدا کنیم که برای جواب دادن سریع به کوئری ما مناسبه. روش کار اینه:
-
برای هر عدد $i$ (تا سقف اندازه آرایه)، موقعیت پرارزشترین بیت (most significant bit) یکِ اون رو پیدا میکنیم. برای اینکه این کار سریع انجام بشه، از یه آرایه پیشمحاسبه شده و DP استفاده میکنیم.
-
حالا برای هر کوئری $q(l, r)$، پرارزشترین بیتِ $l \ \text{xor}\ r$ رو پیدا میکنیم. با استفاده از این مقدار، خیلی راحت لایهی مناسب درخت رو برای پردازش کوئری پیدا میکنیم. اینجا هم میتونیم از یه آرایه پیشمحاسبه شده کمک بگیریم.
برای جزئیات بیشتر، یه نگاه به کد پایین بنداز.
و اینطوری، با این کلک، میتونیم هر کوئری رو تو زمان $O(1)$ جواب بدیم. خودشه! :)
بهروزرسانی عناصر¶
درخت رادیکالی انقدر باحاله که آپدیت کردن عناصر رو هم پشتیبانی میکنه. میشه هم یه عنصر تکی رو آپدیت کرد، هم یه بازه از عناصر رو.
بهروزرسانی یک عنصر¶
کوئری update(x, val) رو در نظر بگیر که کارش اینه: $a_x = val$. باید این کوئری رو هم به اندازه کافی سریع انجام بدیم.
رویکرد ساده و اولیه¶
اول، بیا ببینیم وقتی یه عنصر عوض میشه، چه چیزایی توی درخت ما باید تغییر کنن. یه گره از درخت با طول $l$ و آرایههاش یعنی prefixOp، suffixOp و between رو در نظر بگیر. خیلی راحت میشه دید که فقط $O(\sqrt{l})$ تا از عنصرهای prefixOp و suffixOp عوض میشن (چون تغییر فقط مربوط به بلاکیه که عنصر آپدیت شده توش بوده). اما توی آرایه between اوضاع فرق میکنه و $O(l)$ تا عنصر تغییر میکنن. در نتیجه، برای آپدیت یه گره، $O(l)$ تا کار باید انجام بدیم.
یادته که هر عنصر $x$ دقیقاً توی یه گره از هر لایه درخت وجود داره. گره ریشه (لایه ۰) طولش $O(n)$ هست، گرههای لایه ۱ طولشون $O(\sqrt{n})$، لایه ۲ $O(\sqrt{\sqrt{n}})$ و الی آخر. پس پیچیدگی زمانی کل برای هر آپدیت میشه $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$.
ولی خب این خیلی کنده. نمیشه سریعتر انجامش داد؟
یه درخت رادیکالی تو دل یه درخت رادیکالی دیگه!¶
حواست باشه که گلوگاه اصلی کندی ما، بازسازی کردن آرایه between توی گره ریشه است. برای اینکه سریعترش کنیم، بیا از شر این آرایه خلاص شیم! به جای آرایه between توی گره ریشه، یه درخت رادیکالی دیگه میسازیم و نگهش میداریم. اسم این درخت جدیده رو میذاریم index. کار این درخت index دقیقاً همون کار between هست: به کوئریهایی که روی بازههایی از بلاکها هستن جواب میده. فقط حواست باشه، بقیه گرههای درخت index ندارن و همون آرایههای between خودشون رو نگه میدارن.
پس یه درخت رادیکالی رو میگیم شاخصدار (indexed) اگه گره ریشهاش index داشته باشه. و به درختی که گره ریشهاش آرایه between داره میگیم بدون شاخص (unindexed). حواست باشه که خودِ درختِ index، یه درخت بدون شاخص هست.
با این تعریفها، الگوریتم آپدیت یه درخت شاخصدار اینجوری میشه:
-
آپدیت
prefixOpوsuffixOpکه هزینهاش $O(\sqrt{n})$ هست. -
آپدیت
index. این درخت خودش روی دادههایی به طول $O(\sqrt{n})$ ساخته شده و ما فقط یه دونه آیتم (که نماینده بلاک تغییر کرده است) رو توش آپدیت میکنیم. پس هزینه این مرحله هم میشه $O(\sqrt{n})$. برای این کار از همون الگوریتم «کند» که اول این بخش گفتیم استفاده میکنیم. -
سراغ گره بچهای میریم که بلاک تغییر کرده رو نشون میده و اون رو هم با الگوریتم «کند» توی $O(\sqrt{n})$ آپدیت میکنیم.
یه نکته مهم اینه که پیچیدگی کوئری هنوز هم $O(1)$ باقی میمونه: چون توی یه کوئری لازم نیست بیشتر از یه بار از index استفاده کنیم، و یه کوئری روی index هم خودش $O(1)$ طول میکشه.
در نتیجه، پیچیدگی زمانی کل برای آپدیت یه عنصر میشه $O(\sqrt{n})$. عالی شد! :)
آپدیت کردن یک بازه (Range Update)¶
درخت رادیکالی همچنین میتونه کارهایی مثل مقداردهی به یک بازه کامل رو هم انجام بده. massUpdate(x, l, r) یعنی برای تمام $i$ ها از $l$ تا $r$، قرار بده $a_i = x$.
برای این کار دو تا راه داریم که یه بدهبستان (trade-off) با هم دارن:
* راه اول massUpdate رو توی $O(\sqrt{n}\cdot \log \log n)$ انجام میده و پیچیدگی کوئری رو همون $O(1)$ نگه میداره.
* راه دوم massUpdate رو توی $O(\sqrt{n})$ انجام میده، ولی در عوض پیچیدگی کوئری میشه $O(\log \log n)$.
ایده اصلی اینجا استفاده از انتشار با تأخیر (lazy propagation) هست، خیلی شبیه کاری که توی درخت بازهای (segment tree) میکنیم: بعضی گرهها رو به عنوان تنبل (lazy) علامت میزنیم، یعنی آپدیتهاشون رو بعداً هر وقت لازم شد اعمال (push) میکنیم. اما یه فرق مهم با درخت بازهای وجود داره: اینجا push کردن یه گره هزینه زیادی داره و نمیتونیم وسط کوئری انجامش بدیم. مثلاً تو لایه ۰، push کردن یه گره $O(\sqrt{n})$ طول میکشه. برای همین، ما وسط کوئریها گرهها رو push نمیکنیم، فقط چک میکنیم که گره فعلی یا پدرش lazy هست یا نه و این موضوع رو تو محاسباتمون لحاظ میکنیم.
رویکرد اول¶
تو این روش، قرار میذاریم که فقط گرههای لایه ۱ (که طولشون $O(\sqrt{n})$ هست) میتونن lazy بشن. وقتی یه همچین گرهی رو push میکنیم، کل زیردرختش، به اضافهی خودش، توی $O(\sqrt{n}\cdot \log \log n)$ آپدیت میشه. فرآیند massUpdate اینطوریه:
-
گرههای لایه ۱ و بلاکهای مربوط بهشون رو در نظر بگیر.
-
بعضی بلاکها کامل توسط
massUpdateپوشش داده میشن. اونا رو تو زمان $O(\sqrt{n})$ به عنوان lazy علامت بزن. -
بعضی بلاکها ناقص پوشش داده میشن. حواست باشه که حداکثر دو تا از این بلاکها وجود داره. اونا رو توی $O(\sqrt{n}\cdot \log \log n)$ بازسازی کن. اگه lazy بودن، حواست به این قضیه باشه.
-
برای اون بلاکهایی که ناقص پوشش داده شدن،
prefixOpوsuffixOpرو توی $O(\sqrt{n})$ آپدیت کن (چون فقط دو تا از این بلاکها داریم). -
indexرو در $O(\sqrt{n}\cdot \log \log n)$ بازسازی کن.
اینطوری massUpdate سریع انجام میشه. اما این lazy propagation چه تأثیری روی کوئریها داره؟
-
اگه کوئری ما کامل توی یه بلاک lazy جا بشه، جوابش رو با در نظر گرفتن اون آپدیت تنبل حساب میکنیم. این کار $O(1)$ طول میکشه.
-
اگه کوئری ما شامل چندتا بلاک بشه که بعضیاشون lazy هستن، فقط باید حواسمون به آپدیت تنبل چپترین و راستترین بلاک باشه. جواب بقیه بلاکهای وسط با
indexحساب میشه که از قبل جواب بلاکهای lazy رو میدونه (چون بعد از هر تغییری بازسازی میشه). این هم $O(1)$ میشه.
پس پیچیدگی کوئری همون $O(1)$ باقی میمونه.
رویکرد دوم¶
تو این روش، هر گرهی (به جز ریشه) میتونه lazy باشه. حتی گرههای داخل index هم میتونن lazy باشن. برای همین، وقتی یه کوئری رو پردازش میکنیم، باید تمام گرههای پدر رو برای پیدا کردن تگهای lazy چک کنیم، که این باعث میشه پیچیدگی کوئری بشه $O(\log \log n)$.
اما massUpdate سریعتر میشه. فرآیندش این شکلیه:
-
بعضی بلاکها کامل توسط
massUpdateپوشش داده میشن. پس تگ lazy بهشون اضافه میشه. این کار $O(\sqrt{n})$ هزینه داره. -
برای بلاکهایی که ناقص پوشش داده شدن،
prefixOpوsuffixOpرو توی $O(\sqrt{n})$ آپدیت کن (چون حداکثر دوتا از این نوع بلاک داریم). -
یادت نره که
indexرو هم آپدیت کنی. این کار هم $O(\sqrt{n})$ طول میکشه (با همون الگوریتمmassUpdate). -
برای زیردرختهای بدون شاخص، آرایه
betweenرو آپدیت کن. -
به گرههایی برو که نماینده بلاکهای ناقص پوشش داده شده هستن و
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);
}
};