Агуулгыг алгасах

Хэрчмийн мод

Хэрчмийн мод гэдэг нь массивын интервалуудын тухай мэдээллийг мод хэлбэрээр хадгалдаг өгөгдлийн бүтэц юм. Энэ нь массив дээрх интервалын асуулгад үр ашигтай хариулах боломж олгохын зэрэгцээ массивыг хурдан өөрчлөх боломж олгох хангалттай уян хатан хэвээр байдаг. Үүнд дараалсан массивын элементүүд $a[l \dots r]$-ийн нийлбэрийг олох буюу ийм интервал дахь хамгийн бага элементийг $O(\log n)$ хугацаанд олох зэрэг орно. Ийм асуулгуудад хариулах хооронд Хэрчмийн мод нь нэг элементийг солих буюу бүр бүхэл дэд хэрчмийн элементүүдийг өөрчлөх (жишээ нь бүх элемент $a[l \dots r]$-д дурын утга олгох буюу дэд хэрчмийн бүх элементэд утга нэмэх) замаар массивыг өөрчлөх боломж олгоно.

Ерөнхийдөө Хэрчмийн мод бол маш уян хатан өгөгдлийн бүтэц бөгөөд түүгээр асар олон тооны бодлого бодож болно. Түүнчлэн илүү нарийн төвөгтэй үйлдэл хэрэглэж, илүү нарийн төвөгтэй асуулгад хариулах боломжтой (Хэрчмийн модны дэвшилтэт хувилбарууд-ыг үз). Ялангуяа Хэрчмийн модыг илүү өндөр хэмжээст рүү амархан ерөнхийлж болно. Жишээ нь хоёр хэмжээст Хэрчмийн модоор та өгөгдсөн матрицын ямар нэг дэд тэгш өнцөгт дээрх нийлбэр буюу минимумын асуулгад ердөө $O(\log^2 n)$ хугацаанд хариулж чадна.

Хэрчмийн модны нэг чухал шинж чанар нь зөвхөн шугаман хэмжээний санах ой шаарддаг явдал юм. Стандарт Хэрчмийн мод $n$ хэмжээтэй массив дээр ажиллахад $4n$ орой шаардана.

Хэрчмийн модны хамгийн энгийн хэлбэр

Хялбараар эхлэхийн тулд бид Хэрчмийн модны хамгийн энгийн хэлбэрийг авч үзнэ. Бид нийлбэрийн асуулгад үр ашигтай хариулахыг хүсэж байна. Бидний бодлогын албан ёсны тодорхойлолт нь: $a[0 \dots n-1]$ массив өгөгдсөн үед Хэрчмийн мод нь $l$ ба $r$ индексийн хоорондох элементүүдийн нийлбэрийг (өөрөөр хэлбэл $\sum_{i=l}^r a[i]$ нийлбэрийг тооцоолох) олж чаддаг байх ёстой бөгөөд мөн массив дахь элементүүдийн утгыг өөрчлөхийг (өөрөөр хэлбэл $a[i] = x$ хэлбэрийн олголт гүйцэтгэхийг) зохицуулах ёстой. Хэрчмийн мод нь хоёулаа асуулгыг $O(\log n)$ хугацаанд боловсруулж чаддаг байх ёстой.

Энэ нь илүү энгийн аргуудаас дэвшилттэй. Гэнэн массивын хэрэгжүүлэлт — зүгээр л энгийн массив ашиглах — нь элементүүдийг $O(1)$-д шинэчилж чадна, гэхдээ нийлбэрийн асуулга бүрийг тооцоолоход $O(n)$ шаардана. Урьдчилан тооцоолсон угтвар нийлбэрүүд нь нийлбэрийн асуулгыг $O(1)$-д тооцоолж чадна, гэхдээ массивын элементийг шинэчлэхэд угтвар нийлбэрүүдэд $O(n)$ өөрчлөлт шаардана.

Хэрчмийн модны бүтэц

Массивын хэрчмүүдийн тухайд бид хуваа ба ялагтун аргыг хэрэглэж болно. Бид бүхэл массивын элементүүдийн нийлбэрийг, өөрөөр хэлбэл $a[0 \dots n-1]$ хэрчмийн нийлбэрийг тооцоолж хадгална. Дараа нь бид массивыг $a[0 \dots (n-1)/2]$ ба $a[(n+1)/2 \dots n-1]$ гэсэн хоёр хагаст хувааж, хагас тус бүрийн нийлбэрийг тооцоолж хадгална. Эдгээр хоёр хагас тус бүр нь эргээд хоёр хуваагдаж, бүх хэрчим $1$ хэмжээтэй болтол ингэж үргэлжилнэ.

Бид эдгээр хэрчмийг хоёртын мод үүсгэж байгаа гэж үзэж болно: энэ модны үндэс нь $a[0 \dots n-1]$ хэрчим бөгөөд орой бүр (навч оройнуудаас бусад) яг хоёр хүүхэд оройтой. Ихэнх хэрэгжүүлэлтэд мод нь ил байгуулагддаггүй ч (Implementation-г үз) өгөгдлийн бүтцийг "Хэрчмийн мод" гэж нэрлэдгийн учир нь энэ юм.

$a = [1, 3, -2, 8, -7]$ массив дээрх ийм Хэрчмийн модны дүрслэл энд байна:

"Нийлбэрийн Хэрчмийн мод"

Өгөгдлийн бүтцийн энэ богино тайлбараас бид Хэрчмийн мод зөвхөн шугаман тооны орой шаарддаг гэж аль хэдийн дүгнэж болно. Модны эхний түвшин ганц зангилаа (үндэс) агуулна, хоёр дахь түвшин хоёр орой агуулна, гурав дахьд нь дөрвөн орой агуулах ба оройн тоо $n$ хүртэл ингэж үргэлжилнэ. Тиймээс хамгийн муу тохиолдолд оройн тоог $1 + 2 + 4 + \dots + 2^{\lceil\log_2 n\rceil} \lt 2^{\lceil\log_2 n\rceil + 1} \lt 4n$ нийлбэрээр үнэлж болно.

$n$ нь хоёрын зэрэг биш үед Хэрчмийн модны бүх түвшин бүрэн дүүрэхгүй гэдгийг тэмдэглэх нь зүйтэй. Бид энэ зан төлөвийг зурган дээр харж болно. Одоохондоо бид энэ баримтыг мартаж болох ч хожим хэрэгжүүлэлтийн явцад энэ нь чухал болно.

Хэрчмийн модны өндөр нь $O(\log n)$ байна, учир нь үндэснээс навч руу доош явахад хэрчмүүдийн хэмжээ ойролцоогоор хоёр дахин багасна.

Байгуулалт

Хэрчмийн модыг байгуулахаас өмнө бид дараахыг шийдэх хэрэгтэй:

  1. хэрчмийн модны зангилаа бүрд хадгалагдах утга. Жишээ нь нийлбэрийн хэрчмийн модонд зангилаа нь өөрийн $[l, r]$ интервал дахь элементүүдийн нийлбэрийг хадгална.
  2. хэрчмийн мод дахь хоёр ах дүүг нэгтгэдэг нэгтгэх үйлдэл. Жишээ нь нийлбэрийн хэрчмийн модонд $a[l_1 \dots r_1]$ ба $a[l_2 \dots r_2]$ интервалуудад харгалзах хоёр зангилаа нь хоёр зангилааны утгыг нэмэх замаар $a[l_1 \dots r_2]$ интервалд харгалзах зангилаа болж нэгтгэгдэнэ.

Хэрэв оройн харгалзах хэрчим нь анхны массивын зөвхөн нэг утгыг бүрхэж байвал тэр орой нь "навч орой" болохыг анзаар. Энэ нь хэрчмийн модны хамгийн доод түвшинд байрлана. Түүний утга нь (харгалзах) $a[i]$ элементтэй тэнцүү байна.

Одоо хэрчмийн модыг байгуулахын тулд бид хамгийн доод түвшнээс (навч оройнуудаас) эхлээд тэдгээрт харгалзах утгуудыг ононо. Эдгээр утган дээр үндэслэн бид merge функц ашиглан өмнөх түвшний утгуудыг тооцоолж чадна. Тэдгээр дээр үндэслэн бид өмнөхийн утгуудыг тооцоолж, үндэс оройд хүртэл энэ процедурыг давтана.

Энэ үйлдлийг эсрэг чиглэлд буюу үндэс оройноос навч орой руу рекурсивээр тайлбарлах нь тохиромжтой. Байгуулалтын процедур нь навч биш орой дээр дуудагдвал дараахыг хийнэ:

  1. хоёр хүүхэд оройн утгыг рекурсивээр байгуулна
  2. эдгээр хүүхдийн тооцоолсон утгыг нэгтгэнэ.

Бид байгуулалтыг үндэс оройноос эхлэх ба ингэснээр бүхэл хэрчмийн модыг тооцоолж чадна.

Нэгтгэх үйлдэл тогтмол хугацаатай гэж үзвэл энэ байгуулалтын time complexity нь $O(n)$ юм (нэгтгэх үйлдэл $n$ удаа дуудагдах ба энэ нь хэрчмийн мод дахь дотоод зангилааны тоотой тэнцүү).

Нийлбэрийн асуулга

Одоохондоо бид нийлбэрийн асуулгад хариулах гэж байна. Оролт болгон бид $l$ ба $r$ гэсэн хоёр бүхэл тоо хүлээн авах ба $a[l \dots r]$ хэрчмийн нийлбэрийг $O(\log n)$ хугацаанд тооцоолох ёстой.

Үүний тулд бид Хэрчмийн модыг тойрч, хэрчмүүдийн урьдчилан тооцоолсон нийлбэрүүдийг ашиглана. Бид одоогоор $a[tl \dots tr]$ хэрчмийг бүрхэх оройд байна гэж үзье. Гурван боломжит тохиолдол бий.

Хамгийн хялбар тохиолдол бол $a[l \dots r]$ хэрчим нь одоогийн оройн харгалзах хэрчимтэй тэнцүү (өөрөөр хэлбэл $a[l \dots r] = a[tl \dots tr]$) байх үе бөгөөд тэгвэл бид дуусч, оройд хадгалагдсан урьдчилан тооцоолсон нийлбэрийг буцааж болно.

