Дерево сегментів: Запити діапазону в O(log n)

Торгівля, яку проста масив не може здійснити

Враховуючи масив, дві операції діють у протилежних напрямках. Відповідь на питання «Яка сума (або мінімум) елементів від i до j?» становить O(1), якщо попередньо обчислені префіксні суми, але оновлення одного елемента коштує O(n), оскільки кожен префікс після нього стає неправильним. Не роблячи нічого заздалегідь, оновлення коштує O(1), а запит – O(n). Дерево сегментів відмовляється від цієї угоди: обидві операції коштують O(log n), зберігаючи не лише масив, але й агрегат кожного діапазону, який може бути створений збалансованим рекурсивним розбиттям.

Побудова дерева

Корінь охоплює весь масив [0, n). Кожен внутрішній вузол ділить свій діапазон навпіл і передає половини до своїх двох дітей; лист покриває один елемент. Оскільки дерево завжди розділяється рівномірно, його висота дорівнює ⌈log₂ n⌉, а кількість вузлів становить приблизно 2n − 1, зазвичай зберігаються в масиві розміром 4n для простої схеми індексування без покажчиків:

функція build(вузол, lo, hi) { якщо (lo === hi) { tree[вузол] = a[lo]; повертати; } const mid = (lo + hi) >> 1; build(2*вузол, lo, mid); build(2*вузол+1, mid+1, hi); tree[вузол] = combine(tree[2*вузол], tree[2*вузол+1]); // сума, мінімум, дріб...} Побудова відвідує кожен вузол один раз, тому конструювання займає O(n), незважаючи на те, що дерево виглядає рекурсивно дорогим на папері.

function build(node, lo, hi) {
  if (lo === hi) { tree[node] = a[lo]; return; }
  const mid = (lo + hi) >> 1;
  build(2*node, lo, mid);
  build(2*node+1, mid+1, hi);
  tree[node] = combine(tree[2*node], tree[2*node+1]);  // sum, min, gcd...
}

Відповідь на запит діапазону

Будь-який запит діапазону [l, r] може точно охоплюватися невеликою кількістю вже збережених у дереві діапазонів вузлів — його канонічне розкладання. Рекурсія запиту припиняється в момент, коли діапазон вузла повністю потрапляє всередину або повністю виходить за межі [l, r], і лише продовжується спуск далі, коли діапазони частково перекриваються:

функція query(node, lo, hi, l, r) { if (r < lo || hi < l) return IDENTITY; // відсутність перекриття if (l <= lo && hi <= r) return tree[node]; // повністю охоплено const mid = (lo + hi) >> 1; return combine(query(2*node, lo, mid, l, r), query(2*node+1, mid+1, hi, l, r)); } На кожному рівні дерева може частково перекриватися з запитом не більше двох вузлів — один містить лівий край, інший — правий — тому весь запит торкається всього O(log n) вузлів, незалежно від ширини діапазону.

function query(node, lo, hi, l, r) {
  if (r < lo || hi < l) return IDENTITY;       // no overlap
  if (l <= lo && hi <= r) return tree[node];    // fully covered
  const mid = (lo + hi) >> 1;
  return combine(query(2*node, lo, mid, l, r),
                 query(2*node+1, mid+1, hi, l, r));
}

Оновлення точки та ігнороване поширення для оновлень діапазону

Оновлення окремого елемента йде тим самим шляхом від кореня до листка, що використовувався при побудові дерева, змінює листок, а потім об'єднує кожного предка на шляху вгору — торкається O(log n) вузлів, точно відповідаючи вартості запиту. Оновлення всього діапазону одночасно (додати 5 до кожного елемента від i до j) перетворюється на O(n log n), якщо використовувати наївне оновлення по пунктах, і потрібна більш розумна техніка: ігнороване поширення. Вузол, діапазон якого повністю покритий оновленням, зберігає невиконаний ярлик замість негайного оновлення кожного нащадка; ярлик передається дітям лише тоді, коли запит або рекурсивне оновлення дійсно потребує перегляду цього вузла.

функція pushDown(вузол, lo, hi) { якщо !lazy[вузол] повертати; const mid = (lo + hi) >> 1; applyTag(2*вузол, lo, mid, lazy[вузол]); applyTag(2*вузол+1, mid+1, hi, lazy[вузол]); lazy[вузол] = 0; } З використанням ярликів ігнорування, як оновлення діапазону, так і запити діапазону залишаються O(log n), що робить дерева сегментів стандартним інструментом для задач, які змішують «додати x до всього в [l, r]» з «яка сума/мінімум в [l, r]» у тій же робочій навантаженість.

function pushDown(node, lo, hi) {
  if (!lazy[node]) return;
  const mid = (lo + hi) >> 1;
  applyTag(2*node, lo, mid, lazy[node]);
  applyTag(2*node+1, mid+1, hi, lazy[node]);
  lazy[node] = 0;
}

Дерево сегментів, дерево Фенвіка або розріджена таблиця?

Дерево Фенвіка (двійкове індексоване дерево) виконує аналогічні запити діапазону з сумою та оновлення в пункті за O(log n), але з набагато меншою кількістю коду та меншим константом. Воно працює чисто для обчислювальних операцій, таких як сума, де можна віднімати, щоб отримати будь-який діапазон із двох префіксів — воно не може безпосередньо підтримувати min або max. Розріджена таблиця відповідає на запити діапазону мінімум або діапазону найбільшого спільного дільника за O(1) після побудови за O(n log n), яка передбачає обчислення кожного діапазону, кратного степені двійки. Однак вона статична: вона використовує ідемпотентність (перекриття одного й того самого елемента двічі не порушує мінімум або НСД) і не має ефективного способу обробляти оновлення взагалі. Дерево сегментів є універсальним: будь-яка асоціативна функція комбінування з оновленнями за O(log n) з обох сторін — ціна за цю загальність полягає у додатковій структурі дерева, яку пропускають інші два.

Часті запитання

Спробуйте наживо

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