Дерево відрізків

Дерево відрізків — це структура даних, яка зберігає інформацію про інтервали масиву у вигляді дерева. Це дозволяє ефективно відповідати на запити на відрізку масиву і водночас залишатися достатньо гнучкою, щоб допускати швидку модифікацію масиву. Сюди входить, зокрема, обчислення суми послідовних елементів масиву $a[l \dots r]$ або знаходження мінімального елемента на такому відрізку за час $O(\log n)$. Між відповідями на такі запити дерево відрізків дозволяє модифікувати масив, замінюючи окремий елемент або навіть змінюючи елементи цілого підвідрізка (наприклад, присвоюючи всім елементам $a[l \dots r]$ деяке значення або додаючи значення до всіх елементів підвідрізка).

Узагалі дерево відрізків — це дуже гнучка структура даних, і за допомогою неї можна розв'язати величезну кількість задач. Крім того, на ньому можна виконувати складніші операції та відповідати на складніші запити (див. Розширені версії дерев відрізків). Зокрема, дерево відрізків легко узагальнюється на більші розмірності. Наприклад, за допомогою двовимірного дерева відрізків можна відповідати на запити суми чи мінімуму на деякому підпрямокутнику заданої матриці лише за час $O(\log^2 n)$.

Одна важлива властивість дерев відрізків полягає в тому, що вони потребують лише лінійної кількості пам'яті. Стандартне дерево відрізків потребує $4n$ вершин для роботи з масивом розміру $n$.

Коли підходить цей алгоритм?

• Чи потрібні і запити на відрізку, і оновлення між ними? (якщо масив незмінний → розріджена таблиця)
• Чи є операція лише асоціативною без обернення (наприклад, $\min$/$\max$/$\gcd$) або потрібні складні відкладені оновлення на відрізку? (якщо операція оборотна, як сума, і вистачає точкових оновлень → простіше дерево Фенвіка)
• Чи виправдане $O(\log n)$ на запит порівняно з простішим у написанні $O(\sqrt n)$? (якщо ні, а потрібна гнучкість і простота → кореневе розбиття)

Найпростіша форма дерева відрізків

Щоб почати з легшого, розглянемо найпростішу форму дерева відрізків. Ми хочемо ефективно відповідати на запити суми. Формально наше завдання таке: заданий масив $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]$, і кожна вершина (крім листових) має рівно дві дочірні вершини. Саме тому ця структура даних і називається «деревом відрізків», хоча в більшості реалізацій дерево не будується явно (див. Реалізація).

Ось наочне зображення такого дерева відрізків над масивом $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. операцією злиття (merge), яка зливає двох «братів» у дереві відрізків. Наприклад, у дереві відрізків для суми два вузли, що відповідають діапазонам $a[l_1 \dots r_1]$ та $a[l_2 \dots r_2]$, зливаються у вузол, що відповідає діапазону $a[l_1 \dots r_2]$, додаванням значень цих двох вузлів.

Зауважимо, що вершина є «листовою», якщо відповідний їй відрізок покриває лише одне значення вихідного масиву. Вона міститься на найнижчому рівні дерева відрізків. Її значення дорівнюватиме (відповідному) елементу $a[i]$.

Тепер, для побудови дерева відрізків, ми починаємо з нижнього рівня (листових вершин) і присвоюємо їм відповідні значення. На основі цих значень ми можемо обчислити значення попереднього рівня за допомогою функції merge. А на їх основі ми можемо обчислити значення попереднього рівня, і повторюємо цю процедуру, доки не дійдемо до кореневої вершини.

Цю операцію зручно описати рекурсивно в іншому напрямку, тобто від кореневої вершини до листових. Процедура побудови, якщо її викликати на нелистовій вершині, робить таке:

1. рекурсивно будує значення двох дочірніх вершин;
2. зливає обчислені значення цих дітей.

Ми починаємо побудову з кореневої вершини, і завдяки цьому можемо обчислити все дерево відрізків.

Часова складність цієї побудови — $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$.

Чому складність цього алгоритму $O(\log n)$? Щоб показати цю складність, поглянемо на кожен рівень дерева. Виявляється, що на кожному рівні ми відвідуємо не більше ніж чотири вершини. А оскільки висота дерева становить $O(\log n)$, ми отримуємо бажаний час роботи.

Ми можемо показати, що це твердження (не більше чотирьох вершин на кожному рівні) істинне, за індукцією. На першому рівні ми відвідуємо лише одну вершину, кореневу, тож тут ми відвідуємо менш ніж чотири вершини. Тепер поглянемо на довільний рівень. За припущенням індукції, ми відвідуємо не більше чотирьох вершин. Якщо ми відвідуємо не більше двох вершин, то наступний рівень має не більше чотирьох вершин. Це тривіально, бо кожна вершина може спричинити не більше двох рекурсивних викликів. Тож припустімо, що на поточному рівні ми відвідуємо три або чотири вершини. З цих вершин ми ретельніше проаналізуємо вершини посередині. Оскільки запит суми просить суму неперервного підмасиву, ми знаємо, що відрізки, які відповідають відвіданим вершинам посередині, будуть повністю покриті відрізком запиту суми. Тому ці вершини не зроблять жодних рекурсивних викликів. Отже, лише найлівіша та найправіша вершини матимуть потенціал зробити рекурсивні виклики. А вони створять не більше чотирьох рекурсивних викликів, тож і наступний рівень задовольнятиме твердження. Можна сказати, що одна гілка наближається до лівої межі запиту, а друга гілка наближається до правої.

Тому ми відвідуємо загалом не більше ніж $4 \log n$ вершин, а це дорівнює часу роботи $O(\log n)$.

Підсумовуючи: запит працює, розбиваючи вхідний відрізок на кілька підвідрізків, для яких усі суми вже попередньо обчислені й збережені в дереві. І якщо ми припиняємо розбиття щоразу, коли відрізок запиту збігається з відрізком вершини, то нам потрібно лише $O(\log n)$ таких відрізків, що й дає ефективність дерева відрізків.

Запити оновлення

Тепер ми хочемо змінити конкретний елемент масиву, скажімо, виконати присвоєння $a[i] = x$. І нам потрібно перебудувати дерево відрізків так, щоб воно відповідало новому, зміненому масиву.

Цей запит простіший за запит суми. Кожен рівень дерева відрізків утворює розбиття масиву. Тому елемент $a[i]$ входить лише в один відрізок з кожного рівня. Отже, потрібно оновити лише $O(\log n)$ вершин.

Легко бачити, що запит оновлення можна реалізувати за допомогою рекурсивної функції. Функції передається поточна вершина дерева, і вона рекурсивно викликає сама себе з однією з двох дочірніх вершин (тією, що містить $a[i]$ у своєму відрізку), а після цього перераховує своє значення суми, подібно до того, як це робиться в методі побудови (тобто як суму своїх двох дітей).

Знову ж таки, ось візуалізація з використанням того самого масиву. Тут ми виконуємо оновлення $a[2] = 3$. Зелені вершини — це вершини, які ми відвідуємо й оновлюємо.

Реалізація ###

Головне питання — як зберігати дерево відрізків. Звісно, ми можемо означити структуру $\text{Vertex}$ і створювати об'єкти, які зберігають межі відрізка, його суму, а також вказівники на дочірні вершини. Однак це потребує зберігання великої кількості зайвої інформації у вигляді вказівників. Ми використаємо простий трюк, щоб зробити це набагато ефективнішим, застосувавши неявну структуру даних: зберігатимемо лише суми в масиві. (Подібний метод використовується для бінарних куп.) Сума кореневої вершини — за індексом 1, суми її двох дочірніх вершин — за індексами 2 і 3, суми дітей цих двох вершин — за індексами від 4 до 7, і так далі. За індексації з 1 зручно, що ліва дитина вершини за індексом $i$ зберігається за індексом $2i$, а права — за індексом $2i + 1$. Аналогічно, батько вершини за індексом $i$ зберігається за індексом $i/2$ (цілочислове ділення).

Це значно спрощує реалізацію. Нам не потрібно зберігати структуру дерева в пам'яті. Вона визначена неявно. Нам потрібен лише один масив, який містить суми всіх відрізків.

Як зазначено раніше, нам потрібно зберігати не більше ніж $4n$ вершин. Їх може бути менше, але для зручності ми завжди виділяємо масив розміру $4n$. У масиві сум будуть деякі елементи, які не відповідатимуть жодним вершинам реального дерева, але це не ускладнює реалізацію.

Отже, ми зберігаємо дерево відрізків просто як масив $t[]$ розміру, що в чотири рази більший за вхідний розмір $n$:

C++

int n, t[4*MAXN];

Python

# розмір масиву та дерево відрізків (зберігаємо суми)
n = 0
t = [0] * (4 * MAXN)

TypeScript

let n: number; // розмір масиву
const t: number[] = new Array(4 * MAXN).fill(0); // дерево відрізків (суми)

Go

var n int            // розмір масиву
var t = make([]int, 4*MAXN) // дерево відрізків (суми)

Процедура побудови дерева відрізків із заданого масиву $a[]$ виглядає так: це рекурсивна функція з параметрами $a[]$ (вхідний масив), $v$ (індекс поточної вершини) та межами $tl$ і $tr$ поточного відрізка. У головній програмі ця функція викликатиметься з параметрами кореневої вершини: $v = 1$, $tl = 0$, $tr = n - 1$.

C++

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];
    }
}

Python

def build(a, v, tl, tr):
    if tl == tr:
        t[v] = a[tl]
    else:
        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]

TypeScript

function build(a: number[], v: number, tl: number, tr: number): void {
  if (tl === tr) {
    t[v] = a[tl];
  } else {
    const tm = (tl + tr) >> 1;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    t[v] = t[v * 2] + t[v * 2 + 1];
  }
}

Go

func build(a []int, v, tl, tr int) {
    if tl == tr {
        t[v] = a[tl]
    } else {
        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]
    }
}

Далі, функція для відповіді на запити суми також є рекурсивною; вона отримує як параметри інформацію про поточну вершину/відрізок (тобто індекс $v$ та межі $tl$ і $tr$), а також інформацію про межі запиту, $l$ і $r$. Щоб спростити код, ця функція завжди робить два рекурсивні виклики, навіть якщо потрібен лише один — у цьому випадку зайвий рекурсивний виклик матиме $l > r$, і це легко вловити додатковою перевіркою на початку функції.