Өөр хувилбараар асуулгын хэрчим зүүн эсвэл баруун хүүхдийн мужид бүхэлдээ багтаж болно. Зүүн хүүхэд нь $a[tl \dots tm]$ хэрчмийг, баруун орой нь $a[tm + 1 \dots tr]$ хэрчмийг бүрхэх ба $tm = (tl + tr) / 2$ болохыг сана. Энэ тохиолдолд бид харгалзах хэрчим нь асуулгын хэрчмийг бүрхэж буй хүүхэд орой руу зүгээр л явж, тэр оройтой энд тайлбарласан алгоритмыг гүйцэтгэж болно.

Дараа нь сүүлийн тохиолдол буюу асуулгын хэрчим хоёр хүүхэдтэй хоёуланд нь огтлолцоно. Энэ тохиолдолд бидэнд хүүхэд тус бүрд нэг, нийт хоёр рекурсив дуудалт хийхээс өөр сонголт байхгүй. Эхлээд бид зүүн хүүхэд рүү явж, энэ оройн хувьд хэсэгчилсэн хариуг тооцоолно (өөрөөр хэлбэл асуулгын хэрчим ба зүүн хүүхдийн хэрчмийн огтлолцол дахь утгуудын нийлбэрийг), дараа нь баруун хүүхэд рүү явж, тэр оройг ашиглан хэсэгчилсэн хариуг тооцоолж, дараа нь хариунуудыг нэмэх замаар нэгтгэнэ. Өөрөөр хэлбэл зүүн хүүхэд нь $a[tl \dots tm]$ хэрчмийг, баруун хүүхэд нь $a[tm+1 \dots tr]$ хэрчмийг илэрхийлдэг тул бид зүүн хүүхдийг ашиглан $a[l \dots tm]$ нийлбэрийн асуулгыг, баруун хүүхдийг ашиглан $a[tm+1 \dots r]$ нийлбэрийн асуулгыг тооцоолно.

Тиймээс нийлбэрийн асуулгыг боловсруулах нь өөрийгөө зүүн эсвэл баруун хүүхэдтэй нэг удаа (асуулгын хязгаарыг өөрчлөхгүйгээр), эсвэл зүүнд нэг, баруунд нэг удаа хоёр удаа (асуулгыг хоёр дэд асуулгад хуваах замаар) рекурсивээр дууддаг функц юм. Одоогийн асуулгын хэрчмийн хязгаар нь одоогийн оройн хэрчмийн хязгаартай давхцах үед рекурс дуусна. Тэр тохиолдолд хариу нь модонд хадгалагдсан, энэ хэрчмийн нийлбэрийн урьдчилан тооцоолсон утга байх болно.

Өөрөөр хэлбэл асуулгын тооцоолол нь модны бүх шаардлагатай мөчрөөр тархаж, мод дахь хэрчмүүдийн урьдчилан тооцоолсон нийлбэрийн утгуудыг ашигладаг модны тойролт юм.

Бид тойролтыг Хэрчмийн модны үндэс оройноос эхлэх нь илэрхий.

Процедурыг дараах зурган дээр дүрсэлсэн. Дахин $a = [1, 3, -2, 8, -7]$ массивыг ашигласан бөгөөд энд бид $\sum_{i=2}^4 a[i]$ нийлбэрийг тооцоолохыг хүсэж байна. Өнгөт оройнуудад зочлох ба бид ногоон оройнуудын урьдчилан тооцоолсон утгыг ашиглана. Энэ нь бидэнд $-2 + 1 = -1$ үр дүнг өгнө.

"Нийлбэрийн Хэрчмийн модны асуулга"

Яагаад энэ алгоритмын complexity нь $O(\log n)$ вэ? Энэ complexity-г үзүүлэхийн тулд бид модны түвшин бүрийг харна. Түвшин бүрд бид дөрвөөс олон биш оройд зочилдог нь тогтоогддог. Модны өндөр нь $O(\log n)$ тул бид хүссэн ажиллах хугацаагаа авна.

Энэ саналыг (түвшин бүрд хамгийн ихдээ дөрвөн орой) индукцээр үнэн болохыг үзүүлж болно. Эхний түвшинд бид зөвхөн нэг оройд буюу үндэс оройд зочилдог тул энд бид дөрвөөс бага оройд зочилно. Одоо дурын түвшинг харцгаая. Индукцийн таамаглалаар бид хамгийн ихдээ дөрвөн оройд зочилно. Хэрэв бид хамгийн ихдээ хоёр оройд л зочилбол дараагийн түвшин хамгийн ихдээ дөрвөн оройтой байна. Энэ нь тривиаль, учир нь орой бүр хамгийн ихдээ хоёр рекурсив дуудалт үүсгэж чадна. Тиймээс бид одоогийн түвшинд гурав эсвэл дөрвөн оройд зочилдог гэж үзье. Эдгээр оройноос бид дундах оройнуудыг илүү нарийн шинжилнэ. Нийлбэрийн асуулга нь тасралтгүй дэд массивын нийлбэрийг асуудаг тул дундах зочилсон оройнуудад харгалзах хэрчмүүд нь нийлбэрийн асуулгын хэрчмээр бүрэн бүрхэгдэнэ гэдгийг бид мэднэ. Тиймээс эдгээр орой ямар ч рекурсив дуудалт хийхгүй. Тэгэхээр зөвхөн хамгийн зүүн ба хамгийн баруун орой л рекурсив дуудалт хийх боломжтой. Тэдгээр нь хамгийн ихдээ дөрвөн рекурсив дуудалт үүсгэх тул дараагийн түвшин ч мөн энэ баталгааг хангана. Нэг мөчир асуулгын зүүн хязгаарт, хоёр дахь мөчир баруун хязгаарт ойртдог гэж бид хэлж болно.

Тиймээс бид нийтдээ хамгийн ихдээ $4 \log n$ оройд зочилно, энэ нь $O(\log n)$ ажиллах хугацаатай тэнцүү.

Дүгнэвэл асуулга нь оролтын хэрчмийг бүх нийлбэр нь аль хэдийн урьдчилан тооцоологдож модонд хадгалагдсан хэд хэдэн дэд хэрчимд хуваах замаар ажиллана. Хэрэв бид асуулгын хэрчим оройн хэрчимтэй давхцах үед хуваахаа зогсоовол бидэнд зөвхөн $O(\log n)$ ийм хэрчим хэрэгтэй бөгөөд энэ нь Хэрчмийн модны үр ашгийг өгнө.

Шинэчлэх асуулга

Одоо бид массив дахь тодорхой элементийг өөрчлөхийг хүсэж байна, жишээ нь $a[i] = x$ олголт хийхийг хүсэж байна гэж бодъё. Мөн бид шинэ, өөрчлөгдсөн массивт харгалзахаар Хэрчмийн модыг дахин байгуулах ёстой.

Энэ асуулга нийлбэрийн асуулгаас хялбар. Хэрчмийн модны түвшин бүр массивын хуваалт үүсгэдэг. Тиймээс $a[i]$ элемент нь түвшин бүрээс зөвхөн нэг хэрчимд хувь нэмэр оруулна. Ингэснээр зөвхөн $O(\log n)$ орой шинэчлэгдэх шаардлагатай.

Шинэчлэх хүсэлтийг рекурсив функц ашиглан хэрэгжүүлж болохыг харахад амархан. Функцэд одоогийн модны орой дамжуулагдах ба энэ нь хоёр хүүхэд оройн нэгтэй (өөрийн хэрчимдээ $a[i]$-г агуулж буй нь) өөрийгөө рекурсивээр дуудаж, дараа нь build арга дахьтай адилаар (өөрөөр хэлбэл хоёр хүүхдийнхээ нийлбэр байдлаар) нийлбэрийн утгаа дахин тооцоолно.

Дахин ижил массивыг ашигласан дүрслэл энд байна. Энд бид $a[2] = 3$ шинэчлэлийг гүйцэтгэнэ. Ногоон оройнууд нь бидний зочилж, шинэчилдэг оройнууд юм.

"Нийлбэрийн Хэрчмийн модны шинэчлэл"

Implementation

The main consideration is how to store the Segment Tree. Of course we can define a $\text{Vertex}$ struct and create objects, that store the boundaries of the segment, its sum and additionally also pointers to its child vertices. However, this requires storing a lot of redundant information in the form of pointers. We will use a simple trick to make this a lot more efficient by using an implicit data structure: Only storing the sums in an array. (A similar method is used for binary heaps). The sum of the root vertex at index 1, the sums of its two child vertices at indices 2 and 3, the sums of the children of those two vertices at indices 4 to 7, and so on. With 1-indexing, conveniently the left child of a vertex at index $i$ is stored at index $2i$, and the right one at index $2i + 1$. Equivalently, the parent of a vertex at index $i$ is stored at $i/2$ (integer division).

This simplifies the implementation a lot. We don't need to store the structure of the tree in memory. It is defined implicitly. We only need one array which contains the sums of all segments.

As noted before, we need to store at most $4n$ vertices. It might be less, but for convenience we always allocate an array of size $4n$. There will be some elements in the sum array, that will not correspond to any vertices in the actual tree, but this doesn't complicate the implementation.

So, we store the Segment Tree simply as an array $t[]$ with a size of four times the input size $n$:

int n, t[4*MAXN];

The procedure for constructing the Segment Tree from a given array $a[]$ looks like this: it is a recursive function with the parameters $a[]$ (the input array), $v$ (the index of the current vertex), and the boundaries $tl$ and $tr$ of the current segment. In the main program this function will be called with the parameters of the root vertex: $v = 1$, $tl = 0$, and $tr = n - 1$. 

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

Further the function for answering sum queries is also a recursive function, which receives as parameters information about the current vertex/segment (i.e. the index $v$ and the boundaries $tl$ and $tr$) and also the information about the boundaries of the query, $l$ and $r$. In order to simplify the code, this function always does two recursive calls, even if only one is necessary - in that case the superfluous recursive call will have $l > r$, and this can easily be caught using an additional check at the beginning of the function.

