Дерево отрезков (Segment Tree): полное руководство с реализацией

Что такое дерево отрезков?

Дерево отрезков (Segment Tree) — это структура данных, позволяющая эффективно выполнять:

• Запросы на отрезке — сумма, минимум, максимум, НОД и другие ассоциативные операции
• Обновление элементов — изменение одного или нескольких элементов массива

Зачем нужно дерево отрезков?

*С ленивым распространением (lazy propagation)

Применение в спортивном программировании

• Задачи на сумму/минимум/максимум на отрезке
• Подсчёт элементов, удовлетворяющих условию
• Задачи с обновлениями на отрезках
• Сжатие координат + запросы

Принцип работы

Дерево отрезков — это полное бинарное дерево, где:

1. Листья — элементы исходного массива
2. Внутренние узлы — результат операции для отрезка детей

Визуализация

Для массива [1, 3, 5, 7, 9, 11]:

                    [36]              sum([0,5])
                   /    \
              [9]        [27]         sum([0,2]), sum([3,5])
             /   \       /   \
          [4]   [5]   [16]  [11]      sum([0,1]), [2], sum([3,4]), [5]
         /  \         /  \
       [1]  [3]     [7]  [9]          листья: элементы массива

Каждый узел хранит результат операции (здесь — сумму) для соответствующего отрезка.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Базовая реализация (сумма на отрезке)

JavaScript

class SegmentTree {
    constructor(arr) {
        this.n = arr.length;
        // Размер дерева: 4n достаточно для любого n
        this.tree = new Array(4 * this.n).fill(0);
        this.build(arr, 1, 0, this.n - 1);
    }

    // Построение дерева
    build(arr, node, start, end) {
        if (start === end) {
            // Листовой узел
            this.tree[node] = arr[start];
        } else {
            const mid = Math.floor((start + end) / 2);
            const leftChild = 2 * node;
            const rightChild = 2 * node + 1;

            // Рекурсивно строим левое и правое поддеревья
            this.build(arr, leftChild, start, mid);
            this.build(arr, rightChild, mid + 1, end);

            // Объединяем результаты детей
            this.tree[node] = this.tree[leftChild] + this.tree[rightChild];
        }
    }

    // Запрос суммы на отрезке [l, r]
    query(l, r, node = 1, start = 0, end = this.n - 1) {
        // Отрезок полностью вне запроса
        if (r < start || end < l) {
            return 0; // Нейтральный элемент для суммы
        }

        // Отрезок полностью внутри запроса
        if (l <= start && end <= r) {
            return this.tree[node];
        }

        // Частичное пересечение — спускаемся в детей
        const mid = Math.floor((start + end) / 2);
        const leftResult = this.query(l, r, 2 * node, start, mid);
        const rightResult = this.query(l, r, 2 * node + 1, mid + 1, end);

        return leftResult + rightResult;
    }

    // Обновление элемента arr[idx] = val
    update(idx, val, node = 1, start = 0, end = this.n - 1) {
        if (start === end) {
            // Дошли до листа
            this.tree[node] = val;
        } else {
            const mid = Math.floor((start + end) / 2);

            if (idx <= mid) {
                // Индекс в левом поддереве
                this.update(idx, val, 2 * node, start, mid);
            } else {
                // Индекс в правом поддереве
                this.update(idx, val, 2 * node + 1, mid + 1, end);
            }

            // Пересчитываем текущий узел
            this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
        }
    }
}

// Пример использования
const arr = [1, 3, 5, 7, 9, 11];
const st = new SegmentTree(arr);

console.log(st.query(1, 3)); // 15 (3 + 5 + 7)
st.update(2, 10);            // arr[2] = 10
console.log(st.query(1, 3)); // 20 (3 + 10 + 7)

