Сегментное дерево в массиве: размер 4n, индексация узлов и ленивое проталкивание

Сегментное дерево в массиве размера 4n помещается при любом n. Корень занимает индекс 1, дети считаются как 2v и 2v+1, а заметная часть буфера уходит в запас под самый глубокий уровень, когда n не равно степени двойки. Такой размер не требует анализировать форму дерева и закрывает целый класс ошибок на границах. Дальше разбираем, откуда берётся оценка 4n, чем отличаются рекурсивная и итеративная индексация узлов и как связать массивное представление с ленивым проталкиванием.

Короткие ответы: для рекурсивного построения с корнем в 1 всегда хватает 4n; при n, равном степени двойки, достаточно 2n; итеративное дерево с корнем в 0 и листьями в конце массива укладывается в 2n - 1 ячеек; массив отложенных операций lazy индексируется теми же номерами, что tree, и требует того же размера.

Размер буфера - место, где ошибки проявляются поздно и больно. При n = 6 дерево доходит до индекса 13, и массива из 2n = 12 ячеек уже не хватает: запись в tree[13] уходит за границы. Разберём это на числах.

Зачем сегментному дереву массив размера 4n

Сегментное дерево - полное бинарное дерево, в листьях которого лежат элементы исходного массива, а во внутренних узлах - результат операции над потомками: сумма, минимум, максимум или произведение. Функция build(v, tl, tr) делит отрезок [tl, tr] пополам и рекурсивно строит два поддерева. Глубина такого обхода не превышает ⌈log2 n⌉ + 1: длина отрезка на каждом шаге уменьшается вдвое.

Номер узла в массиве однозначно задаётся путём от корня: корень - 1, шаг влево - умножение на 2, шаг вправо - умножение на 2 и плюс 1. На уровне d (корень считаем уровнем 0) индексы лежат в диапазоне от 2^d до 2^(d+1) - 1, поэтому максимальный индекс меньше 2^(h + 1), где h - максимальная глубина рекурсии. Подставляем h = ⌈log2 n⌉ + 1 и получаем оценку:

max_index ≤ 2^(⌈log2 n⌉ + 1) - 1 ≤ 2^(log2 n + 2) - 1 = 4n - 1.

Массива из 4n ячеек хватает при любом n, включая n = 1. Оценка опирается только на глубину рекурсии и не зависит от того, как именно делится отрезок.

Посмотрим на реальные индексы для n = 5. Массив выделяем на 4n = 20 ячеек, хотя заняты будут только 1..9:

Индексы 10..19 не используются. Этот запас и делает 4n удобным: он покрывает худший случай, а не конкретное n.

Почему 2n не всегда хватает

При n, равном степени двойки, дерево получается идеально сбалансированным: листья занимают позиции n..2n-1, всего узлов 2n - 1, максимальный индекс равен 2n - 1, и памяти хватает с запасом в одну ячейку. Для n = 8 это индексы 1..15, массива размера 16 полностью достаточно.

Как только n перестаёт быть степенью двойки, глубина ветвей расходится, и индексы уходят правее. Возьмём n = 6 и построим дерево вручную:

1. build(1, 0, 5) делит отрезок в точке tm = 2: левое поддерево получает [0, 2], правое - [3, 5].
2. [0, 2] распадается на [0, 1] и [2, 2], а [0, 1] - на [0, 0] и [1, 1].
3. [3, 5] делится на [3, 4] и [5, 5], а [3, 4] - на [3, 3] и [4, 4].

Получаются узлы с индексами 1, 2, 3, 4, 5, 6, 7, 8, 9, 12 и 13. Максимальный индекс равен 13 при 2n = 12, то есть массива размера 2n не хватит: нужно минимум 14 ячеек. Причина в том, что отрезок [3, 4] на третьем уровне спуска уходит в правые ветки и получает индексы 12 и 13, тогда как при ровном делении до степени двойки дальше 11 индексы не заходят.