int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
           + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

Finally the update query. The function will also receive information about the current vertex/segment, and additionally also the parameter of the update query (i.e. the position of the element and its new value).

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = t[v*2] + t[v*2+1];
    }
}

Memory efficient implementation

Most people use the implementation from the previous section. If you look at the array t you can see that it follows the numbering of the tree nodes in the order of a BFS traversal (level-order traversal). Using this traversal the children of vertex $v$ are $2v$ and $2v + 1$ respectively. However if $n$ is not a power of two, this method will skip some indices and leave some parts of the array t unused. The memory consumption is limited by $4n$, even though a Segment Tree of an array of $n$ elements requires only $2n - 1$ vertices.

However it can be reduced. We renumber the vertices of the tree in the order of an Euler tour traversal (pre-order traversal), and we write all these vertices next to each other.

Let's look at a vertex at index $v$, and let it be responsible for the segment $[l, r]$, and let $mid = \dfrac{l + r}{2}$. It is obvious that the left child will have the index $v + 1$. The left child is responsible for the segment $[l, mid]$, i.e. in total there will be $2 * (mid - l + 1) - 1$ vertices in the left child's subtree. Thus we can compute the index of the right child of $v$. The index will be $v + 2 * (mid - l + 1)$. By this numbering we achieve a reduction of the necessary memory to $2n$.

Хэрчмийн модны дэвшилтэт хувилбарууд

Хэрчмийн мод бол маш уян хатан өгөгдлийн бүтэц бөгөөд олон өөр чиглэлд хувилбар, өргөтгөл хийх боломж олгодог. Тэдгээрийг доор ангилахыг оролдъё.

Илүү нарийн төвөгтэй асуулга

Хэрчмийн модыг өөр асуулга тооцоолохоор (жишээ нь нийлбэрийн оронд минимум / максимум тооцоолохоор) чиглэлд нь өөрчлөх нь нэлээд амархан байж болох ч мөн маш тривиаль бус байж болно.

Максимум олох

Дээр тайлбарласан бодлогын нөхцөлийг бага зэрэг өөрчилье: нийлбэр асуухын оронд бид одоо максимумын асуулга хийнэ.

Мод нь дээр тайлбарласан модтой яг ижил бүтэцтэй байна. Бид зөвхөн $\text{build}$ ба $\text{update}$ функцүүдэд $t[v]$-г тооцоолох аргыг өөрчлөх хэрэгтэй. $t[v]$ одоо харгалзах хэрчмийн максимумыг хадгална. Мөн бид $\text{sum}$ функцийн буцаах утгын тооцооллыг өөрчлөх хэрэгтэй (нийлбэрлэхийг максимумаар солино).

Мэдээж энэ бодлогыг максимумын оронд минимум тооцоолохоор амархан өөрчилж болно.

Энэ бодлогын хэрэгжүүлэлтийг үзүүлэхийн оронд дараагийн хэсэгт энэ бодлогын илүү нарийн төвөгтэй хувилбарын хэрэгжүүлэлтийг өгнө.

Максимум ба түүний давтагдах тоог олох

Энэ бодлого өмнөхтэй маш төстэй. Максимум олохоос гадна бид максимумын давтагдалтын тоог мөн олох ёстой.

Энэ бодлогыг бодохын тулд бид модны орой бүрд хос тоо хадгална: максимумаас гадна бид харгалзах хэрчим дэх түүний давтагдалтын тоог мөн хадгална. $t[v]$-д хадгалах зөв хосыг тодорхойлохыг хүүхэд оройнуудад хадгалагдсан хосуудын мэдээллийг ашиглан тогтмол хугацаанд хийсээр байж болно. Ийм хоёр хосыг нэгтгэхийг тусдаа функцэд хийх ёстой, учир нь энэ нь мод байгуулах явцад, максимумын асуулгад хариулах явцад, өөрчлөлт хийх явцад бидний хийх үйлдэл байх болно.

pair<int, int> t[4*MAXN];

pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first) 
        return a;
    if (b.first > a.first)
        return b;
    return make_pair(a.first, a.second + b.second);
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = make_pair(a[tl], 1);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