C++

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);
}

Python

def sum(v, tl, tr, l, r):
    if l > r:
        return 0
    if l == tl and r == tr:
        return t[v]
    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))

TypeScript

function sum(v: number, tl: number, tr: number, l: number, r: number): number {
  if (l > r) return 0;
  if (l === tl && r === tr) return t[v];
  const tm = (tl + tr) >> 1;
  return (
    sum(v * 2, tl, tm, l, Math.min(r, tm)) +
    sum(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r)
  );
}

Go

func sum(v, tl, tr, l, r int) int {
    if l > r {
        return 0
    }
    if l == tl && r == tr {
        return t[v]
    }
    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)
}

Нарешті, запит оновлення. Функція також отримуватиме інформацію про поточну вершину/відрізок, а додатково — і параметри запиту оновлення (тобто позицію елемента та його нове значення).

C++

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];
    }
}

Python

def update(v, tl, tr, pos, new_val):
    if tl == tr:
        t[v] = new_val
    else:
        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]

TypeScript

function update(v: number, tl: number, tr: number, pos: number, newVal: number): void {
  if (tl === tr) {
    t[v] = newVal;
  } else {
    const tm = (tl + tr) >> 1;
    if (pos <= tm) update(v * 2, tl, tm, pos, newVal);
    else update(v * 2 + 1, tm + 1, tr, pos, newVal);
    t[v] = t[v * 2] + t[v * 2 + 1];
  }
}

Go

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

Реалізація, ощадлива до пам'яті

Більшість людей використовують реалізацію з попереднього розділу. Якщо поглянути на масив t, можна побачити, що він дотримується нумерації вузлів дерева в порядку обходу в ширину (порівневий обхід). За такого обходу дітьми вершини $v$ є відповідно $2v$ та $2v + 1$. Однак якщо $n$ не є степенем двійки, цей метод пропускатиме деякі індекси й залишатиме деякі частини масиву t невикористаними. Споживання пам'яті обмежене $4n$, хоча дерево відрізків над масивом із $n$ елементів потребує лише $2n - 1$ вершин.

Однак це можна зменшити. Ми перенумеруємо вершини дерева в порядку обходу за ейлеровим маршрутом (прямий обхід, pre-order) і запишемо всі ці вершини одну за одною.

Поглянемо на вершину за індексом $v$, нехай вона відповідає за відрізок $[l, r]$, і нехай $mid = \dfrac{l + r}{2}$. Очевидно, що ліва дитина матиме індекс $v + 1$. Ліва дитина відповідає за відрізок $[l, mid]$, тобто загалом у піддереві лівої дитини буде $2 * (mid - l + 1) - 1$ вершин. Отже, ми можемо обчислити індекс правої дитини вершини $v$. Цей індекс буде $v + 2 * (mid - l + 1)$. За такої нумерації ми досягаємо зменшення необхідної пам'яті до $2n$.

Розширені версії дерев відрізків

Дерево відрізків — це дуже гнучка структура даних, яка допускає варіації та розширення в багатьох різних напрямках. Спробуймо класифікувати їх нижче.

Складніші запити

Дерево відрізків буває досить легко змінити в напрямку, щоб воно обчислювало інші запити (наприклад, обчислювало мінімум / максимум замість суми), але це також може бути дуже нетривіально.

Знаходження максимуму

Трохи змінимо умову описаної вище задачі: замість запитів суми ми тепер робитимемо запити максимуму.

Дерево матиме точно таку саму структуру, як описане вище дерево. Нам потрібно лише змінити спосіб обчислення $t[v]$ у функціях $\text{build}$ та $\text{update}$. $t[v]$ тепер зберігатиме максимум відповідного відрізка. А ще нам потрібно змінити обчислення значення, що повертається функцією $\text{sum}$ (замінивши підсумовування на максимум).

Звісно, цю задачу легко змінити на обчислення мінімуму замість максимуму.

Замість того щоб показувати реалізацію для цієї задачі, реалізацію буде наведено для складнішої версії цієї задачі в наступному розділі.

Знаходження максимуму та кількості його появ

Це завдання дуже схоже на попереднє. Окрім знаходження максимуму, нам потрібно також знайти кількість входжень максимуму.

Щоб розв'язати цю задачу, ми зберігаємо в кожній вершині дерева пару чисел: окрім максимуму, ми також зберігаємо кількість його входжень у відповідному відрізку. Визначення правильної пари для зберігання в $t[v]$ так само можна зробити за сталий час, використовуючи інформацію пар, що зберігаються в дочірніх вершинах. Поєднання двох таких пар варто винести в окрему функцію, оскільки це операція, яку ми робитимемо під час побудови дерева, під час відповіді на запити максимуму та під час виконання модифікацій.

C++

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]);
    }
}

Python

# кожна вершина зберігає пару (максимум, кількість його входжень)
t = [(0, 0)] * (4 * MAXN)

def combine(a, b):
    if a[0] > b[0]:
        return a
    if b[0] > a[0]:
        return b
    return (a[0], a[1] + b[1])

def build(a, v, tl, tr):
    if tl == tr:
        t[v] = (a[tl], 1)
    else:
        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])

def get_max(v, tl, tr, l, r):
    if l > r:
        return (-INF, 0)
    if l == tl and r == tr:
        return t[v]
    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))

def update(v, tl, tr, pos, new_val):
    if tl == tr:
        t[v] = (new_val, 1)
    else:
        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])

TypeScript

// кожна вершина зберігає пару [максимум, кількість його входжень]
type MaxCount = [number, number];
const t: MaxCount[] = new Array(4 * MAXN).fill(null).map(() => [0, 0] as MaxCount);

function combine(a: MaxCount, b: MaxCount): MaxCount {
  if (a[0] > b[0]) return a;
  if (b[0] > a[0]) return b;
  return [a[0], a[1] + b[1]];
}

function build(a: number[], v: number, tl: number, tr: number): void {
  if (tl === tr) {
    t[v] = [a[tl], 1];
  } else {
    const tm = (tl + tr) >> 1;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    t[v] = combine(t[v * 2], t[v * 2 + 1]);
  }
}

function getMax(v: number, tl: number, tr: number, l: number, r: number): MaxCount {
  if (l > r) return [-INF, 0];
  if (l === tl && r === tr) return t[v];
  const tm = (tl + tr) >> 1;
  return combine(
    getMax(v * 2, tl, tm, l, Math.min(r, tm)),
    getMax(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r)
  );
}

function update(v: number, tl: number, tr: number, pos: number, newVal: number): void {
  if (tl === tr) {
    t[v] = [newVal, 1];
  } else {
    const tm = (tl + tr) >> 1;
    if (pos <= tm) update(v * 2, tl, tm, pos, newVal);
    else update(v * 2 + 1, tm + 1, tr, pos, newVal);
    t[v] = combine(t[v * 2], t[v * 2 + 1]);
  }
}

Go

// кожна вершина зберігає пару (максимум, кількість його входжень)
type maxCount struct{ mx, cnt int }

var t = make([]maxCount, 4*MAXN)

func combine(a, b maxCount) maxCount {
    if a.mx > b.mx {
        return a
    }
    if b.mx > a.mx {
        return b
    }
    return maxCount{a.mx, a.cnt + b.cnt}
}

func build(a []int, v, tl, tr int) {
    if tl == tr {
        t[v] = maxCount{a[tl], 1}
    } else {
        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])
    }
}

func getMax(v, tl, tr, l, r int) maxCount {
    if l > r {
        return maxCount{-INF, 0}
    }
    if l == tl && r == tr {
        return t[v]
    }
    tm := (tl + tr) / 2
    return combine(getMax(v*2, tl, tm, l, min(r, tm)),
        getMax(v*2+1, tm+1, tr, max(l, tm+1), r))
}

func update(v, tl, tr, pos, newVal int) {
    if tl == tr {
        t[v] = maxCount{newVal, 1}
    } else {
        tm := (tl + tr) / 2
        if pos <= tm {
            update(v*2, tl, tm, pos, newVal)
        } else {
            update(v*2+1, tm+1, tr, pos, newVal)
        }
        t[v] = combine(t[v*2], t[v*2+1])
    }
}

Обчислення найбільшого спільного дільника / найменшого спільного кратного

У цій задачі ми хочемо обчислити НСД / НСК усіх чисел на заданих діапазонах масиву.

Цю цікаву варіацію дерева відрізків можна розв'язати точно так само, як дерева відрізків, які ми вивели для запитів суми / мінімуму / максимуму: достатньо зберігати в кожній вершині дерева НСД / НСК відповідної вершини. Поєднання двох вершин можна зробити обчисленням НСД / НСК обох вершин.

Підрахунок кількості нулів, пошук $k$-го нуля

У цій задачі ми хочемо знайти кількість нулів у заданому діапазоні, а також знайти індекс $k$-го нуля за допомогою другої функції.

Знову ж таки, нам доведеться трохи змінити значення, які зберігаються в дереві: цього разу ми зберігатимемо кількість нулів у кожному відрізку в $t[]$. Цілком зрозуміло, як реалізувати функції $\text{build}$, $\text{update}$ та $\text{count\_zero}$ — ми можемо просто скористатися ідеями із задачі про запит суми. Так ми розв'язали першу частину задачі.

Тепер навчімося розв'язувати задачу про знаходження $k$-го нуля в масиві $a[]$. Щоб виконати це завдання, ми спускатимемося деревом відрізків, починаючи з кореневої вершини, і щоразу переходитимемо або до лівої, або до правої дитини, залежно від того, який відрізок містить $k$-й нуль. Щоб вирішити, до якої дитини нам треба піти, достатньо поглянути на кількість нулів у відрізку, що відповідає лівій вершині. Якщо ця попередньо обчислена кількість більша або дорівнює $k$, треба спуститися до лівої дитини, інакше — до правої дитини. Зауважте: якщо ми обрали праву дитину, то маємо відняти кількість нулів лівої дитини від $k$.

У реалізації ми можемо обробити окремий випадок, коли $a[]$ містить менш ніж $k$ нулів, повертаючи -1.