Индексы 10 и 11 пустуют, зато 12 и 13 выходят за границу 2n. Оценка 4n снимает вопрос: 4 * 6 = 24 ячейки против 14 фактически нужных.

Как вычислить точный размер для конкретного n

Если память критична, размер считают точно. Два рабочих варианта:

1. n - степень двойки: достаточно 2n ячеек, используются индексы 1..2n-1.
2. n - не степень двойки: дополните массив до ближайшей степени двойки m нейтральными элементами (0 для суммы, +∞ для минимума, -∞ для максимума) и постройте дерево на m листьях. Размер станет 2m. Для n = 5 получаем m = 8 и 16 ячеек вместо 20.

Плата за экономию - дополнительная логика: хранить фактическое n, отсекать запросы за пределами [0, n-1] и следить, чтобы нейтральные элементы не попали в результат как значимые данные. При n = 7 максимальный индекс равен 13 при 2n = 14, то есть 2n хватает и для нестепени двойки, но проверять такой факт для каждого n вручную не стоит.

Отдельная схема - итеративное дерево с листьями в диапазоне n..2n-1 и родителем i/2. Там массива размера 2n хватает при любом n, включая нестепени двойки, но форма дерева уже не совпадает с полным бинарным деревом над исходным массивом, а ленивое проталкивание в такой схеме реализуется заметно сложнее.

Рекурсивная индексация: корень в 1, дети 2i и 2i+1

Классическая схема: tree[1] - корень, tree[2v] - левый ребёнок, tree[2v + 1] - правый. Границы отрезка передаются аргументами tl и tr и не дублируются в массиве, поэтому память уходит только на значения. Ячейка с индексом 0 не используется, и это первое место, где встречается off-by-one при чтении чужого кода.

Как рекурсивно строить и обновлять дерево

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

void update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        tree[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * v, tl, tm, pos, val);
    else           update(2 * v + 1, tm + 1, tr, pos, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

Для n = 4 и a = [1, 2, 3, 4] массив заполнится так: tree[1] = 10, tree[2] = 3, tree[3] = 7, tree[4] = 1, tree[5] = 2, tree[6] = 3, tree[7] = 4. Листья 4..7 лежат на глубине 2, и за пределы выделенных 4n = 16 ячеек ничего не выходит.

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return tree[v];
    int tm = (tl + tr) / 2;
    return query(2 * v, tl, tm, l, min(r, tm))
         + query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}

Точечное обновление устроено зеркально: спуск до листа по сравнению pos с tm, запись нового значения и пересчёт всех узлов на обратном пути. Сложность build, update и query одинаковая - O(log n).

Плюсы и минусы рекурсивной индексации

• Простой и предсказуемый код: одна формула для детей, одна для родителя.
• Ленивое проталкивание добавляется напрямую, массив lazy индексируется теми же номерами, что и tree.
• Глубина рекурсии порядка log2 n: для n = 10^6 это около 20 кадров стека на операцию.
• Минус - массив 4n, если не считать точный размер, и накладные расходы на вызовы функций при частых запросах. При n до 10^6 рекурсия обычно обходится дешевле, чем кажется по коду.

Итеративная индексация: корень в 0, дети 2i+1 и 2i+2

Вторая схема сдвигает индексы на единицу вниз: корень в 0, левый ребёнок 2i + 1, правый 2i + 2, родитель (i - 1) / 2 при целочисленном делении. Если n - степень двойки, листья занимают конец массива, с n - 1 по 2n - 2, и всего в дереве 2n - 1 узел. Для n = 4 внутренние узлы - 0, 1, 2, листья - 3, 4, 5, 6.

В шпаргалках часто пишут, что листья лежат в диапазоне n..2n-1. Это верно для индексации с единицей, где родитель равен i/2; при детях 2i+1 и 2i+2 вся граница сдвигается на единицу влево, и первый элемент массива попадает в лист с номером n - 1. Ошибка на единицу здесь обходится дорого: часть листьев читается из пустых ячеек.