pair<int, int> get_max(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return make_pair(-INF, 0);
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(get_max(v*2, tl, tm, l, min(r, tm)), 
                   get_max(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = make_pair(new_val, 1);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

Хамгийн их ерөнхий хуваагч / хамгийн бага ерөнхий үржвэрийг тооцоолох

Энэ бодлогод бид массивын өгөгдсөн интервал дахь бүх тооны ХИЕХ / ХБЕҮ-г тооцоолохыг хүсэж байна.

Хэрчмийн модны энэ сонирхолтой хувилбарыг нийлбэр / минимум / максимумын асуулгад зориулж гаргасан Хэрчмийн модтой яг ижил аргаар бодож болно: модны орой бүрд харгалзах оройн ХИЕХ / ХБЕҮ-г хадгалахад хангалттай. Хоёр оройг нэгтгэхийг хоёр оройн ХИЕХ / ХБЕҮ-г тооцоолох замаар хийж болно.

Тэгийн тоог тоолох, $k$ дахь тэгийг хайх

Энэ бодлогод бид өгөгдсөн интервал дахь тэгийн тоог олж, түүнчлэн хоёр дахь функц ашиглан $k$ дахь тэгийн индексийг олохыг хүсэж байна.

Дахин бид модны хадгалах утгуудыг бага зэрэг өөрчлөх хэрэгтэй: Энэ удаад бид хэрчим бүр дэх тэгийн тоог $t[]$-д хадгална. $\text{build}$, $\text{update}$ ба $\text{count_zero}$ функцүүдийг хэрхэн хэрэгжүүлэхийг ойлгоход нэлээд ойлгомжтой, бид нийлбэрийн асуулгын бодлогын санааг зүгээр л ашиглаж болно. Ингэснээр бид бодлогын эхний хэсгийг бодлоо.

Одоо бид $a[]$ массив дахь $k$ дахь тэгийг олох бодлогыг хэрхэн бодохыг сурна. Энэ бодлогыг хийхийн тулд бид үндэс оройноос эхлэн Хэрчмийн модоор буун, $k$ дахь тэгийг аль хэрчим агуулж байгаагаас хамааран тухай бүр зүүн эсвэл баруун хүүхэд рүү шилжинэ. Аль хүүхэд рүү явахаа шийдэхийн тулд зүүн оройд харгалзах хэрчимд гарч буй тэгийн тоог харахад хангалттай. Хэрэв энэ урьдчилан тооцоолсон тоо $k$-аас их буюу тэнцүү бол зүүн хүүхэд рүү буух шаардлагатай, эс бөгөөс баруун хүүхэд рүү буух хэрэгтэй. Хэрэв бид баруун хүүхдийг сонговол $k$-аас зүүн хүүхдийн тэгийн тоог хасах ёстойг анзаар.

Хэрэгжүүлэлтэд бид $a[]$ нь $k$-аас цөөн тэг агуулсан тусгай тохиолдлыг -1 буцаах замаар зохицуулж болно.

int find_kth(int v, int tl, int tr, int k) {
    if (k > t[v])
        return -1;
    if (tl == tr)
        return tl;
    int tm = (tl + tr) / 2;
    if (t[v*2] >= k)
        return find_kth(v*2, tl, tm, k);
    else 
        return find_kth(v*2+1, tm+1, tr, k - t[v*2]);
}

Өгөгдсөн хэмжээтэй массивын угтварыг хайх

Бодлого дараах байдалтай: өгөгдсөн $x$ утгын хувьд бид $a[]$ массивын эхний $i$ элементийн нийлбэр нь $x$-ээс их буюу тэнцүү байх хамгийн бага $i$ индексийг хурдан олох ёстой ($a[]$ массив зөвхөн сөрөг биш утга агуулна гэж үзье).

Энэ бодлогыг Хэрчмийн модоор угтваруудын нийлбэрийг тооцоолж, хоёртын хайлт ашиглан бодож болно. Гэвч энэ нь $O(\log^2 n)$ шийдэлд хүргэнэ.

Үүний оронд бид өмнөх хэсэг дэх ижил санааг ашиглан модоор буух замаар байрлалыг олж болно: зүүн хүүхдийн нийлбэрээс хамааран тухай бүр зүүн эсвэл баруун тийш шилжих замаар. Ингэснээр хариуг $O(\log n)$ хугацаанд олно.

Өгөгдсөн хэмжээнээс их эхний элементийг хайх

Бодлого дараах байдалтай: өгөгдсөн $x$ утга ба $a[l \dots r]$ интервалын хувьд $a[i]$ нь $x$-ээс их байх хамгийн бага $i$-г $a[l \dots r]$ интервалаас ол.

Энэ бодлогыг Хэрчмийн модоор максимум угтварын асуулга дээр хоёртын хайлт ашиглан бодож болно. Гэвч энэ нь $O(\log^2 n)$ шийдэлд хүргэнэ.

Үүний оронд бид өмнөх хэсгүүд дэх ижил санааг ашиглан модоор буух замаар байрлалыг олж болно: зүүн хүүхдийн максимум утгаас хамааран тухай бүр зүүн эсвэл баруун тийш шилжих замаар. Ингэснээр хариуг $O(\log n)$ хугацаанд олно.

int get_first(int v, int tl, int tr, int l, int r, int x) {
    if(tl > r || tr < l) return -1;
    if(t[v] <= x) return -1;

    if (tl== tr) return tl;

    int tm = tl + (tr-tl)/2;
    int left = get_first(2*v, tl, tm, l, r, x);
    if(left != -1) return left;
    return get_first(2*v+1, tm+1, tr, l ,r, x);
}

Хамгийн их нийлбэртэй дэд хэрчмийг олох

Энд дахин бид асуулга бүрд $a[l \dots r]$ интервал хүлээн авах ба энэ удаад бид $l \le l^\prime$ ба $r^\prime \le r$ байх бөгөөд энэ хэрчмийн элементүүдийн нийлбэр хамгийн их байх $a[l^\prime \dots r^\prime]$ дэд хэрчмийг олох ёстой. Өмнөхийн адил бид мөн массивын бие даасан элементүүдийг өөрчлөх боломжтой байхыг хүсэж байна. Массивын элементүүд сөрөг байж болох ба оновчтой дэд хэрчим хоосон байж болно (жишээ нь бүх элемент сөрөг бол).

Энэ бодлого бол Хэрчмийн модны тривиаль бус хэрэглээ юм. Энэ удаад бид орой бүрд дөрвөн утга хадгална: хэрчмийн нийлбэр, хамгийн их угтварын нийлбэр, хамгийн их дагаврын нийлбэр, түүн дэх хамгийн их дэд хэрчмийн нийлбэр. Өөрөөр хэлбэл Хэрчмийн модны хэрчим бүрийн хувьд хариу нь урьдчилан тооцоологдсон байхын зэрэгцээ хэрчмийн зүүн ба баруун хязгаарт хүрч буй хэрчмүүдийн хариу ч мөн урьдчилан тооцоологдсон байна.

Ийм өгөгдөлтэй модыг хэрхэн байгуулах вэ? Дахин бид үүнийг рекурсив байдлаар тооцоолно: бид эхлээд зүүн ба баруун хүүхдийн дөрвөн утгыг бүгдийг тооцоолж, дараа нь одоогийн оройн дөрвөн утгыг гаргахын тулд тэдгээрийг нэгтгэнэ. Одоогийн оройн хариу нь дараахын аль нэг болохыг анзаар:

  • зүүн хүүхдийн хариу, энэ нь оновчтой дэд хэрчим зүүн хүүхдийн хэрчимд бүхэлдээ байрлана гэсэн үг
  • баруун хүүхдийн хариу, энэ нь оновчтой дэд хэрчим баруун хүүхдийн хэрчимд бүхэлдээ байрлана гэсэн үг
  • зүүн хүүхдийн хамгийн их дагаврын нийлбэр ба баруун хүүхдийн хамгийн их угтварын нийлбэрийн нийлбэр, энэ нь оновчтой дэд хэрчим хоёр хүүхэдтэй хоёуланд нь огтлолцоно гэсэн үг.

Тиймээс одоогийн оройн хариу нь эдгээр гурван утгын максимум юм. Хамгийн их угтвар / дагаврын нийлбэрийг тооцоолох нь бүр ч хялбар. Зөвхөн зүүн ба баруун хүүхдээс өгөгдөл хүлээн авч, одоогийн оройн өгөгдлийг буцаадаг $\text{combine}$ функцийн хэрэгжүүлэлт энд байна.

struct data {
    int sum, pref, suff, ans;
};

data combine(data l, data r) {
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
    return res;
}

$\text{combine}$ функцийг ашиглан Хэрчмийн модыг байгуулахад амархан. Бид үүнийг өмнөх хэрэгжүүлэлтүүд дэхтэй яг ижил аргаар хэрэгжүүлж болно. Навч оройнуудыг эхлүүлэхийн тулд бид нэмэлтээр $\text{make_data}$ туслах функц үүсгэх ба энэ нь ганц утгын мэдээллийг агуулсан $\text{data}$ обьект буцаана.

data make_data(int val) {
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = max(0, val);
    return res;
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = make_data(a[tl]);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = make_data(new_val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

Асуулгын хариуг хэрхэн тооцоолох нь л үлдлээ. Түүнд хариулахын тулд бид өмнөхийн адил модоор доош явж, асуулгыг Хэрчмийн модны хэрчмүүдтэй давхцах хэд хэдэн дэд хэрчимд хувааж, тэдгээр дэх хариуг асуулгын ганц хариу болгон нэгтгэнэ. Тэгвэл ажил нь энгийн Хэрчмийн мод дахьтай яг ижил боловч утгуудыг нийлбэрлэх / минимумчлах / максимумчлахын оронд бид $\text{combine}$ функц ашиглана гэдэг нь ойлгомжтой болно.

data query(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return make_data(0);
    if (l == tl && r == tr) 
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(query(v*2, tl, tm, l, min(r, tm)), 
                   query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

Орой бүрд бүхэл дэд массивыг хадгалах

Энэ бол бусдаас тусдаа зогсох тусдаа дэд хэсэг юм, учир нь Хэрчмийн модны орой бүрд бид харгалзах хэрчмийн тухай мэдээллийг шахсан хэлбэрээр (нийлбэр, минимум, максимум, ...) хадгалахгүй, харин хэрчмийн бүх элементийг хадгална. Ингэснээр Хэрчмийн модны үндэс массивын бүх элементийг, зүүн хүүхэд орой массивын эхний хагасыг, баруун орой хоёр дахь хагасыг гэх мэтчилэн хадгална.

Энэ аргын хамгийн энгийн хэрэглээнд бид элементүүдийг эрэмбэлэгдсэн дарааллаар хадгална. Илүү нарийн төвөгтэй хувилбаруудад элементүүдийг жагсаалтад биш, илүү дэвшилтэт өгөгдлийн бүтцэд (set, map, ...) хадгална. Гэвч эдгээр бүх арга нь орой бүр шугаман санах ой (өөрөөр хэлбэл харгалзах хэрчмийн урттай пропорциональ) шаарддаг гэсэн нийтлэг хүчин зүйлтэй.

Эдгээр Хэрчмийн модыг авч үзэхэд гарах эхний байгалийн асуулт бол санах ойн хэрэглээ юм. Зөнгөөрөө бол энэ нь $O(n^2)$ санах ой мэт харагдаж болох ч бүрэн мод ердөө $O(n \log n)$ санах ой шаардах нь тогтоогддог. Яагаад ийм байна вэ? Маш энгийн, учир нь массивын элемент бүр $O(\log n)$ хэрчимд ордог (модны өндөр $O(\log n)$ болохыг сана).

Тиймээс ийм Хэрчмийн мод илт үрэлгэн мэт харагдавч ердийн Хэрчмийн модноос ердөө бага зэрэг илүү санах ой зарцуулна.

Энэ өгөгдлийн бүтцийн хэд хэдэн ердийн хэрэглээг доор тайлбарлав. Эдгээр Хэрчмийн мод нь 2 хэмжээст өгөгдлийн бүтэцтэй төстэй болохыг тэмдэглэх нь зүйтэй (үнэндээ энэ бол 2 хэмжээст өгөгдлийн бүтэц боловч нэлээд хязгаарлагдмал боломжтой).

Заасан тооноос их буюу тэнцүү хамгийн бага тоог олох. Өөрчлөх асуулгагүй.

Бид дараах хэлбэрийн асуулгад хариулахыг хүсэж байна: өгөгдсөн гурван тоо $(l, r, x)$-ийн хувьд бид $a[l \dots r]$ хэрчим дэх $x$-ээс их буюу тэнцүү хамгийн бага тоог олох ёстой.

Бид Хэрчмийн мод байгуулна. Дээр тайлбарласны адил бид орой бүрд харгалзах хэрчимд гарч буй бүх тооны эрэмбэлэгдсэн жагсаалтыг хадгална. Ийм Хэрчмийн модыг хэрхэн аль болох үр дүнтэй байгуулах вэ? Үргэлжийнх шиг бид энэ бодлогод рекурсивээр хандана: зүүн ба баруун хүүхдийн жагсаалтууд аль хэдийн байгуулагдсан байг, бид одоогийн оройн жагсаалтыг байгуулахыг хүсэж байна. Энэ өнцгөөс харахад үйлдэл одоо тривиаль бөгөөд шугаман хугацаанд гүйцэтгэгдэнэ: Бид зөвхөн хоёр эрэмбэлэгдсэн жагсаалтыг нэг болгон нэгтгэх хэрэгтэй бөгөөд үүнийг хоёр заагч ашиглан тэдгээрийг гүйх замаар хийж болно. C++ STL-д энэ алгоритмын хэрэгжүүлэлт аль хэдийн бий.

Хэрчмийн модны энэ бүтэц ба нэгтгэх эрэмбэлэлтийн алгоритмтай төстэй байдлаас болж энэ өгөгдлийн бүтцийг мөн "Merge Sort Tree" гэж олонтаа нэрлэдэг.

vector<int> t[4*MAXN];

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = vector<int>(1, a[tl]);
    } else { 
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
              back_inserter(t[v]));
    }
}

Ийм байдлаар байгуулагдсан Хэрчмийн мод $O(n \log n)$ санах ой шаардана гэдгийг бид аль хэдийн мэднэ. Энэ хэрэгжүүлэлтийн ачаар түүний байгуулалт мөн $O(n \log n)$ хугацаа авна, эцсийн эцэст жагсаалт бүр өөрийн хэмжээний хувьд шугаман хугацаанд байгуулагдана.

Одоо асуулгын хариуг авч үзье. Бид ердийн Хэрчмийн мод дахьтай адил модоор доош явж, $a[l \dots r]$ хэрчмээ хэд хэдэн дэд хэрчимд (хамгийн ихдээ $O(\log n)$ хэсэгт) хуваана. Бүхэл хариу нь дэд асуулга тус бүрийн минимум болох нь ойлгомжтой. Тиймээс одоо бид модны ямар нэг оройд харгалзах ийм нэг дэд хэрчим дээрх асуулгад хэрхэн хариулахыг ойлгох хэрэгтэй.

Бид Хэрчмийн модны ямар нэг оройд байгаа ба асуулгын хариуг тооцоолохыг буюу өгөгдсөн $x$ тооноос их буюу тэнцүү хамгийн бага тоог олохыг хүсэж байна. Орой нь элементүүдийн жагсаалтыг эрэмбэлэгдсэн дарааллаар агуулдаг тул бид энэ жагсаалт дээр зүгээр л хоёртын хайлт гүйцэтгээд $x$-ээс их буюу тэнцүү эхний тоог буцааж болно.

Ингэснээр модны нэг хэрчим дэх асуулгын хариу $O(\log n)$ хугацаа авах ба бүхэл асуулга $O(\log^2 n)$-д боловсруулагдана.

int query(int v, int tl, int tr, int l, int r, int x) {
    if (l > r)
        return INF;
    if (l == tl && r == tr) {
        vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
        if (pos != t[v].end())
            return *pos;
        return INF;
    }
    int tm = (tl + tr) / 2;
    return min(query(v*2, tl, tm, l, min(r, tm), x), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r, x));
}

$\text{INF}$ тогтмол нь массив дахь бүх тооноос их ямар нэг том тоотой тэнцүү. Түүнийг ашиглах нь хэрчимд $x$-ээс их буюу тэнцүү тоо байхгүй гэсэн үг юм. Энэ нь "өгөгдсөн интервалд хариу байхгүй" гэсэн утгатай.

Заасан тооноос их буюу тэнцүү хамгийн бага тоог олох. Өөрчлөх асуулгатай.

Энэ бодлого өмнөхтэй төстэй. Сүүлийн арга нэг сул талтай, асуулгад хариулах хооронд массивыг өөрчлөх боломжгүй байсан. Одоо бид яг үүнийг хийхийг хүсэж байна: өөрчлөх асуулга нь $a[i] = y$ олголт хийнэ.

Шийдэл нь өмнөх бодлогын шийдэлтэй төстэй, гэхдээ Хэрчмийн модны орой бүрд жагсаалтын оронд бид тоо хурдан хайх, тоо устгах, шинэ тоо оруулах боломж олгодог тэнцвэржүүлсэн жагсаалт хадгална. Массив давтагдсан тоо агуулж болох тул оновчтой сонголт нь $\text{multiset}$ өгөгдлийн бүтэц юм.

Ийм Хэрчмийн модны байгуулалтыг өмнөх бодлого дахьтай бараг ижил аргаар хийнэ, зөвхөн одоо бид эрэмбэлэгдсэн жагсаалт биш $\text{multiset}$-үүдийг нэгтгэх хэрэгтэй. Энэ нь $O(n \log^2 n)$ байгуулалтын хугацаанд хүргэнэ (ерөнхийдөө хоёр улаан-хар модыг шугаман хугацаанд нэгтгэж болох ч C++ STL энэ time complexity-г баталгаажуулдаггүй).

$\text{query}$ функц мөн бараг эквивалент, зөвхөн одоо $\text{multiset}$-ийн $\text{lower_bound}$ функцийг оронд нь дуудах ёстой ($\text{std::lower_bound}$ нь random-access iterator-тай ашиглагдсан үед л $O(\log n)$ хугацаанд ажиллана).

Эцэст нь өөрчлөх хүсэлт. Түүнийг боловсруулахын тулд бид модоор доош явж, нөлөөлсөн элементийг агуулсан харгалзах хэрчмүүдийн бүх $\text{multiset}$-г өөрчлөх ёстой. Бид энэ элементийн хуучин утгыг зүгээр л устгаж (гэхдээ зөвхөн нэг давтагдалтыг), шинэ утгыг оруулна.

void update(int v, int tl, int tr, int pos, int new_val) {
    t[v].erase(t[v].find(a[pos]));
    t[v].insert(new_val);
    if (tl != tr) {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
    } else {
        a[pos] = new_val;
    }
}

Энэ өөрчлөх асуулгыг боловсруулах нь мөн $O(\log^2 n)$ хугацаа авна.

Заасан тооноос их буюу тэнцүү хамгийн бага тоог олох. "Fractional cascading"-аар хурдасгах.

Бидэнд ижил бодлогын постановк байна, бид хэрчим дэх $x$-ээс их буюу тэнцүү хамгийн бага тоог олохыг хүсэж байна, гэхдээ энэ удаад $O(\log n)$ хугацаанд. Бид "fractional cascading" арга ашиглан time complexity-г сайжруулна.

Fractional cascading гэдэг нь нэгэн зэрэг явагдаж буй олон хоёртын хайлтын ажиллах хугацааг сайжруулах боломж олгодог энгийн арга юм. Хайлтын асуулгад хандах бидний өмнөх арга нь бодлогыг хэд хэдэн дэд бодлогод хуваах бөгөөд тус бүр нь хоёртын хайлтаар бодогдоно. Fractional cascading нь эдгээр бүх хоёртын хайлтыг ганцаар солих боломж олгоно.

Fractional cascading-ийн хамгийн энгийн бөгөөд илэрхий жишээ бол дараах бодлого юм: $k$ ширхэг эрэмбэлэгдсэн тоонуудын жагсаалт байгаа ба бид жагсаалт бүрээс өгөгдсөн тооноос их буюу тэнцүү эхний тоог олох ёстой.

Жагсаалт бүрд хоёртын хайлт гүйцэтгэхийн оронд бид бүх жагсаалтыг нэг том эрэмбэлэгдсэн жагсаалт болгон нэгтгэж болно. Түүнчлэн элемент $y$ бүрийн хувьд бид $k$ жагсаалт тус бүрээс $y$-г хайсан үр дүнгийн жагсаалтыг хадгална. Тиймээс хэрэв бид $x$-ээс их буюу тэнцүү хамгийн бага тоог олохыг хүсвэл бид ердөө нэг хоёртын хайлт гүйцэтгэх хэрэгтэй бөгөөд индексүүдийн жагсаалтаас бид жагсаалт бүрийн хамгийн бага тоог тодорхойлж чадна. Гэвч энэ арга $O(n \cdot k)$ шаардана ($n$ нь нэгтгэсэн жагсаалтуудын урт) бөгөөд энэ нь нэлээд үр ашиггүй байж болно.

Fractional cascading нь $k$ оролтын жагсаалтаас $k$ шинэ жагсаалт үүсгэх замаар энэ санах ойн complexity-г $O(n)$ санах ой болгон бууруулна, шинэ жагсаалт бүр нь харгалзах жагсаалтыг, түүнчлэн дараагийн шинэ жагсаалтын хоёр дахь элемент бүрийг агуулна. Энэ бүтцийг ашиглавал зөвхөн хоёр индекс хадгалахад хангалттай: анхны жагсаалт дахь элементийн индекс ба дараагийн шинэ жагсаалт дахь элементийн индекс. Тиймээс энэ арга ердөө $O(n)$ санах ой ашиглах ба ганц хоёртын хайлт ашиглан асуулгад хариулж чадсаар байна.

Гэвч бидний хэрэглээнд fractional cascading-ийн бүрэн хүчийг ашиглах шаардлагагүй. Бидний Хэрчмийн модонд орой нь зүүн эсвэл баруун дэд модонд гарч буй бүх элементийн эрэмбэлэгдсэн жагсаалтыг агуулна (Merge Sort Tree дэхтэй адил). Энэ эрэмбэлэгдсэн жагсаалтаас гадна бид элемент бүрд хоёр байрлал хадгална. Элемент $y$-ийн хувьд бид зүүн хүүхдийн эрэмбэлэгдсэн жагсаалтын $i$ дахь элемент нь $y$-ээс их буюу тэнцүү байх хамгийн бага $i$ индексийг хадгална. Мөн бид баруун хүүхдийн эрэмбэлэгдсэн жагсаалтын $j$ дахь элемент нь $y$-ээс их буюу тэнцүү байх хамгийн бага $j$ индексийг хадгална. Эдгээр утгыг мод байгуулах үед нэгтгэх алхамтай зэрэгцүүлэн тооцоолж болно.

Энэ нь асуулгуудыг хэрхэн хурдасгах вэ?

Ердийн шийдэлд бид зангилаа бүрд хоёртын хайлт хийж байсныг сана. Гэвч энэ өөрчлөлтөөр бид нэгээс бусад бүгдээс зайлсхийж чадна.

Асуулгад хариулахын тулд бид ердөө үндэс зангилаанд хоёртын хайлт хийнэ. Энэ нь бидэнд бүхэл массив дахь хамгийн бага элемент $y \ge x$-г өгөх ба мөн хоёр байрлал өгнө. Зүүн дэд мод дахь $x$-ээс их буюу тэнцүү хамгийн бага элементийн индекс ба баруун дэд мод дахь хамгийн бага элемент $y$-ийн индекс. Бидний массив $x$ ба $y$-ийн хооронд ямар ч элемент агуулаагүй тул $\ge y$ нь $\ge x$-тэй ижил болохыг анзаар. Ердийн Merge Sort Tree-ийн шийдэлд бид эдгээр индексийг хоёртын хайлтаар тооцоолох байсан ч урьдчилан тооцоолсон утгуудын тусламжтайгаар бид тэдгээрийг $O(1)$-д зүгээр л хайж олж болно. Мөн бид асуулгын интервалыг бүрхэх бүх зангилаанд зочилтол үүнийг давтаж болно.

Дүгнэвэл бид үргэлжийнх шиг асуулгын явцад $O(\log n)$ зангилаанд хүрнэ. Үндэс зангилаанд бид хоёртын хайлт хийх ба бусад бүх зангилаанд бид зөвхөн тогтмол ажил хийнэ. Энэ нь асуулгад хариулах complexity нь $O(\log n)$ гэсэн үг юм.

Гэвч энэ нь аль хэдийн их санах ой ($O(n \log n)$) ашигладаг ердийн Merge Sort Tree-ээс гурав дахин их санах ой ашигладгийг анзаар.

Ямар ч өөрчлөх асуулга шаарддаггүй бодлогод энэ аргыг хэрэглэхэд шууд ойлгомжтой. Хоёр байрлал нь зүгээр л бүхэл тоо бөгөөд хоёр эрэмбэлэгдсэн дарааллыг нэгтгэх үед тоолох замаар амархан тооцоолж болно.

Өөрчлөх асуулгыг мөн зөвшөөрөх боломжтой хэвээр байгаа ч энэ нь бүхэл кодыг төвөгтэй болгоно. Бүхэл тооны оронд та эрэмбэлэгдсэн массивыг multiset болгон хадгалах хэрэгтэй бөгөөд индексийн оронд iterator хадгалах хэрэгтэй. Мөн та өөрчлөх асуулгын явцад зөв iterator-уудыг нэмэгдүүлэх буюу багасгахын тулд маш болгоомжтой ажиллах хэрэгтэй.

Бусад боломжит хувилбарууд

Энэ арга нь боломжит хэрэглээний цоо шинэ ангиллыг үүсгэнэ. Орой бүрд $\text{vector}$ буюу $\text{multiset}$ хадгалахын оронд өөр өгөгдлийн бүтэц ашиглаж болно: өөр Хэрчмийн мод (Илүү өндөр хэмжээст рүү ерөнхийлөх-д зарим талаар авч үзсэн), Фенвикийн мод, Декартын мод гэх мэт.

Интервалын шинэчлэл (Залхуу тархалт)

Дээрх хэсгүүд дэх бүх бодлого нь массивын ердөө нэг элементэд нөлөөлдөг өөрчлөх асуулгыг авч үзсэн. Гэвч Хэрчмийн мод нь дараалсан элементүүдийн бүхэл хэрчимд өөрчлөх асуулга хэрэглэж, асуулгыг мөн ижил $O(\log n)$ хугацаанд гүйцэтгэх боломж олгоно.

Хэрчим дээр нэмэх

Бид хамгийн энгийн хэлбэрийн бодлогыг авч үзэхээс эхэлье: өөрчлөх асуулга нь $a[l \dots r]$ хэрчим дэх бүх тоон дээр $x$ тоо нэмэх ёстой. Бидний хариулах ёстой хоёр дахь асуулга нь зүгээр л $a[i]$-ийн утгыг асууна.

Нэмэх асуулгыг үр ашигтай болгохын тулд бид Хэрчмийн модны орой бүрд харгалзах хэрчим дэх бүх тоон дээр хэдийг нэмэх ёстойгоо хадгална. Жишээ нь "бүхэл массив $a[0 \dots n-1]$ дээр 3 нэм" гэсэн асуулга ирвэл бид модны үндэст 3 тоог байрлуулна. Ерөнхийдөө бид энэ тоог асуулгын хэрчмийн хуваалт үүсгэдэг олон хэрчимд байрлуулах ёстой. Ингэснээр бид бүх $O(n)$ утгыг өөрчлөх шаардлагагүй, зөвхөн $O(\log n)$ ширхэгийг өөрчилнө.

Хэрэв одоо массивын тодорхой нэг гишүүний одоогийн утгыг асуух асуулга ирвэл модоор доош явж, замд олдсон бүх утгыг нэмэхэд хангалттай.

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

Хэрчим дээр олгох

Одоо өөрчлөх асуулга нь тодорхой $a[l \dots r]$ хэрчмийн элемент бүрд ямар нэг $p$ утга олгохыг хүсэж байна гэж бодъё. Хоёр дахь асуулга болгон бид дахин $a[i]$ массивын утгыг унших явдлыг авч үзнэ.

Энэ өөрчлөх асуулгыг бүхэл хэрчим дээр гүйцэтгэхийн тулд та Хэрчмийн модны орой бүрд харгалзах хэрчим бүхэлдээ ижил утгаар бүрхэгдсэн эсэхийг хадгалах ёстой. Энэ нь бидэнд "залхуу" шинэчлэл хийх боломж олгоно: асуулгын хэрчмийг бүрхэх модны бүх хэрчмийг өөрчлөхийн оронд бид зөвхөн заримыг нь өөрчилж, бусдыг өөрчлөхгүй үлдээнэ. Тэмдэглэгдсэн орой нь харгалзах хэрчмийн элемент бүрд тэр утга олгогдсон бөгөөд үнэндээ бүрэн дэд мод мөн зөвхөн энэ утгыг агуулах ёстой гэсэн үг юм. Тодорхой утгаараа бид залхуу байж, шинэ утгыг тэдгээр бүх оройд бичихийг хойшлуулж байна. Хэрэв шаардлагатай бол бид энэ уйтгартай ажлыг дараа хийж болно.

Тиймээс өөрчлөх асуулга гүйцэтгэгдсэний дараа модны зарим хэсэг хамааралгүй болно — зарим өөрчлөлт түүнд биелэгдээгүй үлдэнэ.

Жишээ нь "бүхэл массив $a[0 \dots n-1]$-д тоо олго" гэсэн өөрчлөх асуулга гүйцэтгэгдвэл Хэрчмийн модонд ердөө нэг өөрчлөлт хийгдэнэ — тоо нь модны үндэст байрлаж, энэ орой тэмдэглэгдэнэ. Үлдсэн хэрчмүүд өөрчлөгдөөгүй хэвээр үлдэнэ, хэдийгээр үнэндээ тоо нь бүхэл модонд байрлах ёстой ч.

Одоо хоёр дахь өөрчлөх асуулга нь массивын эхний хагас $a[0 \dots n/2]$-д өөр ямар нэг тоо олгох ёстой гэж хэлж байна гэж бодъё. Энэ асуулгыг боловсруулахын тулд бид үндэс оройн бүхэл зүүн хүүхэд доторх элемент бүрд тэр тоог олгох ёстой. Гэвч бид үүнийг хийхээсээ өмнө эхлээд үндэс оройг эмхлэх ёстой. Эндэх нарийн зүйл нь массивын баруун хагас эхний асуулгын утгаар олгогдсон хэвээр байх ёстой бөгөөд одоогоор баруун хагасын хувьд ямар ч мэдээлэл хадгалагдаагүй байгаа явдал юм.

Үүнийг шийдэх арга бол үндсийн мэдээллийг хүүхдүүд рүү нь түлхэх явдал юм, өөрөөр хэлбэл хэрэв модны үндэст ямар нэг тоо олгогдсон байсан бол бид зүүн ба баруун хүүхэд оройнуудад энэ тоог олгож, үндсийн тэмдэглэгээг арилгана. Үүний дараа бид ямар ч шаардлагатай мэдээлэл алдалгүйгээр зүүн хүүхдэд шинэ утга олгож болно.

Дүгнэвэл бид дараахыг авна: ямар ч асуулгын хувьд (өөрчлөх эсвэл унших асуулга) модоор буух явцад бид одоогийн оройноос мэдээллийг түүний хоёр хүүхэд рүү үргэлж түлхэх ёстой. Үүнийг бид модоор буух үедээ хойшлуулсан өөрчлөлтүүдийг хэрэглэдэг, гэхдээ яг шаардлагатай хэмжээгээр нь (ингэснээр $O(\log n)$ complexity-г мууруулахгүй) гэж ойлгож болно.

Хэрэгжүүлэлтийн хувьд бид одоогийн оройг хүлээн авч, түүний оройн мэдээллийг хоёр хүүхэд рүү нь түлхэх $\text{push}$ функц хийх хэрэгтэй. Бид энэ функцийг асуулгын функцүүдийн эхэнд дуудна (гэхдээ навчнуудаас дуудахгүй, учир нь тэднээс мэдээллийг цааш түлхэх шаардлагагүй).

void push(int v) {
    if (marked[v]) {
        t[v*2] = t[v*2+1] = t[v];
        marked[v*2] = marked[v*2+1] = true;
        marked[v] = false;
    }
}

void update(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] = new_val;
        marked[v] = true;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), new_val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return t[v];
    }
    push(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) 
        return get(v*2, tl, tm, pos);
    else
        return get(v*2+1, tm+1, tr, pos);
}