Python

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)

    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            left_child = 2 * node
            right_child = 2 * node + 1

            self._build(arr, left_child, start, mid)
            self._build(arr, right_child, mid + 1, end)

            self.tree[node] = self.tree[left_child] + self.tree[right_child]

    def query(self, l, r, node=1, start=None, end=None):
        if start is None:
            start, end = 0, self.n - 1

        # Полностью вне отрезка
        if r < start or end < l:
            return 0

        # Полностью внутри отрезка
        if l <= start and end <= r:
            return self.tree[node]

        # Частичное пересечение
        mid = (start + end) // 2
        left_result = self.query(l, r, 2 * node, start, mid)
        right_result = self.query(l, r, 2 * node + 1, mid + 1, end)

        return left_result + right_result

    def update(self, idx, val, node=1, start=None, end=None):
        if start is None:
            start, end = 0, self.n - 1

        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2

            if idx <= mid:
                self.update(idx, val, 2 * node, start, mid)
            else:
                self.update(idx, val, 2 * node + 1, mid + 1, end)

            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]


# Пример использования
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)

print(st.query(1, 3))  # 15
st.update(2, 10)
print(st.query(1, 3))  # 20

Дерево отрезков для минимума/максимума

Изменения для минимума

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

    build(arr, node, start, end) {
        if (start === end) {
            this.tree[node] = arr[start];
        } else {
            const mid = Math.floor((start + end) / 2);
            this.build(arr, 2 * node, start, mid);
            this.build(arr, 2 * node + 1, mid + 1, end);
            // Изменение: min вместо +
            this.tree[node] = Math.min(
                this.tree[2 * node],
                this.tree[2 * node + 1]
            );
        }
    }

    query(l, r, node = 1, start = 0, end = this.n - 1) {
        if (r < start || end < l) {
            return Infinity; // Нейтральный элемент для min
        }
        if (l <= start && end <= r) {
            return this.tree[node];
        }

        const mid = Math.floor((start + end) / 2);
        return Math.min(
            this.query(l, r, 2 * node, start, mid),
            this.query(l, r, 2 * node + 1, mid + 1, end)
        );
    }

    update(idx, val, node = 1, start = 0, end = this.n - 1) {
        if (start === end) {
            this.tree[node] = val;
        } else {
            const mid = Math.floor((start + end) / 2);

            if (idx <= mid) {
                this.update(idx, val, 2 * node, start, mid);
            } else {
                this.update(idx, val, 2 * node + 1, mid + 1, end);
            }

            this.tree[node] = Math.min(
                this.tree[2 * node],
                this.tree[2 * node + 1]
            );
        }
    }
}

Таблица нейтральных элементов

Ленивое распространение (Lazy Propagation)

Ленивое распространение позволяет обновлять целые отрезки за O(log n).

Идея

Вместо немедленного обновления всех элементов:

1. Помечаем узел как "требующий обновления"
2. Откладываем обновление до момента, когда оно действительно нужно
3. При спуске к детям "проталкиваем" отложенное обновление

Реализация: прибавление на отрезке

class LazySegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(4 * this.n).fill(0);
        this.lazy = new Array(4 * this.n).fill(0); // Отложенные обновления
        this.build(arr, 1, 0, this.n - 1);
    }

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

    // Проталкивание отложенных обновлений к детям
    pushDown(node, start, end) {
        if (this.lazy[node] !== 0) {
            const mid = Math.floor((start + end) / 2);
            const leftChild = 2 * node;
            const rightChild = 2 * node + 1;

            // Обновляем значения детей
            this.tree[leftChild] += this.lazy[node] * (mid - start + 1);
            this.tree[rightChild] += this.lazy[node] * (end - mid);

            // Передаём отложенное обновление детям
            this.lazy[leftChild] += this.lazy[node];
            this.lazy[rightChild] += this.lazy[node];

            // Сбрасываем отложенное обновление текущего узла
            this.lazy[node] = 0;
        }
    }

    // Прибавить val ко всем элементам на отрезке [l, r]
    rangeUpdate(l, r, val, node = 1, start = 0, end = this.n - 1) {
        if (r < start || end < l) {
            return; // Вне отрезка
        }

        if (l <= start && end <= r) {
            // Полностью внутри — применяем обновление
            this.tree[node] += val * (end - start + 1);
            this.lazy[node] += val;
            return;
        }

        // Частичное пересечение — спускаемся
        this.pushDown(node, start, end);

        const mid = Math.floor((start + end) / 2);
        this.rangeUpdate(l, r, val, 2 * node, start, mid);
        this.rangeUpdate(l, r, val, 2 * node + 1, mid + 1, end);

        this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
    }

    query(l, r, node = 1, start = 0, end = this.n - 1) {
        if (r < start || end < l) {
            return 0;
        }

        if (l <= start && end <= r) {
            return this.tree[node];
        }

        // Проталкиваем перед спуском!
        this.pushDown(node, start, end);

        const mid = Math.floor((start + end) / 2);
        return (
            this.query(l, r, 2 * node, start, mid) +
            this.query(l, r, 2 * node + 1, mid + 1, end)
        );
    }
}

// Пример
const arr = [1, 2, 3, 4, 5];
const lst = new LazySegmentTree(arr);

console.log(lst.query(0, 4)); // 15
lst.rangeUpdate(1, 3, 10);    // Прибавить 10 к arr[1..3]
console.log(lst.query(0, 4)); // 45 (1 + 12 + 13 + 14 + 5)
console.log(lst.query(1, 2)); // 25 (12 + 13)

Python версия с lazy propagation

class LazySegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)

    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self._build(arr, 2 * node, start, mid)
            self._build(arr, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def _push_down(self, node, start, end):
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            left, right = 2 * node, 2 * node + 1

            self.tree[left] += self.lazy[node] * (mid - start + 1)
            self.tree[right] += self.lazy[node] * (end - mid)

            self.lazy[left] += self.lazy[node]
            self.lazy[right] += self.lazy[node]

            self.lazy[node] = 0

    def range_update(self, l, r, val, node=1, start=None, end=None):
        if start is None:
            start, end = 0, self.n - 1

        if r < start or end < l:
            return

        if l <= start and end <= r:
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] += val
            return

        self._push_down(node, start, end)

        mid = (start + end) // 2
        self.range_update(l, r, val, 2 * node, start, mid)
        self.range_update(l, r, val, 2 * node + 1, mid + 1, end)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, l, r, node=1, start=None, end=None):
        if start is None:
            start, end = 0, self.n - 1

        if r < start or end < l:
            return 0

        if l <= start and end <= r:
            return self.tree[node]

        self._push_down(node, start, end)

        mid = (start + end) // 2
        return (
            self.query(l, r, 2 * node, start, mid) +
            self.query(l, r, 2 * node + 1, mid + 1, end)
        )

Итеративная реализация (без рекурсии)

Для более быстрой работы (без накладных расходов на рекурсию):

class IterativeSegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(2 * this.n).fill(0);

        // Копируем элементы в листья
        for (let i = 0; i < this.n; i++) {
            this.tree[this.n + i] = arr[i];
        }

        // Строим дерево снизу вверх
        for (let i = this.n - 1; i > 0; i--) {
            this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
        }
    }

    update(idx, val) {
        // Обновляем лист
        idx += this.n;
        this.tree[idx] = val;

        // Поднимаемся вверх, обновляя родителей
        while (idx > 1) {
            idx = Math.floor(idx / 2);
            this.tree[idx] = this.tree[2 * idx] + this.tree[2 * idx + 1];
        }
    }

    query(l, r) {
        let result = 0;
        l += this.n;
        r += this.n + 1; // r включительно

        while (l < r) {
            if (l % 2 === 1) {
                result += this.tree[l];
                l++;
            }
            if (r % 2 === 1) {
                r--;
                result += this.tree[r];
            }
            l = Math.floor(l / 2);
            r = Math.floor(r / 2);
        }

        return result;
    }
}

