Квадрат язгуурын мод¶
$n$ элемент агуулсан $a$ массив ба associative чанарыг хангах $\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$-г тооцоолох хэрэгтэй.
Квадрат язгуурын мод нь ийм асуулгуудыг $O(1)$ хугацаанд боловсруулж чадах бөгөөд урьдчилсан боловсруулалтын хугацаа нь $O(n \cdot \log \log n)$, санах ой нь $O(n \cdot \log \log n)$ байна.
Тайлбар¶
Квадрат язгуурын задаргаа байгуулах¶
Квадрат язгуурын задаргаа хийе. Бид массиваа $\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$ эсвэл $2$ болтол үүнийг рекурсивээр хийнэ. Ийм блокуудын хариуг $O(1)$ хугацаанд амархан тооцоолж болно.
Тэгэхээр бид мод авна. Модны зангилаа бүр массивын ямар нэг хэрчмийг илэрхийлнэ. $k$ хэмжээтэй массивын хэрчмийг илэрхийлж буй зангилаа $\sqrt{k}$ хүүхэдтэй байна — блок бүрд нэг. Мөн зангилаа бүр өөрийн агуулж буй хэрчмийн хувьд дээр тайлбарласан гурван массивыг агуулна. Модны үндэс нь бүхэл массивыг илэрхийлнэ. $1$ эсвэл $2$ хэрчмийн урттай зангилаанууд нь навчнууд болно.
Мөн энэ модны өндөр $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$ эсвэл $2$ урттай хэрчимтэй тааралдтал (түүний хариуг $O(1)$ хугацаанд тооцоолж болно) эсвэл бидний асуулга нэг блокт бүхэлдээ багтахгүй байх эхний хэрчимтэй тааралдтал модоор доош явж болно. Энэ тохиолдолд асуулгад хэрхэн хариулах талаар эхний хэсгийг үз.
За, одоо бид асуулга тутамд $O(\log \log n)$ хийж чадна. Үүнийг илүү хурдан хийж болох уу?
Асуулгын complexity-г оновчлох¶
Хамгийн илэрхий оновчлолуудын нэг бол бидэнд хэрэгтэй модны зангилааг хоёртын хайлтаар олох явдал юм. Хоёртын хайлт ашиглан бид асуулга тутамд $O(\log \log \log n)$ complexity-д хүрч чадна. Үүнийг бүр илүү хурдан хийж чадах уу?
Хариулт нь тийм. Дараах хоёр зүйлийг таамаглая:
- Блок бүрийн хэмжээ нь хоёрын зэрэг байна.
- Давхарга бүр дээрх бүх блок тэнцүү байна.
Үүнд хүрэхийн тулд бид массивынхаа хэмжээ хоёрын зэрэг болтол хэдэн тэг элемент нэмж болно.
Үүнийг ашиглах үед зарим блокийн хэмжээ хоёрын зэрэг болохын тулд хоёр дахин том болж болох ч энэ нь хэмжээгээрээ $O(\sqrt{k})$ хэвээр байх ба хэрчим дэх массивуудыг байгуулах шугаман complexity-г бид хадгална.
Одоо бид асуулга $2^k$ хэмжээтэй блокт бүхэлдээ багтах эсэхийг амархан шалгаж чадна. Асуулгын $l$ ба $r$ хязгаарыг хоёртын хэлбэрээр бичье (бид 0-ээс эхлэх индексжүүлэлт ашиглана). Жишээ нь $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$ (бидний тохиолдолд $4$) битээрээ ялгаатай байж болохыг бид харж байна. Бидний тохиолдолд $l$ ба $r$ нь хамгийн бага дөрвөн битээс бусад битүүдээрээ тэнцүү тул тэдгээр нэг блокт оршино.
Тиймээс бид $k$-аас олон бага бит ялгаатай биш эсэхийг (өөрөөр хэлбэл $l\ \text{xor}\ r$ нь $2^k-1$-ээс хэтрэхгүй эсэхийг) шалгах хэрэгтэй.
Энэ ажиглалтыг ашиглан бид асуулгад хурдан хариулахад тохиромжтой давхаргыг олж чадна. Үүнийг хэрхэн хийх вэ:
-
Массивын хэмжээнээс хэтрэхгүй $i$ бүрийн хувьд бид $1$-тэй тэнцүү хамгийн өндөр битийг олно. Үүнийг хурдан хийхийн тулд бид DP ба урьдчилан тооцоолсон массив ашиглана.
-
Одоо $q(l, r)$ бүрийн хувьд бид $l\ \text{xor}\ r$-ийн хамгийн өндөр битийг олох ба энэ мэдээллийг ашиглан асуулгыг хялбархан боловсруулж чадах давхаргыг сонгоход амархан болно. Бид энд мөн урьдчилан тооцоолсон массив ашиглаж болно.
Дэлгэрэнгүйг доорх кодоос үз.
Тэгэхээр үүнийг ашиглан бид асуулга бүрд $O(1)$ хугацаанд хариулж чадна. Ура! :)
Элемент шинэчлэх¶
Бид мөн квадрат язгуурын мод дахь элементүүдийг шинэчилж чадна. Ганц элементийн шинэчлэл ба хэрчим дээрх шинэчлэл хоёуланг нь дэмжинэ.
Ганц элемент шинэчлэх¶
$a_x = val$ гэсэн олголт хийдэг $\text{update}(x, val)$ асуулгыг авч үзье. Бид энэ асуулгыг хангалттай хурдан гүйцэтгэх хэрэгтэй.
Гэнэн арга¶
Эхлээд ганц элемент өөрчлөгдөх үед модонд юу өөрчлөгддөгийг харцгаая. $l$ урттай модны зангилаа ба түүний $\text{prefixOp}$, $\text{suffixOp}$, $\text{between}$ массивуудыг авч үзье. $\text{prefixOp}$ ба $\text{suffixOp}$-оос зөвхөн $O(\sqrt{l})$ элемент өөрчлөгдөх нь (зөвхөн өөрчлөгдсөн элемент бүхий блокийн дотор) амархан харагдана. $\text{between}$-д $O(l)$ элемент өөрчлөгдөнө. Тиймээс модны зангилаанд $O(l)$ элемент шинэчлэгдэнэ.
Дурын элемент $x$ нь давхарга бүрд яг нэг модны зангилаанд байдгийг бид санаж байна. Үндэс зангилаа (давхарга $0$) $O(n)$ урттай, давхарга $1$ дээрх зангилаанууд $O(\sqrt{n})$ урттай, давхарга $2$ дээрх зангилаанууд $O(\sqrt{\sqrt{n}})$ урттай гэх мэт. Тиймээс шинэчлэлт тутмын time complexity нь $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$ болно.
Гэвч энэ нь хэтэрхий удаан. Үүнийг илүү хурдан хийж болох уу?
Квадрат язгуурын мод доторх квадрат язгуурын мод¶
Шинэчлэлтийн саад бол үндэс зангилааны $\text{between}$-г дахин байгуулах явдал гэдгийг анзаар. Модыг оновчлохын тулд энэ массиваас салцгаая! $\text{between}$ массивын оронд бид үндэс зангилааны хувьд өөр нэг квадрат язгуурын мод хадгална. Үүнийг $\text{index}$ гэж нэрлэе. Энэ нь $\text{between}$-тэй ижил үүрэг гүйцэтгэнэ — блокуудын хэрчим дээрх асуулгуудад хариулна. Модны бусад зангилаанууд $\text{index}$-гүй бөгөөд тэд $\text{between}$ массиваа хадгалсаар байхыг анзаар.
Хэрэв квадрат язгуурын модны үндэс зангилаа $\text{index}$-тэй бол уг мод индексжүүлсэн гэж нэрлэгдэнэ. Үндэс зангилаандаа $\text{between}$ массивтай квадрат язгуурын мод нь индексжүүлээгүй юм. $\text{index}$ нь өөрөө индексжүүлээгүй гэдгийг анзаар.
Тэгэхээр бидэнд индексжүүлсэн модыг шинэчлэх дараах алгоритм байна:
-
$\text{prefixOp}$ ба $\text{suffixOp}$-г $O(\sqrt{n})$ хугацаанд шинэчилнэ.
-
$\text{index}$-г шинэчилнэ. Энэ нь $O(\sqrt{n})$ урттай ба бид түүн дотор зөвхөн нэг элементийг (өөрчлөгдсөн блокийг илэрхийлэх) шинэчлэх хэрэгтэй. Тиймээс энэ алхмын time complexity нь $O(\sqrt{n})$ байна. Үүнийг хийхийн тулд бид энэ хэсгийн эхэнд тайлбарласан ("удаан") алгоритмыг ашиглаж болно.
-
Өөрчлөгдсөн блокийг илэрхийлж буй хүүхэд зангилаа руу орж, "удаан" алгоритмаар түүнийг $O(\sqrt{n})$ хугацаанд шинэчилнэ.
Асуулгын complexity $O(1)$ хэвээр байгааг анзаар: бид асуулгад $\text{index}$-г нэгээс олон удаа ашиглах шаардлагагүй бөгөөд энэ нь $O(1)$ хугацаа авна.
Тэгэхээр ганц элемент шинэчлэх нийт time complexity нь $O(\sqrt{n})$ байна. Ура! :)
Хэрчим шинэчлэх¶
Квадрат язгуурын мод нь хэрчим дээр элемент олгох зэрэг зүйлийг мөн хийж чадна. $\text{massUpdate}(x, l, r)$ гэдэг нь $l \le i \le r$ байх бүх $i$-ийн хувьд $a_i = x$ гэсэн үг.
Үүнийг хийх хоёр арга байна: нэг нь $\text{massUpdate}$-г $O(\sqrt{n}\cdot \log \log n)$ хугацаанд хийж, асуулга тутамд $O(1)$-г хадгална. Хоёр дахь нь $\text{massUpdate}$-г $O(\sqrt{n})$ хугацаанд хийх боловч асуулгын complexity $O(\log \log n)$ болно.
Бид хэрчмийн модонд хийдэгтэй ижил аргаар залхуу тархалт хийнэ: бид зарим зангилааг залхуу гэж тэмдэглэх ба энэ нь шаардлагатай үед тэднийг түлхэнэ гэсэн үг. Гэвч хэрчмийн модноос ялгаатай нэг зүйл бий: зангилааг түлхэх нь үнэтэй тул үүнийг асуулгын дотор хийж болохгүй. Давхарга $0$ дээр зангилаа түлхэхэд $O(\sqrt{n})$ хугацаа зарцуулагдана. Тиймээс бид асуулгын дотор зангилаа түлхэхгүй, зөвхөн одоогийн зангилаа эсвэл түүний эцэг залхуу эсэхийг хараад асуулга гүйцэтгэх явцад үүнийг тооцоолон авч үзнэ.
Эхний арга¶
Эхний аргад зөвхөн давхарга $1$ дээрх зангилаанууд ($O(\sqrt{n}$ урттай) залхуу байж болно гэж бид үзнэ. Ийм зангилааг түлхэх үед энэ нь өөрийгөө оруулаад бүх дэд модоо $O(\sqrt{n}\cdot \log \log n)$ хугацаанд шинэчилнэ. $\text{massUpdate}$ үйл явц дараах байдлаар хийгдэнэ:
-
Давхарга $1$ дээрх зангилаанууд ба тэдгээрт харгалзах блокуудыг авч үзнэ.
-
Зарим блок $\text{massUpdate}$-ээр бүхэлдээ бүрхэгдэнэ. Тэдгээрийг $O(\sqrt{n})$ хугацаанд залхуу гэж тэмдэглэнэ.
-
Зарим блок хэсэгчлэн бүрхэгдэнэ. Ийм төрлийн блок хоёроос олон биш болохыг анзаар. Тэдгээрийг $O(\sqrt{n}\cdot \log \log n)$ хугацаанд дахин байгуулна. Хэрэв тэд залхуу байсан бол үүнийг тооцоолон авч үз.
-
Хэсэгчлэн бүрхэгдсэн блокуудын хувьд $\text{prefixOp}$ ба $\text{suffixOp}$-г $O(\sqrt{n})$ хугацаанд шинэчилнэ (учир нь ийм блок ердөө хоёр байна).
-
$\text{index}$-г $O(\sqrt{n}\cdot \log \log n)$ хугацаанд дахин байгуулна.
Тэгэхээр бид $\text{massUpdate}$-г хурдан хийж чадна. Гэвч залхуу тархалт асуулгуудад хэрхэн нөлөөлөх вэ? Тэдгээр дараах өөрчлөлттэй болно:
-
Хэрэв бидний асуулга залхуу блокт бүхэлдээ орших бол түүнийг тооцоолж, залхуу-г тооцоолон авч үзнэ. $O(1)$.
-
Хэрэв бидний асуулга олон блокоос бүрдэх ба тэдгээрийн зарим нь залхуу бол бид зөвхөн хамгийн зүүн ба хамгийн баруун блокийн залхуу-г анхаарах хэрэгтэй. Бусад блокуудыг $\text{index}$ ашиглан тооцоолох ба энэ нь залхуу блок дээрх хариуг аль хэдийн мэднэ (учир нь өөрчлөлт бүрийн дараа дахин байгуулагддаг). $O(1)$.
Асуулгын complexity $O(1)$ хэвээр байна.
Хоёр дахь арга¶
Энэ аргад зангилаа бүр (үндсийг эс тооцвол) залхуу байж болно. $\text{index}$ доторх зангилаанууд хүртэл залхуу байж болно. Тиймээс асуулга боловсруулах явцад бид бүх эцэг зангилаанаас залхуу таг хайх ёстой, өөрөөр хэлбэл асуулгын complexity $O(\log \log n)$ болно.
Гэвч $\text{massUpdate}$ илүү хурдан болно. Энэ нь дараах байдалтай байна:
-
Зарим блок $\text{massUpdate}$-ээр бүрэн бүрхэгдэнэ. Тиймээс тэдгээрт залхуу таг нэмэгдэнэ. Энэ нь $O(\sqrt{n})$.
-
Хэсэгчлэн бүрхэгдсэн блокуудын хувьд $\text{prefixOp}$ ба $\text{suffixOp}$-г $O(\sqrt{n})$ хугацаанд шинэчилнэ (учир нь ийм блок ердөө хоёр байна).
-
Индексийг шинэчлэхээ бүү мартаарай. Энэ нь $O(\sqrt{n})$ (бид ижил $\text{massUpdate}$ алгоритмыг ашиглана).
-
Индексжүүлээгүй дэд модуудын хувьд $\text{between}$ массивыг шинэчилнэ.
-
Хэсэгчлэн бүрхэгдсэн блокуудыг илэрхийлж буй зангилаанууд руу орж, $\text{massUpdate}$-г рекурсивээр дуудна.
Рекурсив дуудалт хийхдээ бид угтвар эсвэл дагаврын $\text{massUpdate}$ хийдгийг анзаар. Гэвч угтвар ба дагаврын шинэчлэлийн хувьд бид нэгээс олон хэсэгчлэн бүрхэгдсэн хүүхэдтэй байж чадахгүй. Тиймээс бид давхарга $1$ дээр нэг зангилаа, давхарга $2$ дээр хоёр зангилаа, түүнээс гүн дурын түвшинд хоёр зангилаа зочилно. Тэгэхээр time complexity нь $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$ байна. Эндэх арга нь хэрчмийн модны бөөн шинэчлэлтэй төстэй.
Implementation¶
The following implementation of Sqrt Tree can perform the following operations: build in $O(n \cdot \log \log n)$, answer queries in $O(1)$ and update an element in $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);
}
};