Анзаар: $\text{get}$ функцийг өөр аргаар ч хэрэгжүүлж болно: хойшлуулсан шинэчлэл хийхгүй, харин $marked[v]$ үнэн бол $t[v]$ утгыг шууд буцаана.

Хэрчим дээр нэмэх, максимум асуух

Одоо өөрчлөх асуулга нь интервал дахь бүх элемент дээр тоо нэмэх бөгөөд унших асуулга нь интервал дахь максимумыг олох явдал юм.

Тиймээс Хэрчмийн модны орой бүрд бид харгалзах дэд хэрчмийн максимумыг хадгалах ёстой. Сонирхолтой хэсэг нь өөрчлөх хүсэлтийн явцад эдгээр утгыг хэрхэн дахин тооцоолох явдал юм.

Энэ зорилгоор бид орой бүрд нэмэлт утга хадгална. Энэ утгад бид хүүхэд оройнууд руу тараагаагүй нэмэгдүүлэгчүүдээ хадгална. Хүүхэд орой руу тойрч очихоосоо өмнө бид $\text{push}$ дуудаж, утгыг хоёр хүүхэд рүү тараана. Бид үүнийг $\text{update}$ функц ба $\text{query}$ функц хоёуланд нь хийх ёстой.

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2 + 1]);
    }
}