C++

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]);
}

Python

# t[v] зберігає кількість нулів у відрізку
def find_kth(v, tl, tr, k):
    if k > t[v]:
        return -1
    if tl == tr:
        return tl
    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])

TypeScript

// t[v] зберігає кількість нулів у відрізку
function findKth(v: number, tl: number, tr: number, k: number): number {
  if (k > t[v]) return -1;
  if (tl === tr) return tl;
  const tm = (tl + tr) >> 1;
  if (t[v * 2] >= k) return findKth(v * 2, tl, tm, k);
  else return findKth(v * 2 + 1, tm + 1, tr, k - t[v * 2]);
}

Go

// t[v] зберігає кількість нулів у відрізку
func findKth(v, tl, tr, k int) int {
    if k > t[v] {
        return -1
    }
    if tl == tr {
        return tl
    }
    tm := (tl + tr) / 2
    if t[v*2] >= k {
        return findKth(v*2, tl, tm, k)
    }
    return findKth(v*2+1, tm+1, tr, k-t[v*2])
}

Пошук префікса масиву із заданою сумою

Завдання таке: для заданого значення $x$ ми маємо швидко знайти найменший індекс $i$ такий, що сума перших $i$ елементів масиву $a[]$ більша або дорівнює $x$ (за припущення, що масив $a[]$ містить лише невід'ємні значення).

Це завдання можна розв'язати за допомогою бінарного пошуку, обчислюючи суму префіксів за допомогою дерева відрізків. Однак це призведе до розв'язку зі складністю $O(\log^2 n)$.

Натомість ми можемо скористатися тією самою ідеєю, що й у попередньому розділі, і знайти позицію, спускаючись деревом: щоразу переходячи ліворуч або праворуч, залежно від суми лівої дитини. Так ми знаходимо відповідь за час $O(\log n)$.

Пошук першого елемента, більшого за задану величину

Завдання таке: для заданого значення $x$ та діапазону $a[l \dots r]$ знайти найменший $i$ у діапазоні $a[l \dots r]$ такий, що $a[i]$ більший за $x$.

Це завдання можна розв'язати за допомогою бінарного пошуку над запитами максимуму префіксів за допомогою дерева відрізків. Однак це призведе до розв'язку зі складністю $O(\log^2 n)$.

Натомість ми можемо скористатися тією самою ідеєю, що й у попередніх розділах, і знайти позицію, спускаючись деревом: щоразу переходячи ліворуч або праворуч, залежно від максимального значення лівої дитини. Так ми знаходимо відповідь за час $O(\log n)$.

C++

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);
}

Python

# t[v] зберігає максимум відрізка
def get_first(v, tl, tr, l, r, x):
    if tl > r or tr < l:
        return -1
    if t[v] <= x:
        return -1
    if tl == tr:
        return tl
    tm = tl + (tr - tl) // 2
    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)

TypeScript

// t[v] зберігає максимум відрізка
function getFirst(v: number, tl: number, tr: number, l: number, r: number, x: number): number {
  if (tl > r || tr < l) return -1;
  if (t[v] <= x) return -1;
  if (tl === tr) return tl;
  const tm = tl + ((tr - tl) >> 1);
  const left = getFirst(2 * v, tl, tm, l, r, x);
  if (left !== -1) return left;
  return getFirst(2 * v + 1, tm + 1, tr, l, r, x);
}

Go

// t[v] зберігає максимум відрізка
func getFirst(v, tl, tr, l, r, x int) int {
    if tl > r || tr < l {
        return -1
    }
    if t[v] <= x {
        return -1
    }
    if tl == tr {
        return tl
    }
    tm := tl + (tr-tl)/2
    left := getFirst(2*v, tl, tm, l, r, x)
    if left != -1 {
        return left
    }
    return getFirst(2*v+1, tm+1, tr, l, r, x)
}

Знаходження підвідрізків з максимальною сумою

Тут ми знову для кожного запиту отримуємо діапазон $a[l \dots r]$, але цього разу маємо знайти підвідрізок $a[l^\prime \dots r^\prime]$ такий, що $l \le l^\prime$ та $r^\prime \le r$, і сума елементів цього відрізка є максимальною. Як і раніше, ми також хочемо вміти модифікувати окремі елементи масиву. Елементи масиву можуть бути від'ємними, а оптимальний підвідрізок може бути порожнім (наприклад, якщо всі елементи від'ємні).

Ця задача — нетривіальне використання дерева відрізків. Цього разу ми зберігатимемо чотири значення для кожної вершини: суму відрізка, максимальну префіксну суму, максимальну суфіксну суму та суму максимального підвідрізка в ньому. Інакше кажучи, для кожного відрізка дерева відрізків відповідь уже попередньо обчислена, як і відповіді для відрізків, що торкаються лівої та правої меж відрізка.

Як побудувати дерево з такими даними? Знову ж таки, ми обчислюємо це рекурсивно: спочатку обчислюємо всі чотири значення для лівої та правої дитини, а потім поєднуємо їх, щоб отримати чотири значення для поточної вершини. Зауважте, що відповідь для поточної вершини — це одне з:

• відповідь лівої дитини, що означає, що оптимальний підвідрізок цілком розташований у відрізку лівої дитини;
• відповідь правої дитини, що означає, що оптимальний підвідрізок цілком розташований у відрізку правої дитини;
• сума максимальної суфіксної суми лівої дитини та максимальної префіксної суми правої дитини, що означає, що оптимальний підвідрізок перетинається з обома дітьми.

Отже, відповідь для поточної вершини — це максимум із цих трьох значень. Обчислення максимальної префіксної / суфіксної суми ще простіше. Ось реалізація функції $\text{combine}$, яка отримує лише дані від лівої та правої дитини й повертає дані поточної вершини.

C++

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;
}

Python

# data = (sum, pref, suff, ans):
# сума, макс. префіксна сума, макс. суфіксна сума, макс. підвідрізок
def combine(l, r):
    s = l[0] + r[0]
    pref = max(l[1], l[0] + r[1])
    suff = max(r[2], r[0] + l[2])
    ans = max(l[3], r[3], l[2] + r[1])
    return (s, pref, suff, ans)

TypeScript

// Data = [sum, pref, suff, ans]:
// сума, макс. префіксна сума, макс. суфіксна сума, макс. підвідрізок
type Data = [number, number, number, number];

function combine(l: Data, r: Data): Data {
  const sum = l[0] + r[0];
  const pref = Math.max(l[1], l[0] + r[1]);
  const suff = Math.max(r[2], r[0] + l[2]);
  const ans = Math.max(l[3], r[3], l[2] + r[1]);
  return [sum, pref, suff, ans];
}

Go

// data: сума, макс. префіксна сума, макс. суфіксна сума, макс. підвідрізок
type data struct {
    sum, pref, suff, ans int
}

func combine(l, r data) data {
    return data{
        sum:  l.sum + r.sum,
        pref: max(l.pref, l.sum+r.pref),
        suff: max(r.suff, r.sum+l.suff),
        ans:  max(max(l.ans, r.ans), l.suff+r.pref),
    }
}

За допомогою функції $\text{combine}$ легко побудувати дерево відрізків. Ми можемо реалізувати це точно так само, як у попередніх реалізаціях. Щоб ініціалізувати листові вершини, ми додатково створюємо допоміжну функцію $\text{make\_data}$, яка повертатиме об'єкт $\text{data}$, що містить інформацію про одне значення.

C++

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]);
    }
}

Python

def make_data(val):
    return (val, max(0, val), max(0, val), max(0, val))

def build(a, v, tl, tr):
    if tl == tr:
        t[v] = make_data(a[tl])
    else:
        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])

def update(v, tl, tr, pos, new_val):
    if tl == tr:
        t[v] = make_data(new_val)
    else:
        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])

TypeScript

function makeData(val: number): Data {
  const m = Math.max(0, val);
  return [val, m, m, m];
}

function build(a: number[], v: number, tl: number, tr: number): void {
  if (tl === tr) {
    t[v] = makeData(a[tl]);
  } else {
    const tm = (tl + tr) >> 1;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    t[v] = combine(t[v * 2], t[v * 2 + 1]);
  }
}

function update(v: number, tl: number, tr: number, pos: number, newVal: number): void {
  if (tl === tr) {
    t[v] = makeData(newVal);
  } else {
    const tm = (tl + tr) >> 1;
    if (pos <= tm) update(v * 2, tl, tm, pos, newVal);
    else update(v * 2 + 1, tm + 1, tr, pos, newVal);
    t[v] = combine(t[v * 2], t[v * 2 + 1]);
  }
}

Go

func makeData(val int) data {
    m := max(0, val)
    return data{sum: val, pref: m, suff: m, ans: m}
}

func build(a []int, v, tl, tr int) {
    if tl == tr {
        t[v] = makeData(a[tl])
    } else {
        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])
    }
}

func update(v, tl, tr, pos, newVal int) {
    if tl == tr {
        t[v] = makeData(newVal)
    } else {
        tm := (tl + tr) / 2
        if pos <= tm {
            update(v*2, tl, tm, pos, newVal)
        } else {
            update(v*2+1, tm+1, tr, pos, newVal)
        }
        t[v] = combine(t[v*2], t[v*2+1])
    }
}

Залишається тільки те, як обчислити відповідь на запит. Щоб відповісти на нього, ми спускаємося деревом, як і раніше, розбиваючи запит на кілька підвідрізків, що збігаються з відрізками дерева відрізків, і поєднуємо відповіді в них у єдину відповідь на запит. Тоді має бути зрозуміло, що робота точно така сама, як у простому дереві відрізків, але замість підсумовування / мінімізації / максимізації значень ми використовуємо функцію $\text{combine}$.

C++

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));
}

Python

def query(v, tl, tr, l, r):
    if l > r:
        return make_data(0)
    if l == tl and r == tr:
        return t[v]
    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))

TypeScript

function query(v: number, tl: number, tr: number, l: number, r: number): Data {
  if (l > r) return makeData(0);
  if (l === tl && r === tr) return t[v];
  const tm = (tl + tr) >> 1;
  return combine(
    query(v * 2, tl, tm, l, Math.min(r, tm)),
    query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r)
  );
}

