Segment Tree

Segment Tree (дерево отрезков) — структура данных на основе двоичного дерева, позволяющая выполнять запросы на отрезке массива (сумма, минимум, максимум) и точечные обновления за O(log n).

Зачем нужно

Когда нужно многократно запрашивать агрегат (сумму, min, max, НОД) по подмассиву и при этом изменять элементы, наивный подход даёт O(n) на запрос или O(n) на обновление. Segment Tree решает обе задачи за O(log n), что критично при n = 10^5–10^6 и большом числе запросов.

Где используется

  • Конкурентное программирование (CP): диапазонные запросы сумм/минимумов
  • Игровые движки: пространственные запросы по сегментам координат
  • Базы данных: индексы для агрегатных запросов по диапазонам
  • Статистика в реальном времени: скользящие агрегаты по временным окнам

Основной контент

Структура дерева

Массив из n элементов хранится в листьях дерева. Каждый внутренний узел хранит агрегат своих детей. Дерево хранится в массиве размером 4n.

Массив: [2, 4, 3, 1, 6, 7, 2, 5]
              Сумма[0..7] = 30
           /                  \
    Сумма[0..3]=10       Сумма[4..7]=20
     /        \            /         \
  [0..1]=6  [2..3]=4  [4..5]=13   [6..7]=7
  /    \    /    \    /     \     /     \
  2    4   3    1   6      7   2       5

Построение — O(n)

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 0, 0, this.n - 1);
  }

  build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = (start + end) >> 1;
      this.build(arr, 2*node+1, start, mid);
      this.build(arr, 2*node+2, mid+1, end);
      this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
    }
  }

  // Запрос суммы на [l, r] — O(log n)
  query(node, start, end, l, r) {
    if (r < start || end < l) return 0;          // нет пересечения
    if (l <= start && end <= r) return this.tree[node]; // полное покрытие
    const mid = (start + end) >> 1;
    return this.query(2*node+1, start, mid, l, r)
         + this.query(2*node+2, mid+1, end, l, r);
  }

  // Точечное обновление — O(log n)
  update(node, start, end, idx, val) {
    if (start === end) {
      this.tree[node] = val;
    } else {
      const mid = (start + end) >> 1;
      if (idx <= mid) this.update(2*node+1, start, mid, idx, val);
      else            this.update(2*node+2, mid+1, end, idx, val);
      this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
    }
  }
}

const st = new SegmentTree([2, 4, 3, 1, 6, 7, 2, 5]);
console.log(st.query(0, 0, 7, 1, 5)); // сумма [1..5] = 21
st.update(0, 0, 7, 3, 10);            // arr[3] = 10

Lazy Propagation — O(log n) для диапазонных обновлений

Если нужно прибавить значение к целому отрезку, «ленивое» распространение откладывает обновления узлов до момента обращения к ним.

Сложность

Операция Время Память
Построение O(n) O(n)
Запрос на отрезке O(log n) —
Точечное обновление O(log n) —
Диапазонное обновление (lazy) O(log n) O(n)

Частые ошибки

  • Выделять массив размером 2n вместо 4n — при n, не являющемся степенью двойки, это вызывает выход за границы.
  • Забывать базовый случай r < start || end < l в запросе — функция возвращает нейтральный элемент (0 для суммы, +∞ для min).
  • Не применять lazy propagation при диапазонных обновлениях — сложность деградирует до O(n log n).
  • Путать индексацию: дерево индексируется от 0, формулы детей: 2*node+1 и 2*node+2.

Связанные темы

Ресурсы