Преди това записах „видео“ и сега организирам съдържанието в статия.

В компютърните науки сегментното дърво е дървовидна структура от данни, използвана за съхраняване на информация за интервали като дърво.

Позволява ефективно да отговаря на заявки за обхват върху масив и все още е достатъчно гъвкав, за да позволи бърза модификация на масива.

Сегментното дърво има мощни възможности и поддържа операции като намиране на сумата от интервал, намиране на максимума на интервал, актуализиране на интервал и актуализиране на единична точка.

проблем

Ако приемем, че има много голям масив, две операции трябва да бъдат изпълнени многократно много пъти върху елементите на този масив.

  • Заявка: Изберете интервал в този масив и намерете сумата от всички елементи в този интервал.
  • Актуализация: Добавете стойност към елемент от масива.

Основна идея

Концепцията за сегментирано дърво е подобна на разделяй и владей.

За да получим ефективно сумата от интервала [l, r] (представен от s), можем да го разделим на два интервала [l, mid] и [mid+1, r]. Ако знаем сумата от [l, mid] (представено от sl) и [mid+1, r] (представено от sr) предварително, можем да получим s = sl + sr директно,както е показано на фигура 1:

Първоначално обаче не знаем sl и sr, така че продължаваме да разделяме интервала, докато дължината на сегмента стане 1. В този момент можем директно да получим сумата на единичния елемент в масива.

Например, за да получим сумата на интервала от [1,4], ние я разделяме на сумата от [1,2] и [3,4], след което на четири интервала: [1,1], [2,2], [3,3] и [4,4].

Като третираме всеки интервал като възел и двата му подинтервала като дъщерни възли, можем да конструираме двоична дървоподобна структура, наречена сегментно дърво, която поддържа сумата от всеки интервал.

Съхранение

Първото съображение при внедряването на сегментно дърво е как да го съхраните в паметта. Един подход е да се дефинира дървовидна структура и да се създадат обекти, които съхраняват границите на сегмента, сумата и указателите към дъщерните възли. Този подход обаче изисква съхраняване на излишна информация под формата на указатели.

За да намалим изискванията за съхранение, можем да използваме прост трик, подобен на двоичните купчини. Вместо да съхраняваме указатели, можем да съхраняваме само сумите в масив, наречен „sum“. Дължината на този масив ще бъде обсъдена скоро.

Сумата на основния възел при индекс 1 (ето защо масивът трябва да бъде индексиран с 1), сумите на неговите два дъщерни възела при индекси 2 и 3, сумите от децата на тези два върха при индекси 4 до 7 , и така нататък.

С 1-индексиране удобно лявото дете на връх при индекс i се съхранява при индекс 2i, а дясното при индекс 2i + 1. Еквивалентно, родителят на възел при индекс i се съхранява в i/2 (целочислено деление), както е показано на фигура 2:

Това много опростява изпълнението. Не е необходимо да съхраняваме структурата на дървото в паметта. Дефинира се имплицитно. Трябва ни само един масив, който съдържа сумите на всички сегменти.

Установихме, че първото ниво на дървото съдържа един възел (корена), второто ниво съдържа 2 възли, а третото ниво съдържа 4 възли. Този модел продължава до последното ниво, където броят на възлите достига n (n представлява дължината на масива A).

Следователно броят на възлите в най-лошия случай може да бъде оценен чрез сумата:

Можем да заключим, че сегментното дърво изисква само линеен брой възли, както е показано на фигура 3:

Струва си да се отбележи, че когато дължината на масива A не е степен на 2, не всички нива на сегментното дърво ще бъдат напълно запълнени. С други думи, сегментното дърво не е непременно пълно двоично дърво.

Фигура 4 показва пример на сегментно дърво за масив с 5 елемента, което не е степен на 2:

Строителство

Алгоритъмът за изграждане на сегментно дърво е както следва:

const int MAX_LEN = 1e5 + 9;

int sum[4 * MAX_LEN];

void build(int A[], int rt, int L, int R)
{
    if (L == R)
    {
        sum[rt] = A[L];
    }
    else
    {
        int mid = (L + R) / 2;
        build(A, rt * 2, L, mid);
        build(A, rt * 2 + 1, mid + 1, R);
        push_up(rt);
    }
}

MAX_LEN е максималната дължина, която може да достигне масив A. Както бе споменато по-рано, масивът от суми трябва да бъде четири пъти по-голям от размера на масива A.

Функцията за изграждане има 4 параметри:

  • Оригиналният масив A
  • Номерът на дървовидния възел (обозначен с rt)
  • Лявата граница на затворен интервал, съответстващ на rt (обозначен с L)
  • Дясната граница на затворен интервал, съответстваща на rt (обозначена с R)

Започваме да конструираме дървото на сегмента в основния възел (номериран 1), с лява граница 1 и дясна граница 8. Следвайки рекурсивен процес, можем да конструираме цялото сегментно дърво.

Когато процедурата се извика на връх, който не е лист, тя прави следното:

  1. Рекурсивно конструира стойностите на двата дъщерни върха.
  2. Обединява изчислените стойности на тези деца.