Go

func query(v, tl, tr, l, r int) data {
    if l > r {
        return makeData(0)
    }
    if l == tl && r == tr {
        return t[v]
    }
    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))
}

Зберігання цілих підмасивів у кожній вершині

Це окремий підрозділ, що стоїть осторонь від інших, бо в кожній вершині дерева відрізків ми зберігаємо інформацію про відповідний відрізок не у стиснутій формі (сума, мінімум, максимум, ...), а зберігаємо всі елементи відрізка. Таким чином, корінь дерева відрізків зберігатиме всі елементи масиву, ліва дочірня вершина зберігатиме першу половину масиву, права вершина — другу половину, і так далі.

У найпростішому застосуванні цієї техніки ми зберігаємо елементи у відсортованому порядку. У складніших версіях елементи зберігаються не в списках, а в досконаліших структурах даних (множинах, відображеннях, ...). Але всі ці методи мають спільну рису: кожна вершина потребує лінійної пам'яті (тобто пропорційної довжині відповідного відрізка).

Перше природне питання, коли ми розглядаємо такі дерева відрізків, — про споживання пам'яті. Інтуїтивно це може виглядати як $O(n^2)$ пам'яті, але виявляється, що все дерево потребуватиме лише $O(n \log n)$ пам'яті. Чому так? Доволі просто: бо кожен елемент масиву потрапляє в $O(\log n)$ відрізків (пам'ятаймо, що висота дерева становить $O(\log n)$).

Тож, попри уявну марнотратність такого дерева відрізків, воно споживає лише трохи більше пам'яті, ніж звичайне дерево відрізків.

Нижче описано кілька типових застосувань цієї структури даних. Варто зауважити схожість цих дерев відрізків із двовимірними структурами даних (фактично це двовимірна структура даних, але з доволі обмеженими можливостями).

Знайти найменше число, більше або рівне заданому. Без запитів модифікації.

Ми хочемо відповідати на запити такого виду: для трьох заданих чисел $(l, r, x)$ ми маємо знайти мінімальне число у відрізку $a[l \dots r]$, яке більше або дорівнює $x$.

Ми будуємо дерево відрізків. У кожній вершині ми зберігаємо відсортований список усіх чисел, що зустрічаються у відповідному відрізку, як описано вище. Як побудувати таке дерево відрізків якомога ефективніше? Як завжди, ми підходимо до цієї задачі рекурсивно: нехай списки лівої та правої дитини вже побудовані, і ми хочемо побудувати список для поточної вершини. З цієї точки зору операція тепер тривіальна й може бути виконана за лінійний час: нам потрібно лише поєднати два відсортовані списки в один, що можна зробити, проходячи по них за допомогою двох вказівників. У C++ STL уже є реалізація цього алгоритму.

Через таку структуру дерева відрізків і схожість з алгоритмом сортування злиттям цю структуру даних часто також називають «деревом злиття» (Merge Sort Tree).

C++

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]));
    }
}

Python

# у кожній вершині зберігаємо відсортований список елементів відрізка
t = [[] for _ in range(4 * MAXN)]

def _merge(left, right):
    # злиття двох відсортованих списків (як у сортуванні злиттям)
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

def build(a, v, tl, tr):
    if tl == tr:
        t[v] = [a[tl]]
    else:
        tm = (tl + tr) // 2
        build(a, v * 2, tl, tm)
        build(a, v * 2 + 1, tm + 1, tr)
        t[v] = _merge(t[v * 2], t[v * 2 + 1])

TypeScript

// у кожній вершині зберігаємо відсортований список елементів відрізка
const t: number[][] = new Array(4 * MAXN).fill(null).map(() => []);

function mergeSorted(left: number[], right: number[]): number[] {
  // злиття двох відсортованих списків (як у сортуванні злиттям)
  const res: number[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) res.push(left[i++]);
    else res.push(right[j++]);
  }
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

function build(a: number[], v: number, tl: number, tr: number): void {
  if (tl === tr) {
    t[v] = [a[tl]];
  } else {
    const tm = (tl + tr) >> 1;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    t[v] = mergeSorted(t[v * 2], t[v * 2 + 1]);
  }
}

Go

// у кожній вершині зберігаємо відсортований список елементів відрізка
var t = make([][]int, 4*MAXN)

func mergeSorted(left, right []int) []int {
    // злиття двох відсортованих списків (як у сортуванні злиттям)
    res := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            res = append(res, left[i])
            i++
        } else {
            res = append(res, right[j])
            j++
        }
    }
    res = append(res, left[i:]...)
    res = append(res, right[j:]...)
    return res
}

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

Ми вже знаємо, що побудоване в такий спосіб дерево відрізків потребуватиме $O(n \log n)$ пам'яті. І завдяки цій реалізації його побудова також займає $O(n \log n)$ часу, адже кожен список будується за лінійний час відносно свого розміру.

Тепер розгляньмо відповідь на запит. Ми спускатимемося деревом, як у звичайному дереві відрізків, розбиваючи наш відрізок $a[l \dots r]$ на кілька підвідрізків (на не більш ніж $O(\log n)$ частин). Зрозуміло, що відповідь на весь запит — це мінімум кожного з підзапитів. Тож тепер нам потрібно лише зрозуміти, як відповісти на запит на одному такому підвідрізку, що відповідає деякій вершині дерева.

Ми перебуваємо в деякій вершині дерева відрізків і хочемо обчислити відповідь на запит, тобто знайти мінімальне число, більше або рівне заданому числу $x$. Оскільки вершина містить список елементів у відсортованому порядку, ми можемо просто виконати бінарний пошук у цьому списку й повернути перше число, більше або рівне $x$.

Отже, відповідь на запит в одному відрізку дерева займає $O(\log n)$ часу, а весь запит обробляється за $O(\log^2 n)$.

C++

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));
}

Python

from bisect import bisect_left

def query(v, tl, tr, l, r, x):
    if l > r:
        return INF
    if l == tl and r == tr:
        # перший елемент >= x у відсортованому списку вершини
        pos = bisect_left(t[v], x)
        if pos != len(t[v]):
            return t[v][pos]
        return INF
    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))

TypeScript

function lowerBound(arr: number[], x: number): number {
  // перший індекс, де arr[i] >= x
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function query(v: number, tl: number, tr: number, l: number, r: number, x: number): number {
  if (l > r) return INF;
  if (l === tl && r === tr) {
    const pos = lowerBound(t[v], x);
    if (pos !== t[v].length) return t[v][pos];
    return INF;
  }
  const tm = (tl + tr) >> 1;
  return Math.min(
    query(v * 2, tl, tm, l, Math.min(r, tm), x),
    query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, x)
  );
}

Go

import "sort"

func query(v, tl, tr, l, r, x int) int {
    if l > r {
        return INF
    }
    if l == tl && r == tr {
        // перший елемент >= x у відсортованому списку вершини
        pos := sort.SearchInts(t[v], x)
        if pos != len(t[v]) {
            return t[v][pos]
        }
        return INF
    }
    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 не гарантує такої часової складності).

Функція $\text{query}$ також майже еквівалентна, тільки тепер замість цього слід викликати функцію $\text{lower\_bound}$ самого $\text{multiset}$ ($\text{std::lower\_bound}$ працює за час $O(\log n)$, лише якщо використовується з ітераторами довільного доступу).

Нарешті, запит модифікації. Щоб його обробити, ми маємо спуститися деревом і модифікувати всі $\text{multiset}$-и з відповідних відрізків, які містять зачеплений елемент. Ми просто видаляємо старе значення цього елемента (але лише одне входження) і вставляємо нове значення.

C++

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;
    }
}

Python

from bisect import insort, bisect_left

# у кожній вершині — відсортований список (Python не має multiset;
# тримаємо список упорядкованим за допомогою bisect)
def update(v, tl, tr, pos, new_val):
    old = a[pos]
    # видаляємо одне входження старого значення
    i = bisect_left(t[v], old)
    t[v].pop(i)
    # вставляємо нове значення, зберігаючи впорядкованість
    insort(t[v], new_val)
    if tl != tr:
        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

TypeScript

// у кожній вершині — відсортований масив (TS не має multiset;
// тримаємо масив упорядкованим)
function update(v: number, tl: number, tr: number, pos: number, newVal: number): void {
  const old = a[pos];
  // видаляємо одне входження старого значення
  const idx = lowerBound(t[v], old);
  t[v].splice(idx, 1);
  // вставляємо нове значення, зберігаючи впорядкованість
  const ins = lowerBound(t[v], newVal);
  t[v].splice(ins, 0, newVal);
  if (tl !== tr) {
    const tm = (tl + tr) >> 1;
    if (pos <= tm) update(v * 2, tl, tm, pos, newVal);
    else update(v * 2 + 1, tm + 1, tr, pos, newVal);
  } else {
    a[pos] = newVal;
  }
}

Go

// у кожній вершині — відсортований слайс (у Go немає multiset;
// тримаємо слайс упорядкованим)
func update(v, tl, tr, pos, newVal int) {
    old := a[pos]
    // видаляємо одне входження старого значення
    i := sort.SearchInts(t[v], old)
    t[v] = append(t[v][:i], t[v][i+1:]...)
    // вставляємо нове значення, зберігаючи впорядкованість
    j := sort.SearchInts(t[v], newVal)
    t[v] = append(t[v], 0)
    copy(t[v][j+1:], t[v][j:])
    t[v][j] = newVal
    if tl != tr {
        tm := (tl + tr) / 2
        if pos <= tm {
            update(v*2, tl, tm, pos, newVal)
        } else {
            update(v*2+1, tm+1, tr, pos, newVal)
        }
    } else {
        a[pos] = newVal
    }
}

Обробка цього запиту модифікації також займає $O(\log^2 n)$ часу.

Знайти найменше число, більше або рівне заданому. Прискорення за допомогою «дробового каскадування».

Маємо те саме формулювання задачі: ми хочемо знайти мінімальне число, більше або рівне $x$, у відрізку, але цього разу за час $O(\log n)$. Ми покращимо часову складність за допомогою техніки «дробового каскадування» (fractional cascading).