void push(int v) {
    t[v*2] += lazy[v];
    lazy[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -INF;
    if (l == tl && tr == r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

Илүү өндөр хэмжээст рүү ерөнхийлөх

Хэрчмийн модыг илүү өндөр хэмжээст рүү нэлээд байгалийн замаар ерөнхийлж болно. Хэрэв нэг хэмжээст тохиолдолд бид массивын индексүүдийг хэрчимд хуваадаг байсан бол хоёр хэмжээстэд бид эхний индексийн хувьд ердийн Хэрчмийн мод хийж, хэрчим бүрийн хувьд хоёр дахь индексийн хувьд ердийн Хэрчмийн мод байгуулна.

Энгийн 2 хэмжээст Хэрчмийн мод

$a[0 \dots n-1, 0 \dots m-1]$ матриц өгөгдсөн ба бид ямар нэг дэд матриц $a[x_1 \dots x_2, y_1 \dots y_2]$ дээрх нийлбэрийг (эсвэл минимум/максимумыг) олох, түүнчлэн матрицын бие даасан элементүүдийг өөрчлөх (өөрөөр хэлбэл $a[x][y] = p$ хэлбэрийн асуулга) ёстой.

Тиймээс бид 2 хэмжээст Хэрчмийн мод байгуулна: эхлээд эхний координат ($x$)-ыг ашиглан Хэрчмийн мод, дараа нь хоёр дахь ($y$)-г.

Байгуулах үйл явцыг илүү ойлгомжтой болгохын тулд та матриц хоёр хэмжээст болохыг хэсэг зуур мартаж, зөвхөн эхний координатыг үлдээж болно. Бид зөвхөн эхний координатыг ашиглан ердийн нэг хэмжээст Хэрчмийн мод байгуулна. Гэвч хэрчимд тоо хадгалахын оронд бид бүхэл Хэрчмийн мод хадгална: өөрөөр хэлбэл яг энэ мөчид бид хоёр дахь координаттай гэдгээ санаж байна; гэхдээ энэ мөчид эхний координат ямар нэг $[l \dots r]$ интервалд аль хэдийн тогтоогдсон тул бид үнэндээ ийм $a[l \dots r, 0 \dots m-1]$ зурвастай ажиллаж байгаа ба түүний хувьд бид Хэрчмийн мод байгуулна.

2 хэмжээст Хэрчмийн модыг байгуулах хэрэгжүүлэлт энд байна. Энэ нь үнэндээ хоёр тусдаа блокийг илэрхийлнэ: $x$ координатын дагуух Хэрчмийн модны байгуулалт ($\text{build}_x$) ба $y$ координатынх ($\text{build}_y$). $\text{build}_y$ дэх навч зангилаануудын хувьд бид хоёр тохиолдлыг салгах ёстой: эхний координатын одоогийн хэрчим $[tlx \dots trx]$ нь 1 урттай үе, мөн нэгээс их урттай үе. Эхний тохиолдолд бид матрицаас харгалзах утгыг зүгээр л авах ба хоёр дахь тохиолдолд бид $x$ координат дахь зүүн ба баруун хүүхдийн хоёр Хэрчмийн модны утгыг нэгтгэж болно.

void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = a[lx][ly];
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
    } else {
        int my = (ly + ry) / 2;
        build_y(vx, lx, rx, vy*2, ly, my);
        build_y(vx, lx, rx, vy*2+1, my+1, ry);
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
    }
}

void build_x(int vx, int lx, int rx) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        build_x(vx*2, lx, mx);
        build_x(vx*2+1, mx+1, rx);
    }
    build_y(vx, lx, rx, 1, 0, m-1);
}