Когато се достигне листен възел, условието е L = R.

Например, да кажем, че l = 1 и r = 8. Можем да изчислим mid като вземем средната стойност на l и r, което ни дава (1 + 8) / 2 = 4 (закръглено надолу). Този интервал може да бъде разделен на две части: [1, 4] и [5, 8]. Важно е да се отбележи, че стойността на корена в момента не е определена. Ще го изчислим с помощта на функцията pushup, след като получим стойностите на двете му деца.

Процесът е показан на фигура 5:

  • Първо отиваме при лявото дете. Сега l = 1, r = 4 и средата е (1 + 4) / 2 = 2 (закръгляване надолу). Този интервал е разделен на две части: [1,2], [3, 4] .
  • След това отиваме при лявото дете. Сега l = 1, r = 2 и средата е (1 + 1) / 2 = 1 (закръгляване надолу). Този интервал е разделен на две части: [1,1], [2, 2] .
  • След това отиваме при лявото дете. Сега, l = r = 1, така че присвояваме на този възел стойност 2, която е a[1] в оригиналния масив.
  • Когато рекурсивната функция се върне към родителския възел, отиваме към дясното дете. Дясното дете е същото като лявото дете, така че можем да присвоим на този възел стойност 5, която е a[2] в оригиналния масив.
  • Когато рекурсивната функция се върне отново към родителския възел, след получаване на стойността на всички дъщерни възли, можем лесно да получим стойността на родителския възел, която е 2 + 5 = 7. Този процес се нарича лицева опора.

Конструкцията на други възли също може да бъде изведена по аналогия.

След изграждането сегментното дърво е показано на фигура 6:

Червеният шрифт от дясната страна на възела представлява номера на възела, който също е индексът на масива от суми. Числата в полетата представляват стойностите на масива от суми.

За да обобщим процеса на изграждане:

  • Започваме от основния възел и рекурсивно се спускаме до най-долното ниво (листовите възли), за да им присвоим съответните им стойности.
  • Въз основа на тези стойности можем да изчислим стойностите на предишното ниво с помощта на функцията pushup. След това можем да изчислим стойностите на предишното ниво въз основа на тях и да повторим процедурата, докато стигнем до основния връх .

Характеристики

  • Всеки възел в сегментното дърво представлява интервал.
  • Сегментното дърво има уникален коренов възел, който представлява целия диапазон на масива: [1, n].
  • За всеки дъщерен възел той представлява подинтервал в цялата последователност.
  • За всеки листен възел той представлява един елемент в последователността. Всеки дъщерен възел непрекъснато предава информация към своя родителски възел, който съхранява интегрираната информация за всеки от неговите подвъзли.
  • За всеки вътрешен възел [l, r] неговият ляв дъщерен възел е [l, mid], а десният дъщерен възел е [mid+1, r], където mid=(l + r) / 2 (закръглено надолу).

Запитване

След като дървото на сегментите бъде конструирано, следващата стъпка е да използваме тази усъвършенствана структура от данни за ефективно запитване и актуализиране. По-конкретно, трябва да изчислим сумата от интервала [L, R] в O(log n) време .

Алгоритъмът за запитване е както следва:

// rt: current tree node number
// [L, R]: the interval corresponding to node rt
// [ql, qr]: the interval range we want to query,
// in other words [ql, qr] is our target search range
int query(int rt, int L, int R, int ql, int qr)
{ 
    if (ql > R or qr < L)
        return 0;              // Case 1 (disjoint)

    if (ql <= L and R <= qr)
        return sum[rt];        // Case 2 (fully contained)

    int mid = (L + R) >> 1;    // Case 3 (intersection)
    return query(2 * rt, L, mid, ql, qr) + query(2 * rt + 1, mid + 1, R, ql, qr);
}

Функцията за заявка приема 5 параметъра:

  • Номерът на дървовидния възел (обозначен с rt)
  • [L, R] представлява интервала, съответстващ на възел rt
  • [ql, qr] представлява диапазона, който искаме да направим заявка, или с други думи, нашия целеви диапазон на търсене.

За да постигнем това, преминаваме през дървото на сегментите и използваме предварително изчислените суми на сегментите.

Има три възможни случая, като случай 3 вероятно съдържа предишните два случая:

Заявка: Случай 1 (несвързан)

Ако интервалът, съответстващ на текущия възел rt, не е в целевия обхват на търсене, върнете 0.

Заявка: Случай 2 (напълно включен)

Ако интервалът, съответстващ на текущия възел rt, е изцяло в целевия диапазон на търсене, тогава се връща сумата от интервала, съответстващ на rt.

В този случай интервалът, съответстващ на rt, е част от нашия целеви обхват на търсене, така че неговата текуща сума от интервали може да допринесе за сумата на нашия целеви обхват на търсене.

Заявка: Случай 3 (пресичане)

В последния случай целевият обхват на търсене се пресича с текущия интервал. В този сценарий нямаме друга възможност освен да направим две рекурсивни повиквания, по едно за всяко дете.