Дробове каскадування — це проста техніка, яка дозволяє покращити час роботи кількох бінарних пошуків, що проводяться одночасно. Наш попередній підхід до пошукового запиту полягав у тому, що ми розбиваємо задачу на кілька підзадач, кожна з яких розв'язується бінарним пошуком. Дробове каскадування дозволяє замінити всі ці бінарні пошуки одним.

Найпростіший і найочевидніший приклад дробового каскадування — це така задача: є $k$ відсортованих списків чисел, і ми маємо знайти в кожному списку перше число, більше або рівне заданому числу.

Замість того щоб виконувати бінарний пошук для кожного списку, ми могли б злити всі списки в один великий відсортований список. Додатково для кожного елемента $y$ ми зберігаємо список результатів пошуку $y$ в кожному з $k$ списків. Тому якщо ми хочемо знайти найменше число, більше або рівне $x$, нам потрібно лише виконати один єдиний бінарний пошук, і зі списку індексів ми можемо визначити найменше число в кожному списку. Однак цей підхід потребує $O(n \cdot k)$ ($n$ — довжина об'єднаних списків), що може бути доволі неефективно.

Дробове каскадування зменшує цю складність за пам'яттю до $O(n)$, створюючи з $k$ вхідних списків $k$ нових списків, у яких кожен список містить відповідний список і додатково ще кожен другий елемент наступного нового списку. За допомогою цієї структури достатньо зберігати лише два індекси: індекс елемента в початковому списку та індекс елемента в наступному новому списку. Тож цей підхід використовує лише $O(n)$ пам'яті й усе одно може відповідати на запити за допомогою одного бінарного пошуку.

Але для нашого застосування нам не потрібна вся потуга дробового каскадування. У нашому дереві відрізків вершина міститиме відсортований список усіх елементів, що зустрічаються або в лівому, або в правому піддереві (як у дереві злиття). Додатково до цього відсортованого списку ми зберігаємо дві позиції для кожного елемента. Для елемента $y$ ми зберігаємо найменший індекс $i$ такий, що $i$-й елемент у відсортованому списку лівої дитини більший або рівний $y$. І ми зберігаємо найменший індекс $j$ такий, що $j$-й елемент у відсортованому списку правої дитини більший або рівний $y$. Ці значення можна обчислити паралельно з кроком злиття, коли ми будуємо дерево.

Як це прискорює запити?

Пам'ятаймо, що у звичайному розв'язку ми робили бінарний пошук у кожному вузлі. Але з цією модифікацією ми можемо уникнути всіх, окрім одного.

Щоб відповісти на запит, ми просто робимо бінарний пошук у кореневому вузлі. Це дає нам найменший елемент $y \ge x$ у всьому масиві, але також дає нам дві позиції. Індекс найменшого елемента, більшого або рівного $x$, у лівому піддереві та індекс найменшого елемента $y$ у правому піддереві. Зауважте, що $\ge y$ — це те саме, що $\ge x$, оскільки наш масив не містить жодних елементів між $x$ та $y$. У звичайному розв'язку з деревом злиття ми б обчислювали ці індекси бінарним пошуком, але за допомогою попередньо обчислених значень ми можемо просто подивитися їх за $O(1)$. І ми можемо повторювати це, доки не відвідаємо всі вузли, що покривають наш інтервал запиту.

Підсумовуючи: як завжди, під час запиту ми торкаємося $O(\log n)$ вузлів. У кореневому вузлі ми робимо бінарний пошук, а в усіх інших вузлах ми виконуємо лише сталу роботу. Це означає, що складність відповіді на запит становить $O(\log n)$.

Але зауважте, що це використовує втричі більше пам'яті, ніж звичайне дерево злиття, яке вже використовує багато пам'яті ($O(n \log n)$).

Цю техніку прямолінійно застосувати до задачі, яка не потребує жодних запитів модифікації. Дві позиції — це просто цілі числа, і їх легко обчислити підрахунком під час злиття двох відсортованих послідовностей.

Усе ще можливо також допустити запити модифікації, але це ускладнює весь код. Замість цілих чисел вам потрібно зберігати відсортований масив як multiset, а замість індексів вам потрібно зберігати ітератори. І вам потрібно працювати дуже обережно, щоб збільшувати чи зменшувати правильні ітератори під час запиту модифікації.

Інші можливі варіації

Ця техніка передбачає цілий новий клас можливих застосувань. Замість зберігання $\text{vector}$ або $\text{multiset}$ у кожній вершині можна використовувати інші структури даних: інші дерева відрізків (дещо обговорено в розділі Узагальнення на вищі розмірності), дерева Фенвіка, декартові дерева тощо.

Оновлення на відрізках (відкладені оновлення)

Усі задачі в наведених вище розділах обговорювали запити модифікації, кожен з яких зачіпав лише один елемент масиву. Однак дерево відрізків дозволяє застосовувати запити модифікації до цілого відрізка суміжних елементів і виконувати запит за той самий час $O(\log n)$.

Додавання на відрізках

Почнемо з розгляду задач найпростішої форми: запит модифікації має додавати число $x$ до всіх чисел у відрізку $a[l \dots r]$. Другий запит, на який ми маємо відповідати, просто запитує значення $a[i]$.

Щоб зробити запит додавання ефективним, ми зберігаємо в кожній вершині дерева відрізків, скільки нам слід додати до всіх чисел у відповідному відрізку. Наприклад, якщо надходить запит «додати 3 до всього масиву $a[0 \dots n-1]$», то ми ставимо число 3 в корінь дерева. Узагалі нам доводиться ставити це число в кілька відрізків, які утворюють розбиття відрізка запиту. Отже, нам не потрібно змінювати всі $O(n)$ значень, а лише $O(\log n)$ з них.

Якщо тепер надходить запит, який просить поточне значення певного елемента масиву, достатньо спуститися деревом і додати всі значення, знайдені на шляху.

C++

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);
}

Python

def build(a, v, tl, tr):
    if tl == tr:
        t[v] = a[tl]
    else:
        tm = (tl + tr) // 2
        build(a, v * 2, tl, tm)
        build(a, v * 2 + 1, tm + 1, tr)
        t[v] = 0

def update(v, tl, tr, l, r, add):
    if l > r:
        return
    if l == tl and r == tr:
        t[v] += add
    else:
        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)

def get(v, tl, tr, pos):
    if tl == tr:
        return t[v]
    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)

TypeScript

function build(a: number[], v: number, tl: number, tr: number): void {
  if (tl === tr) {
    t[v] = a[tl];
  } else {
    const tm = (tl + tr) >> 1;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    t[v] = 0;
  }
}

function update(v: number, tl: number, tr: number, l: number, r: number, add: number): void {
  if (l > r) return;
  if (l === tl && r === tr) {
    t[v] += add;
  } else {
    const tm = (tl + tr) >> 1;
    update(v * 2, tl, tm, l, Math.min(r, tm), add);
    update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, add);
  }
}

function get(v: number, tl: number, tr: number, pos: number): number {
  if (tl === tr) return t[v];
  const tm = (tl + tr) >> 1;
  if (pos <= tm) return t[v] + get(v * 2, tl, tm, pos);
  else return t[v] + get(v * 2 + 1, tm + 1, tr, pos);
}

Go

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

func update(v, tl, tr, l, r, add int) {
    if l > r {
        return
    }
    if l == tl && r == tr {
        t[v] += add
    } else {
        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)
    }
}

func get(v, tl, tr, pos int) int {
    if tl == tr {
        return t[v]
    }
    tm := (tl + tr) / 2
    if pos <= tm {
        return t[v] + get(v*2, tl, tm, pos)
    }
    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)$).

Для реалізації нам потрібно зробити функцію $\text{push}$, яка отримуватиме поточну вершину й проштовхуватиме інформацію цієї вершини в обидві її дитини. Ми викликатимемо цю функцію на початку функцій запитів (але не викликатимемо її з листя, бо немає потреби проштовхувати інформацію з них далі).

C++

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);
}

Python

# marked[v] = True означає, що весь відрізок присвоєно значенню t[v]
def push(v):
    if marked[v]:
        t[v * 2] = t[v * 2 + 1] = t[v]
        marked[v * 2] = marked[v * 2 + 1] = True
        marked[v] = False

def update(v, tl, tr, l, r, new_val):
    if l > r:
        return
    if l == tl and tr == r:
        t[v] = new_val
        marked[v] = True
    else:
        push(v)
        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)

def get(v, tl, tr, pos):
    if tl == tr:
        return t[v]
    push(v)
    tm = (tl + tr) // 2
    if pos <= tm:
        return get(v * 2, tl, tm, pos)
    else:
        return get(v * 2 + 1, tm + 1, tr, pos)

TypeScript

// marked[v] = true означає, що весь відрізок присвоєно значенню t[v]
function push(v: number): void {
  if (marked[v]) {
    t[v * 2] = t[v * 2 + 1] = t[v];
    marked[v * 2] = marked[v * 2 + 1] = true;
    marked[v] = false;
  }
}

function update(v: number, tl: number, tr: number, l: number, r: number, newVal: number): void {
  if (l > r) return;
  if (l === tl && tr === r) {
    t[v] = newVal;
    marked[v] = true;
  } else {
    push(v);
    const tm = (tl + tr) >> 1;
    update(v * 2, tl, tm, l, Math.min(r, tm), newVal);
    update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, newVal);
  }
}

function get(v: number, tl: number, tr: number, pos: number): number {
  if (tl === tr) return t[v];
  push(v);
  const tm = (tl + tr) >> 1;
  if (pos <= tm) return get(v * 2, tl, tm, pos);
  else return get(v * 2 + 1, tm + 1, tr, pos);
}

Go

// marked[v] = true означає, що весь відрізок присвоєно значенню t[v]
func push(v int) {
    if marked[v] {
        t[v*2], t[v*2+1] = t[v], t[v]
        marked[v*2], marked[v*2+1] = true, true
        marked[v] = false
    }
}

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

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

Зауваження: функцію $\text{get}$ можна також реалізувати в інший спосіб: не робити відкладених оновлень, а одразу повертати значення $t[v]$, якщо $marked[v]$ є істинним.

Додавання на відрізках, запит максимуму