Ийм Хэрчмийн мод шугаман хэмжээний санах ой ашигласаар байх ч илүү том тогтмолтой: $16 n m$. Тайлбарласан $\text{build}_x$ процедур мөн шугаман хугацаанд ажилладаг нь ойлгомжтой.

Одоо бид асуулга боловсруулах руу шилжье. Бид хоёр хэмжээст асуулгад ижил зарчмаар хариулна: эхлээд асуулгыг эхний координат дээр задалж, дараа нь хүрсэн орой бүрийн хувьд хоёр дахь координатын харгалзах Хэрчмийн модыг дуудна.

int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry) 
        return 0;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         + sum_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry);
}

int sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return sum_y(vx, 1, 0, m-1, ly, ry);
    int tmx = (tlx + trx) / 2;
    return sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         + sum_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry);
}

Энэ функц $O(\log n \log m)$ хугацаанд ажиллана, учир нь энэ нь эхлээд эхний координат дээр модоор буух ба модонд тойрсон орой бүрийн хувьд хоёр дахь координатын дагуух харгалзах Хэрчмийн модонд асуулга хийнэ.

Эцэст нь бид өөрчлөх асуулгыг авч үзье. Бид ямар нэг элемент $a[x][y] = p$-ийн утгын өөрчлөлтөд нийцүүлэн Хэрчмийн модыг хэрхэн өөрчлөхийг сурахыг хүсэж байна. Өөрчлөлт нь эхний Хэрчмийн модны $x$ координатыг бүрхэх оройнуудад л гарах нь (ийм нь $O(\log n)$ байх болно), мөн тэдгээрт харгалзах Хэрчмийн модуудын хувьд өөрчлөлт нь зөвхөн $y$ координатыг бүрхэх оройнуудад гарах нь (ийм нь $O(\log m)$ байх болно) ойлгомжтой. Тиймээс хэрэгжүүлэлт нэг хэмжээст тохиолдлоос тийм ч их ялгаатай биш байх ба зөвхөн одоо бид эхлээд эхний координатаар, дараа нь хоёр дахиар нь буух болно.

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
    }
}

void update_x(int vx, int lx, int rx, int x, int y, int new_val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx+1, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
}

2 хэмжээст Хэрчмийн модыг шахах

Бодлого дараах байдалтай байг: хавтгайд $(x_i, y_i)$ координатаараа өгөгдсөн $n$ цэг байгаа ба "$((x_1, y_1), (x_2, y_2))$ тэгш өнцөгтөд орших цэгийн тоог тоол" гэсэн хэлбэрийн асуулгууд байна. Ийм бодлогын хувьд $O(n^2)$ элементтэй хоёр хэмжээст Хэрчмийн мод байгуулах нь зохисгүй үрэлгэн болох нь ойлгомжтой. Энэ санах ойн ихэнх нь дэмий үрэгдэнэ, учир нь ганц цэг бүр эхний координатын дагуух модны зөвхөн $O(\log n)$ хэрчимд орж чадах бөгөөд тиймээс хоёр дахь координат дээрх бүх модны хэрчмүүдийн нийт "ашигтай" хэмжээ нь $O(n \log n)$ юм.

Тиймээс бид дараах байдлаар үргэлжлүүлнэ: эхний координатын хувьд Хэрчмийн модны орой бүрд бид эхний координатуудын одоогийн хэрчимд гарч буй хоёр дахь координатуудаар л байгуулагдсан Хэрчмийн мод хадгална. Өөрөөр хэлбэл $vx$ индекстэй, $tlx$ ба $trx$ хязгаартай ямар нэг оройн дотор Хэрчмийн мод байгуулахдаа бид зөвхөн энэ $x \in [tlx, trx]$ интервалд багтах цэгүүдийг авч үзэж, зөвхөн тэдгээрийг ашиглан Хэрчмийн мод байгуулна.

Ингэснээр бид хоёр дахь координат дээрх Хэрчмийн мод бүр яг байх ёстой хэмжээний санах ой эзлэхэд хүрнэ. Үр дүнд нь нийт санах ойн хэмжээ $O(n \log n)$ хүртэл буурна. Бид асуулгад $O(\log^2 n)$ хугацаанд хариулж чадсаар байх ба зөвхөн хоёр дахь координат дээр хоёртын хайлт хийх хэрэгтэй болох ч энэ нь complexity-г мууруулахгүй.

Гэвч энэ бүтэцтэй бол өөрчлөх асуулга боломжгүй болно: үнэндээ шинэ цэг гарч ирвэл бид хоёр дахь координатын дагуух ямар нэг Хэрчмийн модны дунд шинэ элемент нэмэх ёстой бөгөөд үүнийг үр дүнтэй хийж чадахгүй.

Дүгнэж хэлэхэд тайлбарласан аргаар агшаасан хоёр хэмжээст Хэрчмийн мод нь нэг хэмжээст Хэрчмийн модны өөрчлөлттэй практикт эквивалент болохыг бид тэмдэглэе (Орой бүрд бүхэл дэд массивыг хадгалах-г үз). Ялангуяа хоёр хэмжээст Хэрчмийн мод бол модны орой бүрд дэд массив хадгалах явдлын тусгай тохиолдол юм. Эндээс үзвэл хэрэв та асуулга гүйцэтгэх боломжгүйгээс болж хоёр хэмжээст Хэрчмийн модноос татгалзах шаардлагатай болбол үүрлэсэн Хэрчмийн модыг илүү хүчирхэг ямар нэг өгөгдлийн бүтцээр, жишээ нь Декартын модоор солихыг оролдох нь утга учиртай.

Утгуудынх нь түүхийг хадгалах (Persistent Хэрчмийн мод)

Persistent өгөгдлийн бүтэц гэдэг нь өөрчлөлт бүрийн хувьд өмнөх төлөвөө санадаг өгөгдлийн бүтэц юм. Энэ нь бидний сонирхож буй энэ өгөгдлийн бүтцийн ямар ч хувилбарт хандаж, түүн дээр асуулга гүйцэтгэх боломж олгоно.

Хэрчмийн мод бол (хугацаа ба санах ойн хэрэглээ хоёуланд нь) үр дүнтэйгээр persistent өгөгдлийн бүтэц болгон хувиргаж болох өгөгдлийн бүтэц юм. Бид өөрчлөлт бүрийн өмнө бүхэл модыг хуулахаас зайлсхийхийг хүсэж байгаа бөгөөд интервалын асуулгад хариулах $O(\log n)$ хугацааны зан төлөвөө алдахыг хүсэхгүй байна.

Үнэндээ Хэрчмийн мод дахь ямар ч өөрчлөх хүсэлт нь үндэснээс эхлэх зам дагуух зөвхөн $O(\log n)$ оройн өгөгдөлд өөрчлөлт оруулахад хүргэнэ. Тиймээс хэрэв бид Хэрчмийн модыг заагч ашиглан хадгалбал (өөрөөр хэлбэл орой нь зүүн ба баруун хүүхэд оройнууд руу заасан заагч хадгална) өөрчлөх асуулга гүйцэтгэхдээ бид байгаа оройнуудыг өөрчлөхийн оронд шинэ орой үүсгэх л хэрэгтэй. Өөрчлөх асуулгад нөлөөлөөгүй оройнуудыг заагчуудыг хуучин оройнууд руу заалгах замаар ашигласаар байж болно. Ингэснээр өөрчлөх асуулгын хувьд Хэрчмийн модны шинэ үндэс оройг оруулаад $O(\log n)$ шинэ орой үүсэх ба хуучин үндэс оройд үндэслэсэн модны бүхэл өмнөх хувилбар өөрчлөгдөөгүй хэвээр үлдэнэ.

Хамгийн энгийн Хэрчмийн модны жишээ хэрэгжүүлэлтийг өгье: зөвхөн нийлбэр асуух асуулга, ганц элементийн өөрчлөх асуулга байх үед.

struct Vertex {
    Vertex *l, *r;
    int sum;

    Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }
};