// n - степень двойки, a - исходный массив длины n
for (int i = 0; i < n; ++i) tree[n - 1 + i] = a[i];
for (int i = n - 2; i >= 0; --i)
    tree[i] = tree[2 * i + 1] + tree[2 * i + 2];

Как работает итеративное обновление и запрос

void update(int p, int val) {          // p - индекс в исходном массиве
    int i = n - 1 + p;
    tree[i] = val;
    while (i > 0) {
        i = (i - 1) / 2;
        tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
    }
}

int query(int l, int r) {              // полуинтервал [l, r)
    int res = 0;
    l += n - 1;
    r += n - 1;
    while (l < r) {
        if (l % 2 == 0) res += tree[l++];   // l - правый ребёнок
        if (r % 2 == 0) res += tree[--r];   // r - правый ребёнок
        l = (l - 1) / 2;
        r = (r - 1) / 2;
    }
    return res;
}

Разберём запрос суммы на [1, 3) при n = 4 и a = [1, 2, 3, 4]. После инициализации tree[0] = 10, tree[1] = 3, tree[2] = 7, tree[3..6] = 1, 2, 3, 4, ячейка 7 свободна. Вызов query(1, 3) переводит границы в листовые позиции: l = 3 + 1 = 4, r = 3 + 3 = 6. Первая итерация: l чётное, значит это правый ребёнок, добавляем tree[4] = 2 и сдвигаем l на 5; r чётное, поэтому уменьшаем r до 5 и добавляем tree[5] = 3. Обе границы поднимаются к родителям: l = 2, r = 2, значения сравнялись, цикл завершён. Ответ 5 равен a[1] + a[2].

Итеративная схема держит только индексы, без границ отрезков, поэтому обходится без рекурсии и без проверок пересечения. За это приходится платить: дерево опирается на нумерацию листьев от n - 1, и для n, не равного степени двойки, итеративная схема с листьями в конце массива теряет свойство полного бинарного дерева. Практический выход - либо округлить n до степени двойки, либо взять вариант с родителем i/2 и массивом 2n для любого n.

Сравнение с рекурсивной индексацией

Выбор простой: если нужны обновления на отрезке с отложенными операциями, берите рекурсивную индексацию и 4n. Если операции только точечные, а запросов много, итеративная схема с двумя указателями даёт меньше накладных расходов, при условии что n приведено к степени двойки.

Ленивое проталкивание в массиве: как это работает

Идея ленивого проталкивания: обновляя отрезок целиком, мы не спускаемся к каждому листу, а записываем операцию в узел и останавливаемся. К потомкам она применится тогда, когда через узел пройдёт следующий запрос или обновление. Отложенные операции хранятся во втором массиве, индексируемом теми же номерами, что tree, поэтому его размер тоже считают как 4n.

Как написать push и update с ленивым проталкиванием

void push(int v, int tl, int tr) {
    if (lazy[v] == 0 || tl == tr) return;   // лист нечего проталкивать
    int tm = (tl + tr) / 2;
    int left = 2 * v, right = 2 * v + 1;
    tree[left]  += lazy[v] * (tm - tl + 1);
    lazy[left]  += lazy[v];
    tree[right] += lazy[v] * (tr - tm);
    lazy[right] += lazy[v];
    lazy[v] = 0;
}

Длины дочерних отрезков берутся из середины tm: для левого ребёнка это tm - tl + 1, для правого tr - tm. Проверка tl == tr в начале push защищает от обращения к детям листа с индексами 2v и 2v + 1, которых в дереве нет.

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r) return;
    if (l == tl && r == tr) {
        tree[v] += add * (tr - tl + 1);
        lazy[v] += add;
        return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, min(r, tm), add);
    update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return tree[v];
    push(v, tl, tr);                        // только после проверки покрытия
    int tm = (tl + tr) / 2;
    return query(2 * v, tl, tm, l, min(r, tm))
         + query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}