Тепер запит модифікації полягає в додаванні числа до всіх елементів у діапазоні, а запит на читання — у знаходженні максимуму в діапазоні.

Отже, для кожної вершини дерева відрізків ми маємо зберігати максимум відповідного підвідрізка. Цікава частина — як перерахувати ці значення під час запиту модифікації.

Для цього ми зберігаємо додаткове значення для кожної вершини. У цьому значенні ми зберігаємо доданки, які ми ще не проштовхнули до дочірніх вершин. Перед переходом до дочірньої вершини ми викликаємо $\text{push}$ і проштовхуємо значення до обох дітей. Ми маємо робити це і у функції $\text{update}$, і у функції $\text{query}$.

C++

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));
}

Python

def build(a, v, tl, tr):
    if tl == tr:
        t[v] = a[tl]
    else:
        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])

def push(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

def update(v, tl, tr, l, r, addend):
    if l > r:
        return
    if l == tl and tr == r:
        t[v] += addend
        lazy[v] += addend
    else:
        push(v)
        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])

def query(v, tl, tr, l, r):
    if l > r:
        return -INF
    if l == tl and tr == r:
        return t[v]
    push(v)
    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))

TypeScript

function build(a: number[], v: number, tl: number, tr: number): void {
  if (tl === tr) {
    t[v] = a[tl];
  } else {
    const tm = (tl + tr) >> 1;
    build(a, v * 2, tl, tm);
    build(a, v * 2 + 1, tm + 1, tr);
    t[v] = Math.max(t[v * 2], t[v * 2 + 1]);
  }
}

function push(v: number): void {
  // проштовхуємо відкладений доданок до дітей
  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;
}

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

function query(v: number, tl: number, tr: number, l: number, r: number): number {
  if (l > r) return -INF;
  if (l === tl && tr === r) return t[v];
  push(v);
  const tm = (tl + tr) >> 1;
  return Math.max(
    query(v * 2, tl, tm, l, Math.min(r, tm)),
    query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r)
  );
}

Go

func build(a []int, v, tl, tr int) {
    if tl == tr {
        t[v] = a[tl]
    } else {
        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])
    }
}

func push(v int) {
    // проштовхуємо відкладений доданок до дітей
    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
}

func update(v, tl, tr, l, r, addend int) {
    if l > r {
        return
    }
    if l == tl && tr == r {
        t[v] += addend
        lazy[v] += addend
    } else {
        push(v)
        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])
    }
}

func query(v, tl, tr, l, r int) int {
    if l > r {
        return -INF
    }
    if l == tl && tr == r {
        return t[v]
    }
    push(v)
    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))
}

Узагальнення на вищі розмірності

Дерево відрізків доволі природно узагальнюється на вищі розмірності. Якщо в одновимірному випадку ми розбиваємо індекси масиву на відрізки, то у двовимірному ми робимо звичайне дерево відрізків відносно перших індексів, і для кожного відрізка будуємо звичайне дерево відрізків відносно других індексів.

Просте 2D-дерево відрізків

Задано матрицю $a[0 \dots n-1, 0 \dots m-1]$, і ми маємо знайти суму (або мінімум/максимум) на деякій підматриці $a[x_1 \dots x_2, y_1 \dots y_2]$, а також виконувати модифікації окремих елементів матриці (тобто запити виду $a[x][y] = p$).

Отже, ми будуємо 2D-дерево відрізків: спочатку дерево відрізків за першою координатою ($x$), потім за другою ($y$).

Щоб зробити процес побудови зрозумілішим, можна на якийсь час забути, що матриця двовимірна, і лишити тільки першу координату. Ми побудуємо звичайне одновимірне дерево відрізків лише за першою координатою. Але замість зберігання числа у відрізку ми зберігаємо ціле дерево відрізків: тобто в цей момент ми пам'ятаємо, що в нас є й друга координата; але оскільки в цей момент перша координата вже зафіксована на деякому інтервалі $[l \dots r]$, ми фактично працюємо з такою смугою $a[l \dots r, 0 \dots m-1]$ і для неї будуємо дерево відрізків.

Ось реалізація побудови 2D-дерева відрізків. Вона фактично складається з двох окремих блоків: побудови дерева відрізків уздовж координати $x$ ($\text{build}_x$) та координати $y$ ($\text{build}_y$). Для листових вузлів у $\text{build}_y$ нам треба розрізнити два випадки: коли поточний відрізок першої координати $[tlx \dots trx]$ має довжину 1 і коли він має довжину більшу за одиницю. У першому випадку ми просто беремо відповідне значення з матриці, а в другому випадку можемо поєднати значення двох дерев відрізків від лівого та правого сина за координатою $x$.

C++

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);
}

Python

def build_y(vx, lx, rx, vy, ly, 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:
        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]

def build_x(vx, lx, rx):
    if lx != rx:
        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)

TypeScript

function buildY(vx: number, lx: number, rx: number, vy: number, ly: number, ry: number): void {
  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 {
    const my = (ly + ry) >> 1;
    buildY(vx, lx, rx, vy * 2, ly, my);
    buildY(vx, lx, rx, vy * 2 + 1, my + 1, ry);
    t[vx][vy] = t[vx][vy * 2] + t[vx][vy * 2 + 1];
  }
}

function buildX(vx: number, lx: number, rx: number): void {
  if (lx !== rx) {
    const mx = (lx + rx) >> 1;
    buildX(vx * 2, lx, mx);
    buildX(vx * 2 + 1, mx + 1, rx);
  }
  buildY(vx, lx, rx, 1, 0, m - 1);
}

Go

func buildY(vx, lx, rx, vy, ly, ry int) {
    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 {
        my := (ly + ry) / 2
        buildY(vx, lx, rx, vy*2, ly, my)
        buildY(vx, lx, rx, vy*2+1, my+1, ry)
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]
    }
}

func buildX(vx, lx, rx int) {
    if lx != rx {
        mx := (lx + rx) / 2
        buildX(vx*2, lx, mx)
        buildX(vx*2+1, mx+1, rx)
    }
    buildY(vx, lx, rx, 1, 0, m-1)
}

Таке дерево відрізків усе ще використовує лінійну кількість пам'яті, але з більшою сталою: $16 n m$. Зрозуміло, що описана процедура $\text{build}_x$ також працює за лінійний час.

Тепер перейдемо до обробки запитів. Ми відповідатимемо на двовимірний запит за тим самим принципом: спочатку розбиваємо запит за першою координатою, а потім для кожної досягнутої вершини викликаємо відповідне дерево відрізків другої координати.

C++

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);
}

Python

def sum_y(vx, vy, tly, t_ry, ly, ry):
    if ly > ry:
        return 0
    if ly == tly and t_ry == ry:
        return t[vx][vy]
    tmy = (tly + t_ry) // 2
    return (sum_y(vx, vy * 2, tly, tmy, ly, min(ry, tmy))
            + sum_y(vx, vy * 2 + 1, tmy + 1, t_ry, max(ly, tmy + 1), ry))

def sum_x(vx, tlx, trx, lx, rx, ly, ry):
    if lx > rx:
        return 0
    if lx == tlx and trx == rx:
        return sum_y(vx, 1, 0, m - 1, ly, ry)
    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))

TypeScript

function sumY(vx: number, vy: number, tly: number, tryy: number, ly: number, ry: number): number {
  if (ly > ry) return 0;
  if (ly === tly && tryy === ry) return t[vx][vy];
  const tmy = (tly + tryy) >> 1;
  return (
    sumY(vx, vy * 2, tly, tmy, ly, Math.min(ry, tmy)) +
    sumY(vx, vy * 2 + 1, tmy + 1, tryy, Math.max(ly, tmy + 1), ry)
  );
}

function sumX(vx: number, tlx: number, trx: number, lx: number, rx: number, ly: number, ry: number): number {
  if (lx > rx) return 0;
  if (lx === tlx && trx === rx) return sumY(vx, 1, 0, m - 1, ly, ry);
  const tmx = (tlx + trx) >> 1;
  return (
    sumX(vx * 2, tlx, tmx, lx, Math.min(rx, tmx), ly, ry) +
    sumX(vx * 2 + 1, tmx + 1, trx, Math.max(lx, tmx + 1), rx, ly, ry)
  );
}

Go

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

func sumX(vx, tlx, trx, lx, rx, ly, ry int) int {
    if lx > rx {
        return 0
    }
    if lx == tlx && trx == rx {
        return sumY(vx, 1, 0, m-1, ly, ry)
    }
    tmx := (tlx + trx) / 2
    return sumX(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry) +
        sumX(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)$). Тому реалізація не дуже відрізнятиметься від одновимірного випадку, тільки тепер ми спочатку спускаємося за першою координатою, а потім за другою.

C++

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);
}

Python

def update_y(vx, lx, rx, vy, ly, ry, x, y, 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:
        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]

def update_x(vx, lx, rx, x, y, new_val):
    if lx != rx:
        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)

TypeScript

function updateY(vx: number, lx: number, rx: number, vy: number, ly: number, ry: number, x: number, y: number, newVal: number): void {
  if (ly === ry) {
    if (lx === rx) t[vx][vy] = newVal;
    else t[vx][vy] = t[vx * 2][vy] + t[vx * 2 + 1][vy];
  } else {
    const my = (ly + ry) >> 1;
    if (y <= my) updateY(vx, lx, rx, vy * 2, ly, my, x, y, newVal);
    else updateY(vx, lx, rx, vy * 2 + 1, my + 1, ry, x, y, newVal);
    t[vx][vy] = t[vx][vy * 2] + t[vx][vy * 2 + 1];
  }
}

function updateX(vx: number, lx: number, rx: number, x: number, y: number, newVal: number): void {
  if (lx !== rx) {
    const mx = (lx + rx) >> 1;
    if (x <= mx) updateX(vx * 2, lx, mx, x, y, newVal);
    else updateX(vx * 2 + 1, mx + 1, rx, x, y, newVal);
  }
  updateY(vx, lx, rx, 1, 0, m - 1, x, y, newVal);
}

Go