Сравнение реализаций

Итеративная версия быстрее на практике из-за отсутствия рекурсии.

Типичные задачи

Задача 1: Range Sum Query - Mutable (LeetCode 307)

class NumArray {
    constructor(nums) {
        this.st = new SegmentTree(nums);
    }

    update(index, val) {
        this.st.update(index, val);
    }

    sumRange(left, right) {
        return this.st.query(left, right);
    }
}

Задача 2: Количество инверсий

Подсчёт пар (i, j) где i < j и arr[i] > arr[j]:

def count_inversions(arr):
    # Сжатие координат
    sorted_arr = sorted(set(arr))
    rank = {v: i for i, v in enumerate(sorted_arr)}
    n = len(sorted_arr)

    # Дерево отрезков для подсчёта
    tree = [0] * (4 * n)

    def update(node, start, end, idx):
        if start == end:
            tree[node] += 1
        else:
            mid = (start + end) // 2
            if idx <= mid:
                update(2 * node, start, mid, idx)
            else:
                update(2 * node + 1, mid + 1, end, idx)
            tree[node] = tree[2 * node] + tree[2 * node + 1]

    def query(node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return tree[node]
        mid = (start + end) // 2
        return query(2 * node, start, mid, l, r) + \
               query(2 * node + 1, mid + 1, end, l, r)

    inversions = 0
    for x in arr:
        r = rank[x]
        # Сколько чисел > x уже добавлено?
        inversions += query(1, 0, n - 1, r + 1, n - 1)
        update(1, 0, n - 1, r)

    return inversions

Задача 3: K-й элемент в отсортированном порядке

function kthElement(st, k, node = 1, start = 0, end = st.n - 1) {
    if (start === end) {
        return start;
    }

    const mid = Math.floor((start + end) / 2);
    const leftCount = st.tree[2 * node];

    if (k <= leftCount) {
        return kthElement(st, k, 2 * node, start, mid);
    } else {
        return kthElement(st, k - leftCount, 2 * node + 1, mid + 1, end);
    }
}

Оптимизации и советы

1. Размер массива

Для безопасности выделяйте 4 * n элементов. Точный размер: 2 * nextPowerOf2(n).

2. Индексация

• node * 2 и node * 2 + 1 для детей
• Или node << 1 и (node << 1) | 1 для скорости

3. Избегайте лишних вычислений

// Вместо
const mid = Math.floor((start + end) / 2);

// Используйте
const mid = (start + end) >> 1;

4. Персистентное дерево отрезков

Для сохранения всех версий дерева (полезно для задач с откатами).

Анализ сложности

Когда использовать дерево отрезков?

Используйте, когда:

• Много запросов на отрезках
• Нужны обновления элементов
• Операция ассоциативна (сумма, min, max, gcd...)

Не используйте, когда:

• Только запросы без обновлений → префиксные суммы O(1)
• Нужны медианы → другие структуры
• Массив слишком большой и разреженный → неявное дерево отрезков

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

1. Range Sum Query - Mutable (LeetCode 307) — базовое дерево отрезков
2. Range Minimum Query — замена суммы на минимум
3. Count of Smaller Numbers After Self (LeetCode 315) — подсчёт инверсий
4. Falling Squares (LeetCode 699) — lazy propagation
5. Count of Range Sum (LeetCode 327) — сложное применение

Заключение

Дерево отрезков — одна из важнейших структур данных в спортивном программировании:

• O(log n) на запросы и обновления
• Универсальность — работает с любой ассоциативной операцией
• Lazy propagation — эффективные обновления отрезков

Рекомендуемый порядок изучения:

1. Базовое дерево для суммы
2. Минимум/максимум
3. Точечные обновления
4. Ленивое распространение
5. Итеративная реализация
6. Продвинутые техники (персистентность, 2D)