Порядок проверок в query принципиален: сначала отсекается l больше r, затем проверяется полное покрытие, и только после этого вызывается push. Если поднять push выше проверки на полное покрытие, отложенная операция будет спускаться в узлы, которые запрос не посещает, и дерево начнёт расходиться с массивом.

Разберём пример на a = [1, 2, 3, 4]. Начальное состояние: tree[1] = 10, tree[2] = 3, tree[3] = 7, листья равны 1, 2, 3, 4, все элементы lazy нулевые. Обновление update(1, 0, 3, 0, 3, 5) попадает в корень целиком:

После push у корня tree[2] = 13, lazy[2] = 5, tree[3] = 17, lazy[3] = 5. Дальше рекурсия идёт в оба ребёнка, каждый прогоняет свой push, и листья получают итоговые значения: tree[4] = 6, tree[5] = 7, tree[6] = 8, tree[7] = 9. Ответ на запрос [1, 2] равен 7 + 8 = 15, что совпадает с прямым подсчётом по массиву [6, 7, 8, 9].

Типичные ошибки при ленивом проталкивании

• push не вызывается перед частичным спуском. Отложенная операция остаётся на узле, дети возвращают старые значения, и запрос на подотрезке даёт заниженный результат при правильном ответе на всём диапазоне.
• Неверная длина дочернего отрезка. Левое поддерево получает tm - tl + 1 элементов, правое - tr - tm. Если взять (tr - tl) / 2 на оба, ошибка вылезает только на отрезках нечётной длины.
• Порядок записи. Сначала обновляется tree ребёнка, затем lazy ребёнка, и только потом обнуляется lazy родителя.
• Массив lazy меньшего размера, чем tree. Размеры обязаны совпадать: те же 4n.
• Операция присваивания на отрезке. Одного lazy мало: нужен признак того, что на узле висит set, иначе set и add смешиваются. Храните пару (set, add), при push сначала применяйте set, затем add.
• Проверка lazy[v] == 0 как универсальный признак. Она корректна, только когда ноль нейтрален для операции: для суммы это так, для присваивания и умножения нужен отдельный флаг.

Вот укороченный update с двумя типовыми дефектами:

void update_wrong(int v, int tl, int tr, int l, int r, int add) {
    if (l > r) return;
    if (l == tl && r == tr) {
        lazy[v] += add;          // tree[v] остался прежним
        return;
    }
    int tm = (tl + tr) / 2;      // push отсутствует
    update_wrong(2 * v, tl, tm, l, min(r, tm), add);
    update_wrong(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

Первый дефект ломает запросы, попадающие точно в этот узел: там вернётся старое значение. Второй портит все подотрезки, которые спускаются ниже: дети не знают о накопленной добавке. Лечится двумя строками - tree[v] += add * (tr - tl + 1) в ветке полного покрытия и вызовом push(v, tl, tr) перед разбиением отрезка.

Практические рекомендации: размер буфера и проверка границ

Правила, которые экономят часы отладки:

• Не уверены в n, берите 4n плюс небольшой запас: 4n + 5 закрывает и вопрос о случайном обращении к ячейке 0 при индексации с единицей. Пять лишних ячеек стоят байты и снимают риск.
• Посчитайте память заранее. Для int и n = 10^6 массив tree занимает 16 МБ, вместе с lazy - 32 МБ. При n = 10^7 это уже 320 МБ, и разумнее посмотреть на дерево Фенвика, разреженную таблицу или блочную декомпозицию.
• Знаете, что n - степень двойки, и ленивого проталкивания нет, хватит 2n; для итеративной схемы с корнем в 0 достаточно 2n - 1 ячеек.
• Итеративное дерево с ленивым проталкиванием: выделяйте 4n, схема с двумя указателями требует запаса под внутренние узлы.
• Буфер выделяйте один раз и переиспользуйте между тестами. Повторные resize на каждой итерации дают лишние реаллокации и копирование, механика роста разобрана в материале про динамические массивы и цену реаллокации.
• Проверки границ включайте только в отладочной сборке: assert(l >= 0 && r <= n - 1) на входе и assert(2 * v + 1 < size) перед обращением к правому ребёнку. В релизе они бьют по производительности.

Чек-лист перед запуском в продакшн

1. Размеры tree и lazy не меньше 4n, оба массива инициализированы (для суммы нулями, для присваивания отдельным флагом).
2. Во всех рекурсивных функциях есть отсечение l больше r и проверка полного покрытия l == tl и r == tr.
3. push вызывается после проверки полного покрытия и только для нелистовых узлов.
4. Длины дочерних отрезков считаются как tm - tl + 1 и tr - tm.
5. После возврата из рекурсии tree[v] пересчитывается из детей.
6. Проверены граничные случаи: n = 1, n = 2, запрос на весь массив, запрос на один элемент, обновление всего массива, пустой запрос с l больше r.
7. Есть стресс-тест против наивного пересчёта массива.

Стресс-тест на Python занимает минуту и ловит почти все ошибки в границах. Сверяем дерево с прямым пересчётом:

import random

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n + 5)
        self.lazy = [0] * (4 * self.n + 5)
        self.build(1, 0, self.n - 1, data)

    def build(self, v, tl, tr, data):
        if tl == tr:
            self.tree[v] = data[tl]
            return
        tm = (tl + tr) // 2
        self.build(2 * v, tl, tm, data)
        self.build(2 * v + 1, tm + 1, tr, data)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def push(self, v, tl, tr):
        if self.lazy[v] == 0 or tl == tr:
            return
        tm = (tl + tr) // 2
        left, right = 2 * v, 2 * v + 1
        self.tree[left] += self.lazy[v] * (tm - tl + 1)
        self.lazy[left] += self.lazy[v]
        self.tree[right] += self.lazy[v] * (tr - tm)
        self.lazy[right] += self.lazy[v]
        self.lazy[v] = 0

    def add(self, l, r, val):
        self._add(1, 0, self.n - 1, l, r, val)

    def _add(self, v, tl, tr, l, r, val):
        if l > r:
            return
        if l == tl and r == tr:
            self.tree[v] += val * (tr - tl + 1)
            self.lazy[v] += val
            return
        self.push(v, tl, tr)
        tm = (tl + tr) // 2
        self._add(2 * v, tl, tm, l, min(r, tm), val)
        self._add(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def total(self, l, r):
        return self._total(1, 0, self.n - 1, l, r)

    def _total(self, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return self.tree[v]
        self.push(v, tl, tr)
        tm = (tl + tr) // 2
        return (self._total(2 * v, tl, tm, l, min(r, tm))
                + self._total(2 * v + 1, tm + 1, tr, max(l, tm + 1), r))

def stress(n, trials=200, ops=40):
    for _ in range(trials):
        a = [random.randint(-20, 20) for _ in range(n)]
        st = SegTree(a)
        for _ in range(ops):
            l = random.randrange(n)
            r = random.randrange(l, n)
            if random.random() < 0.5:
                val = random.randint(-10, 10)
                st.add(l, r, val)
                for i in range(l, r + 1):
                    a[i] += val
            else:
                assert st.total(l, r) == sum(a[l:r + 1]), (a, l, r)

stress(9)

Прогоните тест на n = 1, 2, 3, 5, 9: нечётные размеры и n, не равное степени двойки, дают самые полезные падения. Соберите рабочий вариант из трёх решений: 4n плюс запас, рекурсивная индексация с корнем в 1, второй массив lazy того же размера. Добавьте assert на границы в debug-сборке, прогоните стресс-тест из чек-листа, и выход за пределы массива в сегментном дереве перестанет быть той ошибкой, которую ловят в проде по ночам.