func updateY(vx, lx, rx, vy, ly, ry, x, y, newVal int) {
    if ly == ry {
        if lx == rx {
            t[vx][vy] = newVal
        } else {
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy]
        }
    } else {
        my := (ly + ry) / 2
        if y <= my {
            updateY(vx, lx, rx, vy*2, ly, my, x, y, newVal)
        } else {
            updateY(vx, lx, rx, vy*2+1, my+1, ry, x, y, newVal)
        }
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]
    }
}

func updateX(vx, lx, rx, x, y, newVal int) {
    if lx != rx {
        mx := (lx + rx) / 2
        if x <= mx {
            updateX(vx*2, lx, mx, x, y, newVal)
        } else {
            updateX(vx*2+1, mx+1, rx, x, y, newVal)
        }
    }
    updateY(vx, lx, rx, 1, 0, m-1, x, y, newVal)
}

Стиснення 2D-дерева відрізків

Нехай задача така: на площині задано $n$ точок своїми координатами $(x_i, y_i)$ та запити виду «підрахувати кількість точок, що лежать у прямокутнику $((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)$, нам просто треба зробити бінарний пошук за другою координатою, але це не погіршить складність.

Але запити модифікації будуть неможливі з цією структурою: адже якщо з'являється нова точка, нам доводиться додавати новий елемент у середину деякого дерева відрізків уздовж другої координати, що не можна зробити ефективно.

На завершення зауважимо, що двовимірне дерево відрізків, стиснуте в описаний спосіб, стає практично еквівалентним модифікації одновимірного дерева відрізків (див. Зберігання цілих підмасивів у кожній вершині). Зокрема, двовимірне дерево відрізків — це лише окремий випадок зберігання підмасиву в кожній вершині дерева. Звідси випливає, що якщо вам довелося відмовитися від двовимірного дерева відрізків через неможливість виконання запиту, є сенс спробувати замінити вкладене дерево відрізків якоюсь потужнішою структурою даних, наприклад декартовим деревом.

Збереження історії своїх значень (персистентне дерево відрізків)

Персистентна структура даних — це структура даних, яка пам'ятає свій попередній стан для кожної модифікації. Це дозволяє звертатися до будь-якої версії цієї структури даних, що нас цікавить, і виконувати на ній запит.

Дерево відрізків — це структура даних, яку можна ефективно (як за часом, так і за споживанням пам'яті) перетворити на персистентну структуру даних. Ми хочемо уникнути копіювання всього дерева перед кожною модифікацією, і ми не хочемо втрачати поведінку $O(\log n)$ для відповіді на запити на відрізку.

Насправді будь-який запит зміни в дереві відрізків призводить до зміни даних лише $O(\log n)$ вершин уздовж шляху, що починається від кореня. Тож якщо ми зберігаємо дерево відрізків за допомогою вказівників (тобто вершина зберігає вказівники на ліву та праву дочірні вершини), то, виконуючи запит модифікації, нам просто треба створювати нові вершини замість зміни наявних вершин. Вершини, яких запит модифікації не зачіпає, усе ще можна використовувати, спрямувавши вказівники на старі вершини. Таким чином, для запиту модифікації буде створено $O(\log n)$ нових вершин, зокрема нову кореневу вершину дерева відрізків, а вся попередня версія дерева з коренем у старій кореневій вершині лишиться незмінною.

Наведімо приклад реалізації для найпростішого дерева відрізків: коли є лише запит, що просить суми, та запити модифікації окремих елементів.

C++

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));
}

Python

class Vertex:
    # персистентна вершина: посилається на дітей, не змінюється після створення
    __slots__ = ("l", "r", "sum")

    def __init__(self, l=None, r=None, val=None):
        if val is not None:  # листова вершина
            self.l = self.r = None
            self.sum = val
        else:                # внутрішня вершина — сума дітей
            self.l = l
            self.r = r
            self.sum = (l.sum if l else 0) + (r.sum if r else 0)

def build(a, tl, tr):
    if tl == tr:
        return Vertex(val=a[tl])
    tm = (tl + tr) // 2
    return Vertex(build(a, tl, tm), build(a, tm + 1, tr))

def get_sum(v, tl, tr, l, r):
    if l > r:
        return 0
    if l == tl and tr == r:
        return v.sum
    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))

def update(v, tl, tr, pos, new_val):
    if tl == tr:
        return Vertex(val=new_val)
    tm = (tl + tr) // 2
    if pos <= tm:
        return Vertex(update(v.l, tl, tm, pos, new_val), v.r)
    else:
        return Vertex(v.l, update(v.r, tm + 1, tr, pos, new_val))

TypeScript

// персистентна вершина: посилається на дітей, не змінюється після створення
class Vertex {
  l: Vertex | null;
  r: Vertex | null;
  sum: number;

  constructor(arg: number | Vertex | null, r?: Vertex | null) {
    if (r === undefined) {
      // листова вершина зі значенням
      this.l = null;
      this.r = null;
      this.sum = arg as number;
    } else {
      // внутрішня вершина — сума дітей
      this.l = arg as Vertex | null;
      this.r = r;
      this.sum = (this.l ? this.l.sum : 0) + (this.r ? this.r.sum : 0);
    }
  }
}

function build(a: number[], tl: number, tr: number): Vertex {
  if (tl === tr) return new Vertex(a[tl]);
  const tm = (tl + tr) >> 1;
  return new Vertex(build(a, tl, tm), build(a, tm + 1, tr));
}

function getSum(v: Vertex, tl: number, tr: number, l: number, r: number): number {
  if (l > r) return 0;
  if (l === tl && tr === r) return v.sum;
  const tm = (tl + tr) >> 1;
  return (
    getSum(v.l!, tl, tm, l, Math.min(r, tm)) +
    getSum(v.r!, tm + 1, tr, Math.max(l, tm + 1), r)
  );
}

function update(v: Vertex, tl: number, tr: number, pos: number, newVal: number): Vertex {
  if (tl === tr) return new Vertex(newVal);
  const tm = (tl + tr) >> 1;
  if (pos <= tm) return new Vertex(update(v.l!, tl, tm, pos, newVal), v.r);
  else return new Vertex(v.l, update(v.r!, tm + 1, tr, pos, newVal));
}

Go

// персистентна вершина: посилається на дітей, не змінюється після створення
type Vertex struct {
    l, r *Vertex
    sum  int
}

func newLeaf(val int) *Vertex {
    return &Vertex{sum: val}
}

func newNode(l, r *Vertex) *Vertex {
    s := 0
    if l != nil {
        s += l.sum
    }
    if r != nil {
        s += r.sum
    }
    return &Vertex{l: l, r: r, sum: s}
}

func build(a []int, tl, tr int) *Vertex {
    if tl == tr {
        return newLeaf(a[tl])
    }
    tm := (tl + tr) / 2
    return newNode(build(a, tl, tm), build(a, tm+1, tr))
}

func getSum(v *Vertex, tl, tr, l, r int) int {
    if l > r {
        return 0
    }
    if l == tl && tr == r {
        return v.sum
    }
    tm := (tl + tr) / 2
    return getSum(v.l, tl, tm, l, min(r, tm)) +
        getSum(v.r, tm+1, tr, max(l, tm+1), r)
}

func update(v *Vertex, tl, tr, pos, newVal int) *Vertex {
    if tl == tr {
        return newLeaf(newVal)
    }
    tm := (tl + tr) / 2
    if pos <= tm {
        return newNode(update(v.l, tl, tm, pos, newVal), v.r)
    }
    return newNode(v.l, update(v.r, tm+1, tr, pos, newVal))
}

Для кожної модифікації дерева відрізків ми отримуватимемо нову кореневу вершину. Щоб швидко переходити між двома різними версіями дерева відрізків, нам потрібно зберігати ці корені в масиві. Щоб скористатися конкретною версією дерева відрізків, ми просто викликаємо запит із відповідною кореневою вершиною.

З описаним вище підходом майже будь-яке дерево відрізків можна перетворити на персистентну структуру даних.

Знаходження $k$-го за величиною найменшого числа в діапазоні

Цього разу ми маємо відповідати на запити виду «Яким є $k$-й за величиною найменший елемент у діапазоні $a[l \dots r]$». На цей запит можна відповісти за допомогою бінарного пошуку та дерева злиття, але часова складність одного запиту була б $O(\log^3 n)$. Ми виконаємо те саме завдання за допомогою персистентного дерева відрізків за $O(\log n)$.

Спочатку обговорімо розв'язок простішої задачі: ми розглядатимемо лише масиви, у яких елементи обмежені умовою $0 \le a[i] \lt n$. І ми хочемо знайти лише $k$-й за величиною найменший елемент у деякому префіксі масиву $a$. Розвинуті ідеї буде дуже легко поширити пізніше на необмежені масиви та необмежені запити на діапазоні. Зауважте, що для $a$ ми використовуватимемо індексацію з 1.

Ми використаємо дерево відрізків, яке підраховує всі числа, що з'являються, тобто в дереві відрізків ми зберігатимемо гістограму масиву. Отже, листові вершини зберігатимуть, як часто значення $0$, $1$, $\dots$, $n-1$ з'являються в масиві, а інші вершини зберігають, скільки чисел у деякому діапазоні є в масиві. Інакше кажучи, ми створюємо звичайне дерево відрізків із запитами суми над гістограмою масиву. Але замість створення всіх $n$ дерев відрізків для кожного можливого префікса ми створимо одне персистентне, яке міститиме ту саму інформацію. Ми почнемо з порожнього дерева відрізків (усі лічильники будуть $0$), на яке вказує $root_0$, і додаватимемо елементи $a[1]$, $a[2]$, $\dots$, $a[n]$ один за одним. Для кожної модифікації ми отримуватимемо нову кореневу вершину; назвемо $root_i$ коренем дерева відрізків після вставлення перших $i$ елементів масиву $a$. Дерево відрізків із коренем $root_i$ міститиме гістограму префікса $a[1 \dots i]$. За допомогою цього дерева відрізків ми можемо за час $O(\log n)$ знайти позицію $k$-го елемента, використовуючи ту саму техніку, що обговорювалася в розділі Підрахунок кількості нулів, пошук $k$-го нуля.

Тепер до необмеженої версії задачі.

Спочатку про обмеження на запити: замість виконання цих запитів лише над префіксом $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}$

C++

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);
}

Python