Vertex* build(int a[], int tl, int tr) {
    if (tl == tr)
        return new Vertex(a[tl]);
    int tm = (tl + tr) / 2;
    return new Vertex(build(a, tl, tm), build(a, tm+1, tr));
}

int get_sum(Vertex* v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && tr == r)
        return v->sum;
    int tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, min(r, tm))
         + get_sum(v->r, tm+1, tr, max(l, tm+1), r);
}

Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        return new Vertex(new_val);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos, new_val), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos, new_val));
}

Хэрчмийн модны өөрчлөлт бүрийн хувьд бид шинэ үндэс орой хүлээн авна. Хэрчмийн модны хоёр өөр хувилбарын хооронд хурдан үсрэхийн тулд бид эдгээр үндсийг массивд хадгалах хэрэгтэй. Хэрчмийн модны тодорхой хувилбарыг ашиглахын тулд бид зохих үндэс оройг ашиглан асуулгыг зүгээр л дуудна.

Дээр тайлбарласан аргаар бараг ямар ч Хэрчмийн модыг persistent өгөгдлийн бүтэц болгон хувиргаж болно.

Интервал дахь $k$ дахь хамгийн бага тоог олох

Энэ удаад бид "$a[l \dots r]$ интервал дахь $k$ дахь хамгийн бага элемент юу вэ" гэсэн хэлбэрийн асуулгад хариулах ёстой. Энэ асуулгад хоёртын хайлт ба Merge Sort Tree ашиглан хариулж болох ч ганц асуулгын time complexity нь $O(\log^3 n)$ байх болно. Бид ижил бодлогыг persistent Хэрчмийн мод ашиглан $O(\log n)$-д гүйцэтгэнэ.

Эхлээд бид илүү энгийн бодлогын шийдлийг хэлэлцэнэ: Бид зөвхөн элементүүд нь $0 \le a[i] \lt n$-ээр хязгаарлагдсан массивуудыг авч үзнэ. Мөн бид зөвхөн $a$ массивын ямар нэг угтвар дахь $k$ дахь хамгийн бага элементийг олохыг хүсэж байна. Боловсруулсан санаагаа хожим хязгаарлагдаагүй массив ба хязгаарлагдаагүй интервалын асуулгад өргөтгөхөд маш амархан байх болно. Бид $a$-ийн хувьд 1-ээс эхлэх индексжүүлэлт ашиглана гэдгийг анзаар.

Бид гарч ирж буй бүх тоог тоолдог Хэрчмийн мод ашиглана, өөрөөр хэлбэл Хэрчмийн модонд бид массивын гистограммыг хадгална. Тиймээс навч оройнууд нь $0$, $1$, $\dots$, $n-1$ утгууд массивд хэдэн удаа гарч ирэхийг хадгалах ба бусад оройнууд ямар нэг интервал дахь хэдэн тоо массивд байгааг хадгална. Өөрөөр хэлбэл бид массивын гистограмм дээр нийлбэрийн асуулгатай ердийн Хэрчмийн мод үүсгэнэ. Гэвч боломжит угтвар бүрийн хувьд бүх $n$ Хэрчмийн модыг үүсгэхийн оронд бид ижил мэдээллийг агуулах нэг persistent модыг үүсгэнэ. Бид $root_0$-оор заагдсан хоосон Хэрчмийн модноос (бүх тоолол $0$ байна) эхэлж, $a[1]$, $a[2]$, $\dots$, $a[n]$ элементүүдийг нэг нэгээр нь нэмнэ. Өөрчлөлт бүрийн хувьд бид шинэ үндэс орой хүлээн авах ба $a$ массивын эхний $i$ элементийг оруулсны дараах Хэрчмийн модны үндсийг $root_i$ гэж нэрлэе. $root_i$-д үндэслэсэн Хэрчмийн мод нь $a[1 \dots i]$ угтварын гистограммыг агуулна. Энэ Хэрчмийн модыг ашиглан бид Тэгийн тоог тоолох, $k$ дахь тэгийг хайх-д хэлэлцсэн ижил аргыг ашиглан $k$ дахь элементийн байрлалыг $O(\log n)$ хугацаанд олж чадна.

Одоо бодлогын хязгаарлагдаагүй хувилбар руу орцгооё.

Эхлээд асуулга дээрх хязгаарлалтын тухайд: Эдгээр асуулгыг зөвхөн $a$-ийн угтвар дээр гүйцэтгэхийн оронд бид дурын $a[l \dots r]$ хэрчмүүдийг ашиглахыг хүсэж байна. Энд бидэнд $a[l \dots r]$ интервал дахь элементүүдийн гистограммыг илэрхийлэх Хэрчмийн мод хэрэгтэй. Ийм Хэрчмийн мод нь $root_{r}$-д үндэслэсэн Хэрчмийн мод ба $root_{l-1}$-д үндэслэсэн Хэрчмийн модны зөрүү болохыг харахад амархан, өөрөөр хэлбэл $[l \dots r]$ Хэрчмийн мод дахь орой бүрийг $root_{r}$ модны оройноос $root_{l-1}$ модны оройг хассанаар тооцоолж болно.

$\text{find_kth}$ функцийн хэрэгжүүлэлтэд үүнийг хоёр оройн заагч дамжуулж, одоогийн хэрчмийн тоолол/нийлбэрийг хоёр оройн тоолол/нийлбэрийн зөрүү байдлаар тооцоолох замаар зохицуулж болно.

Өөрчлөгдсөн $\text{build}$, $\text{update}$ ба $\text{find_kth}$ функцүүд энд байна

Vertex* build(int tl, int tr) {
    if (tl == tr)
        return new Vertex(0);
    int tm = (tl + tr) / 2;
    return new Vertex(build(tl, tm), build(tm+1, tr));
}

Vertex* update(Vertex* v, int tl, int tr, int pos) {
    if (tl == tr)
        return new Vertex(v->sum+1);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos));
}

int find_kth(Vertex* vl, Vertex *vr, int tl, int tr, int k) {
    if (tl == tr)
        return tl;
    int tm = (tl + tr) / 2, left_count = vr->l->sum - vl->l->sum;
    if (left_count >= k)
        return find_kth(vl->l, vr->l, tl, tm, k);
    return find_kth(vl->r, vr->r, tm+1, tr, k-left_count);
}

Дээр аль хэдийн бичсэнчлэн бид анхны Хэрчмийн модны үндсийг, мөн шинэчлэл бүрийн дараах бүх үндсийг хадгалах хэрэгтэй. [0, MAX_VALUE] интервал дахь элементүүдтэй a вектор дээр persistent Хэрчмийн мод байгуулах код энд байна.

int tl = 0, tr = MAX_VALUE + 1;
std::vector<Vertex*> roots;
roots.push_back(build(tl, tr));
for (int i = 0; i < a.size(); i++) {
    roots.push_back(update(roots.back(), tl, tr, a[i]));
}

// find the 5th smallest number from the subarray [a[2], a[3], ..., a[19]]
int result = find_kth(roots[2], roots[20], tl, tr, 5);

Одоо массивын элементүүд дээрх хязгаарлалтын тухайд: Бид үнэндээ ямар ч массивыг индексийн шахалтаар ийм массив болгон хувиргаж болно. Массив дахь хамгийн бага элементэд 0 утга, хоёр дахь хамгийн багад 1 утга гэх мэтчилэн оноогдоно. Утгыг индекс рүү нь, эсрэгээр нь $O(\log n)$ хугацаанд хувиргадаг хайлтын хүснэгтийг (жишээ нь $\text{map}$ ашиглан) үүсгэхэд амархан.

Динамик хэрчмийн мод

(Хэлбэр нь динамик бөгөөд зангилаанууд нь ихэвчлэн динамикаар хуваарилагддаг тул ингэж нэрлэсэн. Мөн далд хэрчмийн мод буюу сийрэг хэрчмийн мод гэж нэрлэдэг.)

Өмнө нь бид анхны хэрчмийн модыг байгуулах боломжтой тохиолдлуудыг авч үзсэн. Гэвч анхны хэмжээ нь ямар нэг өгөгдмөл элементээр дүүрсэн боловч хэмжээ нь урьдчилан бүрэн байгуулах боломж олгохгүй бол яах вэ?

Бид энэ бодлогыг хэрчмийн модыг залхуугаар (өсөн нэмэгдэх байдлаар) үүсгэх замаар бодож болно. Эхэндээ бид зөвхөн үндсийг үүсгэх ба бусад оройг зөвхөн хэрэгтэй үед нь үүсгэнэ. Энэ тохиолдолд бид заагч дээрх хэрэгжүүлэлтийг ашиглана (оройн хүүхдүүд рүү очихоосоо өмнө тэдгээр үүссэн эсэхийг шалгаж, үүсээгүй бол үүсгэнэ). Асуулга бүр $O(\log n)$ complexity-тэй хэвээр байх ба энэ нь ихэнх хэрэглээнд хангалттай бага юм (жишээ нь $\log_2 10^9 \approx 30$).

Энэ хэрэгжүүлэлтэд бидэнд хоёр асуулга байна: байрлал дээр утга нэмэх (эхэндээ бүх утга $0$ байна), мөн интервал дахь бүх утгын нийлбэрийг тооцоолох. Vertex(0, n) нь далд модны үндэс орой байх болно.

struct Vertex {
    int left, right;
    int sum = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
    }

    void extend() {
        if (!left_child && left + 1 < right) {
            int t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t, right);
        }
    }

    void add(int k, int x) {
        extend();
        sum += x;
        if (left_child) {
            if (k < left_child->right)
                left_child->add(k, x);
            else
                right_child->add(k, x);
        }
    }

    int get_sum(int lq, int rq) {
        if (lq <= left && right <= rq)
            return sum;
        if (max(left, lq) >= min(right, rq))
            return 0;
        extend();
        return left_child->get_sum(lq, rq) + right_child->get_sum(lq, rq);
    }
};

Энэ санааг олон өөр аргаар өргөтгөж болох нь илэрхий. Жишээ нь залхуу тархалтаар интервалын шинэчлэлийн дэмжлэг нэмэх замаар.

Дасгал бодлогууд