Първо отиваме до лявото дете и изчисляваме частичен отговор за този възел. Това е сумата от стойностите на пресечната точка между сегмента на заявката и сегмента на лявото дете. След това отиваме до дясното дете и изчисляваме друг частичен отговор. Накрая комбинираме отговорите, като ги добавяме.

Да предположим например, че искаме да поискаме сумата от [3, 5], процесът е показан на фигура 7:

  • Започвайки от корена, откриваме, че нито случай 1, нито случай 2 са удовлетворени, така че правим две рекурсивни извиквания, по едно за всяко дете.
  • Когато стигнем до възел 2, случай 3 е удовлетворен, така че правим две рекурсивни извиквания.
  • Когато достигнем възел 4, случай 3 е удовлетворен. Тъй като [1, 2] и [3, 5] не се пресичат, връщаме 0.
  • Когато достигнем възел 5, случай 2 е удовлетворен. [3, 4] е изцяло в целевия обхват на търсене [3, 5], така че връщаме интервалната сума на 16.
  • Така за левия клон на корена получаваме 16.
  • Според този алгоритъм получаваме друга част от отговора в десния клон на корена, който е 6.
  • Накрая сумираме частичните отговори, които получихме от лявото и дясното поддървета. Крайният отговор е 16 + 6 = 22. Можем ръчно да проверим дали това наистина е правилният отговор за нашия целеви диапазон на търсене от [3, 5].

Актуализация

За да увеличим A[pos] с k, трябва да актуализираме съответния възел в дървото на сегментите.

Актуализирането на дървото е по-лесно, отколкото запитването към него. Алгоритъмът за актуализиране на възел е както следва:

void push_up(int rt)
{
    sum[rt] = sum[rt * 2] + sum[rt * 2 + 1];
}

// rt: current tree node number
// [L, R]: the interval corresponding to node rt
// pos: the index of array A
// k: the value added to A[pos]
// The purpose of this function is to realize A[pos] += k
void update(int rt, int L, int R, int pos, int k)
{
    if (L == R)
    {
        sum[rt] += k;
        return;
    }

    int mid = (L + R) >> 1;
    if (L <= pos and pos <= mid)
        update(rt * 2, L, mid, pos, k);
    if (mid + 1 <= pos and pos <= R)
        update(rt * 2 + 1, mid + 1, R, pos, k);

    push_up(rt);

    return;
}

Функцията за актуализиране приема 5 параметъра:

  • Номерът на дървовидния възел (обозначен с rt)
  • [L, R] представлява интервалът, съответстващ на възел rt
  • pos представлява индекса на масива A
  • k представлява стойността, добавена към A[pos]

Целта е да се намери листовият възел в сегментното дърво, което съответства на A[pos]. Когато листовият възел се актуализира, стойността на родителския възел се актуализира слой по слой чрез функцията push_up.

Например, за да увеличим A[7] с 5, първо обхождаме дървото на сегмента рекурсивно, за да намерим листовия възел, съответстващ на A[7], и след това актуализираме неговата стойност. Ние актуализираме стойността на родителския възел, когато рекурсивната функция се върне към родителския възел.

Както е показано на Фигура 8, веригата от корена до листния възел (зелен кръг на Фигура 8), съответстващ на A[7], се актуализира:

Времева сложност

Конструкция: O(n), съответстваща на броя на възлите в сегментното дърво.

Заявка: O(log n), тъй като целевият обхват на търсене може да бъде разделен на най-много O(log n) интервали и крайният отговор може да бъде получен чрез комбиниране на тези интервали.

Актуализация: O(log n), тъй като всяко ниво на сегментното дърво образува дял на масива, елемент A[pos] допринася само за един сегмент от всяко ниво. Следователно трябва да се актуализират само O(log n) възли.

Тук няма да бъде предоставено по-строго доказателство. Може би ще бъде разработено в бъдеще.

Заключение

Тази статия обяснява основите на сегментното дърво, включително основна идея, съхранение, конструкция, характеристики, заявка и едноточкова актуализация.

Чрез предварителното създаване на усъвършенствани структури от данни като дървета на сегменти можем да извършим две операции, заявка и актуализиране, за O(logn) време. Това значително подобрява ефективността.

Заслужава да се спомене, че Fenwick Tree (Binary Indexed Tree) всъщност е подмножество на Segment Tree. Предимството на двоичното индексирано дърво е, че кодът му е по-кратък, константата му е по-малка, и скоростта му е по-висока.

Дървото на сегментите може да поддържа всички операции, които отговарят на асоциативния закон (като добавяне, умножение, максимална стойност, минимална стойност), а мързеливият таг може също така да направи промяна на интервала за поддръжка на дървото на сегментите (следващата статия ще обясни интервалните актуализации и ленивото разпространение за сегментно дърво), което не може да бъде постигнато от двоично индексирано дърво.

Накрая, ако има пропуски или грешки в тази статия, моля, уведомете ме. Благодаря ви.

Препратки

https://en.wikipedia.org/wiki/Segment_tree

https://cp-algorithms.com/data_structures/segment_tree.html