def build(tl, tr):
    if tl == tr:
        return Vertex(val=0)
    tm = (tl + tr) // 2
    return Vertex(build(tl, tm), build(tm + 1, tr))

def update(v, tl, tr, pos):
    if tl == tr:
        return Vertex(val=v.sum + 1)
    tm = (tl + tr) // 2
    if pos <= tm:
        return Vertex(update(v.l, tl, tm, pos), v.r)
    else:
        return Vertex(v.l, update(v.r, tm + 1, tr, pos))

def find_kth(vl, vr, tl, tr, k):
    if tl == tr:
        return tl
    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)

TypeScript

function build(tl: number, tr: number): Vertex {
  if (tl === tr) return new Vertex(0);
  const tm = (tl + tr) >> 1;
  return new Vertex(build(tl, tm), build(tm + 1, tr));
}

function update(v: Vertex, tl: number, tr: number, pos: number): Vertex {
  if (tl === tr) return new Vertex(v.sum + 1);
  const tm = (tl + tr) >> 1;
  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));
}

function findKth(vl: Vertex, vr: Vertex, tl: number, tr: number, k: number): number {
  if (tl === tr) return tl;
  const tm = (tl + tr) >> 1;
  // кількість елементів у лівій половині = різниця двох версій
  const leftCount = vr.l!.sum - vl.l!.sum;
  if (leftCount >= k) return findKth(vl.l!, vr.l!, tl, tm, k);
  return findKth(vl.r!, vr.r!, tm + 1, tr, k - leftCount);
}

Go

func build(tl, tr int) *Vertex {
    if tl == tr {
        return newLeaf(0)
    }
    tm := (tl + tr) / 2
    return newNode(build(tl, tm), build(tm+1, tr))
}

func update(v *Vertex, tl, tr, pos int) *Vertex {
    if tl == tr {
        return newLeaf(v.sum + 1)
    }
    tm := (tl + tr) / 2
    if pos <= tm {
        return newNode(update(v.l, tl, tm, pos), v.r)
    }
    return newNode(v.l, update(v.r, tm+1, tr, pos))
}

func findKth(vl, vr *Vertex, tl, tr, k int) int {
    if tl == tr {
        return tl
    }
    tm := (tl + tr) / 2
    // кількість елементів у лівій половині = різниця двох версій
    leftCount := vr.l.sum - vl.l.sum
    if leftCount >= k {
        return findKth(vl.l, vr.l, tl, tm, k)
    }
    return findKth(vl.r, vr.r, tm+1, tr, k-leftCount)
}

Як уже написано вище, нам потрібно зберігати корінь початкового дерева відрізків, а також усі корені після кожного оновлення. Ось код для побудови персистентного дерева відрізків над вектором a з елементами в діапазоні [0, MAX_VALUE].

C++

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]));
}

// знайти 5-те за величиною найменше число з підмасиву [a[2], a[3], ..., a[19]]
int result = find_kth(roots[2], roots[20], tl, tr, 5);

Python

tl, tr = 0, MAX_VALUE + 1
roots = [build(tl, tr)]
for i in range(len(a)):
    roots.append(update(roots[-1], tl, tr, a[i]))

# знайти 5-те за величиною найменше число з підмасиву [a[2], a[3], ..., a[19]]
result = find_kth(roots[2], roots[20], tl, tr, 5)

TypeScript

const tl = 0, tr = MAX_VALUE + 1;
const roots: Vertex[] = [build(tl, tr)];
for (let i = 0; i < a.length; i++) {
  roots.push(update(roots[roots.length - 1], tl, tr, a[i]));
}

// знайти 5-те за величиною найменше число з підмасиву [a[2], a[3], ..., a[19]]
const result = findKth(roots[2], roots[20], tl, tr, 5);

Go

tl, tr := 0, MAX_VALUE+1
roots := []*Vertex{build(tl, tr)}
for i := 0; i < len(a); i++ {
    roots = append(roots, update(roots[len(roots)-1], tl, tr, a[i]))
}

// знайти 5-те за величиною найменше число з підмасиву [a[2], a[3], ..., a[19]]
result := findKth(roots[2], roots[20], tl, tr, 5)

Тепер до обмежень на елементи масиву: ми фактично можемо перетворити будь-який масив на такий масив за допомогою стиснення індексів. Найменшому елементу в масиві буде присвоєне значення 0, другому за величиною найменшому — значення 1, і так далі. Легко згенерувати таблиці попередніх обчислень (наприклад, за допомогою $\text{map}$), які перетворюють значення на його індекс і навпаки за час $O(\log n)$.

Динамічне дерево відрізків

(Названо так, бо його форма динамічна, а вузли зазвичай виділяються динамічно. Також відоме як неявне дерево відрізків або розріджене дерево відрізків.)

Раніше ми розглядали випадки, коли в нас є можливість побудувати початкове дерево відрізків. Але що робити, якщо початковий розмір заповнений якимось значенням за замовчуванням, але його розмір не дозволяє заздалегідь повністю побудувати дерево до нього?

Ми можемо розв'язати цю задачу, створюючи дерево відрізків ліниво (поступово). Спочатку ми створимо лише корінь, а інші вершини створюватимемо лише тоді, коли вони нам знадобляться. У цьому випадку ми використаємо реалізацію на вказівниках (перед переходом до дітей вершини перевіряємо, чи вони створені, і якщо ні — створюємо їх). Кожен запит усе ще має лише складність $O(\log n)$, що досить мало для більшості випадків використання (наприклад, $\log_2 10^9 \approx 30$).

У цій реалізації в нас два запити: додавання значення до позиції (спочатку всі значення дорівнюють $0$) та обчислення суми всіх значень у діапазоні. Vertex(0, n) буде кореневою вершиною неявного дерева.

C++

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);
    }
};

Python

class Vertex:
    # вершини створюються ліниво, лише коли потрібні
    __slots__ = ("left", "right", "sum", "left_child", "right_child")

    def __init__(self, lb, rb):
        self.left = lb
        self.right = rb
        self.sum = 0
        self.left_child = None
        self.right_child = None

    def extend(self):
        if self.left_child is None and self.left + 1 < self.right:
            mid = (self.left + self.right) // 2
            self.left_child = Vertex(self.left, mid)
            self.right_child = Vertex(mid, self.right)

    def add(self, k, x):
        self.extend()
        self.sum += x
        if self.left_child is not None:
            if k < self.left_child.right:
                self.left_child.add(k, x)
            else:
                self.right_child.add(k, x)

    def get_sum(self, lq, rq):
        if lq <= self.left and self.right <= rq:
            return self.sum
        if max(self.left, lq) >= min(self.right, rq):
            return 0
        self.extend()
        return self.left_child.get_sum(lq, rq) + self.right_child.get_sum(lq, rq)

TypeScript

// вершини створюються ліниво, лише коли потрібні
class Vertex {
  left: number;
  right: number;
  sum = 0;
  leftChild: Vertex | null = null;
  rightChild: Vertex | null = null;

  constructor(lb: number, rb: number) {
    this.left = lb;
    this.right = rb;
  }

  extend(): void {
    if (this.leftChild === null && this.left + 1 < this.right) {
      const mid = (this.left + this.right) >> 1;
      this.leftChild = new Vertex(this.left, mid);
      this.rightChild = new Vertex(mid, this.right);
    }
  }

  add(k: number, x: number): void {
    this.extend();
    this.sum += x;
    if (this.leftChild !== null) {
      if (k < this.leftChild.right) this.leftChild.add(k, x);
      else this.rightChild!.add(k, x);
    }
  }

  getSum(lq: number, rq: number): number {
    if (lq <= this.left && this.right <= rq) return this.sum;
    if (Math.max(this.left, lq) >= Math.min(this.right, rq)) return 0;
    this.extend();
    return this.leftChild!.getSum(lq, rq) + this.rightChild!.getSum(lq, rq);
  }
}

Go

// вершини створюються ліниво, лише коли потрібні
type Vertex struct {
    left, right int
    sum         int
    leftChild   *Vertex
    rightChild  *Vertex
}

func NewVertex(lb, rb int) *Vertex {
    return &Vertex{left: lb, right: rb}
}

func (v *Vertex) extend() {
    if v.leftChild == nil && v.left+1 < v.right {
        mid := (v.left + v.right) / 2
        v.leftChild = NewVertex(v.left, mid)
        v.rightChild = NewVertex(mid, v.right)
    }
}

func (v *Vertex) add(k, x int) {
    v.extend()
    v.sum += x
    if v.leftChild != nil {
        if k < v.leftChild.right {
            v.leftChild.add(k, x)
        } else {
            v.rightChild.add(k, x)
        }
    }
}

func (v *Vertex) getSum(lq, rq int) int {
    if lq <= v.left && v.right <= rq {
        return v.sum
    }
    if max(v.left, lq) >= min(v.right, rq) {
        return 0
    }
    v.extend()
    return v.leftChild.getSum(lq, rq) + v.rightChild.getSum(lq, rq)
}

Очевидно, цю ідею можна розширити безліччю різних способів. Наприклад, додавши підтримку оновлень на відрізку за допомогою відкладених оновлень.

Задачі для практики

• SPOJ - KQUERY [Persistent segment tree / Merge sort tree]
• Codeforces - Xenia and Bit Operations
• UVA 11402 - Ahoy, Pirates!
• SPOJ - GSS3
• Codeforces - Distinct Characters Queries
• Codeforces - Knight Tournament [For beginners]
• Codeforces - Ant colony
• Codeforces - Drazil and Park
• Codeforces - Circular RMQ
• Codeforces - Lucky Array
• Codeforces - The Child and Sequence
• Codeforces - DZY Loves Fibonacci Numbers [Lazy propagation]
• Codeforces - Alphabet Permutations
• Codeforces - Eyes Closed
• Codeforces - Kefa and Watch
• Codeforces - A Simple Task
• Codeforces - SUM and REPLACE
• Codeforces - XOR on Segment [Lazy propagation]
• Codeforces - Please, another Queries on Array? [Lazy propagation]
• COCI - Deda [Last element smaller or equal to x / Binary search]
• Codeforces - The Untended Antiquity [2D]
• CSES - Hotel Queries
• CSES - Polynomial Queries
• CSES - Range Updates and Sums

Відеоматеріали