Дерево отрезков и дерево Фенвика

Есть задача, которая выглядит настолько простой, что кажется, будто её решает for-цикл: «дан массив из миллиона чисел, скажи сумму на отрезке [l, r)». И for-цикл её действительно решает — за O(n) на запрос. Проблема начинается, когда запросов тоже миллион, а между ними элементы меняются. Тогда O(n·q) — это 10¹² операций, то есть минуты вместо миллисекунд.

Эта статья — про два способа сделать так, чтобы и чтение отрезка, и изменение элемента стоили O(log n). Дерево Фенвика (binary indexed tree, BIT) — компактный трюк на битовой арифметике, который умеет мало, но делает это очень быстро и в двадцати строках кода. Дерево отрезков (segment tree) — универсальная конструкция, которая умеет почти всё, что можно выразить ассоциативной операцией, и расширяется до массовых обновлений, персистентности и запросов вроде «найди первый индекс правее l, где значение ≥ x».

Предполагается, что вы знакомы с асимптотикой и моделью памяти, массивами и деревьями.

Почему наивные решения не работают

Зафиксируем задачу. Дан массив a[0..n). Нужно поддерживать две операции:

• update(i, x) — изменить элемент;
• query(l, r) — вернуть агрегат по отрезку (сумма, минимум, максимум, gcd, …).

Есть ровно три очевидных решения, и все три упираются в одну и ту же стену:

Префиксные суммы — почти идеал, но одно изменение a[i] портит все p[j] при j > i. Это и есть суть проблемы: точечное изменение и агрегат по отрезку тянут в разные стороны. Массив оптимизирует запись, префиксные суммы — чтение, и обе крайности плохи.

Выход — промежуточная структура: хранить агрегаты не по всем префиксам и не по одному элементу, а по иерархии отрезков. Тогда и точка, и отрезок «задеваются» лишь O(log n) предпосчитанными кусками. Это ровно то, что делают дерево Фенвика и дерево отрезков, просто разными способами выбирая, какие именно отрезки предпосчитать.

Что вообще можно считать: моноид

Прежде чем писать код, стоит понять границу применимости. И Фенвик, и дерево отрезков склеивают ответ из кусков: query(l, r) = f(кусок₁) ⊕ f(кусок₂) ⊕ …. Чтобы это было корректно, операция ⊕ обязана быть ассоциативной: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). Плюс нужен нейтральный элемент e — чтобы было что вернуть на пустом отрезке. Пара (⊕, e) с этими свойствами называется моноидом.

Что подходит: сумма (+, 0), произведение (*, 1), min (min, +∞), max (max, −∞), gcd, побитовые and/or/xor, конкатенация строк, композиция линейных функций x ↦ kx + b, матричное умножение, «максимальная сумма подотрезка» (хитрая структура из четырёх чисел).

Что не подходит: среднее (не ассоциативно — но легко чинится, если хранить пару «сумма, количество» и делить только в конце), медиана, «количество различных значений» (не склеивается из двух половин), любая операция, которой нужен глобальный контекст.

Обратите внимание на последнюю связь. Дерево отрезков живёт на любом моноиде. Дерево Фенвика умеет отвечать только на префиксы, а отрезок получает вычитанием: query(l, r) = prefix(r) − prefix(l). Значит, ему нужна не просто ассоциативность, а обратимость — группа. Сумма и xor подходят, минимум — нет. Это главное функциональное ограничение Фенвика, и оно объясняет, почему в 90% реальных применений BIT считает именно суммы.

Дерево Фенвика: иерархия, спрятанная в битах

Идея Питера Фенвика (1994, задача — адаптивные таблицы частот для арифметического кодирования) красива до неприличия. Пронумеруем ячейки с единицы и договоримся:

Ячейка t[i] хранит сумму отрезка длиной lowbit(i), заканчивающегося в позиции i.

Здесь lowbit(i) = i & (−i) — младший установленный бит числа. Для i = 12 (двоичное 1100) lowbit = 4, значит t[12] = сумма a[9..12]. Для i = 13 (1101) lowbit = 1, значит t[13] = просто a[13].

Из картинки сразу видны оба алгоритма.

Запрос префикса prefix(i) — сумма a[1..i]. Берём t[i], он покрывает хвост длины lowbit(i). Остаётся префикс до i − lowbit(i), повторяем. Каждый шаг гасит один установленный бит, значит шагов не больше, чем битов в i: O(log n). prefix(13) = t[13] + t[12] + t[8] — три шага, потому что в 13 = 1101₂ три единицы.

Обновление add(i, δ) — идём вверх по «накрывающим» полосам: i += lowbit(i). Из 5 попадаем в 6, из 6 в 8, из 8 в 16. Тоже O(log n), потому что каждый шаг переносит бит влево.

class Fenwick:
    """Дерево Фенвика над суммами. Снаружи индексы 0-based, внутри 1-based."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.t = [0] * (n + 1)  # t[0] не используется

    @classmethod
    def from_list(cls, a: list[int]) -> "Fenwick":
        """Построение за O(n): каждый узел один раз «вливает» себя в родителя."""
        f = cls(len(a))
        for i, v in enumerate(a, start=1):
            f.t[i] = v
        for i in range(1, f.n + 1):
            parent = i + (i & -i)
            if parent <= f.n:
                f.t[parent] += f.t[i]
        return f

    def add(self, i: int, delta: int) -> None:
        """a[i] += delta. O(log n)."""
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i          # подъём к накрывающей полосе

    def prefix(self, i: int) -> int:
        """Сумма a[0..i) — то есть i элементов. O(log n)."""
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i          # гасим младший установленный бит
        return s

    def range_sum(self, l: int, r: int) -> int:
        """Сумма a[l..r). O(log n)."""
        return self.prefix(r) - self.prefix(l)

Обратите внимание на согласование индексов: наружу структура принимает полуинтервалы [l, r) в 0-based, а prefix(i) принимает количество элементов. Такая конвенция избавляет от половины off-by-one багов — prefix(0) естественно равен нулю, а range_sum(l, r) не требует ни одного ±1.

Построение через from_list — это O(n), а не O(n log n): мы кладём значения на места и один раз протягиваем каждое в его непосредственного «родителя» i + lowbit(i). Каждая ячейка участвует ровно в одном сложении.

Поиск по префиксу: бинарный спуск за O(log n)

Классическая задача: «найти минимальный индекс, у которого префиксная сумма ≥ k». На неотрицательных значениях префиксные суммы монотонны, и наивно это бинпоиск плюс prefix() — O(log² n). Но Фенвик — это дерево, и по нему можно спуститься напрямую, за один проход:

    def lower_bound(self, k: int) -> int:
        """Число элементов в максимальном префиксе с суммой < k.
        Требует неотрицательных значений. O(log n)."""
        pos = 0
        step = 1 << self.n.bit_length()
        while step:
            nxt = pos + step
            if nxt <= self.n and self.t[nxt] < k:
                pos = nxt
                k -= self.t[pos]
            step >>= 1
        return pos

Мы двигаемся по степеням двойки от старшей к младшей, «съедая» полосы, пока они помещаются в остаток. Это ровно спуск по неявному дереву — и именно этот приём делает Фенвик рабочим инструментом для взвешенного сэмплинга с динамическими весами: положили веса, lower_bound(random() * total) даёт элемент с вероятностью, пропорциональной весу, обновление веса — O(log n).

Массовые обновления двумя деревьями

Фенвик не ограничен точечными изменениями. Классический приём — работать с массивом разностей d[i] = a[i] − a[i−1]. Тогда «прибавить v на [l, r)» — это d[l] += v; d[r] -= v, то есть два точечных обновления, а a[i] = prefix(i+1) по разностям. Получаем «range update + point query» одним BIT.

Чтобы получить ещё и сумму на отрезке, нужен второй BIT-корректор. Раскроем:

sum(a[0..i)) = Σ_{j<i} Σ_{k≤j} d[k] = i·Σ_{k<i} d[k] − Σ_{k<i} k·d[k]

Первое слагаемое считает BIT над d, второе — BIT над k·d[k]:

class RangeFenwick:
    """Прибавление на отрезке + сумма на отрезке. Оба за O(log n)."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.b1 = Fenwick(n)   # коэффициент при i
        self.b2 = Fenwick(n)   # поправка

    def add_range(self, l: int, r: int, v: int) -> None:
        if l < self.n:
            self.b1.add(l, v)
            self.b2.add(l, v * l)
        if r < self.n:
            self.b1.add(r, -v)
            self.b2.add(r, -v * r)

    def prefix(self, i: int) -> int:
        return self.b1.prefix(i) * i - self.b2.prefix(i)

    def range_sum(self, l: int, r: int) -> int:
        return self.prefix(r) - self.prefix(l)

Два дерева по n чисел — всё ещё вдвое компактнее дерева отрезков и заметно проще lazy-логики. Если задача — «прибавить на отрезке, спросить сумму на отрезке», это лучший выбор по соотношению «строк кода к производительности».

Та же идея масштабируется в 2D: t[i][j], два вложенных цикла по lowbit — сумма по прямоугольнику за O(log² n) и O(n·m) памяти. Дальше растёт как O(logᵈ n), и уже при d = 3 обычно проще перейти к другой структуре.

Почему Фенвик так быстр на практике

Асимптотика у Фенвика и дерева отрезков одинаковая, но константа отличается в 2–4 раза в пользу BIT, и причин несколько:

• Памяти ровно n + 1 элементов против 2n (итеративное) или 4n (рекурсивное) у дерева отрезков. Массив на миллион int64 — 8 МБ против 32 МБ; разница между «влезло в L3» и «не влезло».
• Нет рекурсии и почти нет ветвлений — цикл из трёх арифметических операций, который отлично разворачивается компилятором.
• Короткие пути. prefix(i) делает popcount(i) шагов, а не log n — на «круглых» индексах это 1–2 обращения. В среднем по случайным i это log n / 2.

Обратная сторона — обращения к памяти разбросаны: t[13], t[12], t[8] лежат рядом, а t[1000000], t[999936], … — нет. При n порядка сотен миллионов промахи кеша доминируют, и разрыв с деревом отрезков сокращается.

Дерево отрезков: универсальный ответ

Дерево Фенвика — узкий инструмент. Дерево отрезков — общий: полное бинарное дерево, где лист v хранит a[v], а внутренний узел — агрегат своих детей. Корень покрывает [0, n), у каждого узла [lo, hi) дети покрывают [lo, mid) и [mid, hi).

Ключевое свойство — каноническое разбиение: любой отрезок [l, r) представляется как объединение не более 2·⌈log n⌉ узлов дерева, попарно непересекающихся.

Доказательство оценки простое и стоит его понимать, а не заучивать. Спускаясь от корня, на каждом уровне узел может быть в одном из трёх состояний:

Рекурсия продолжается только из «частичных» узлов. А частичных узлов на каждом уровне не более двух — один содержит границу l, другой границу r. Всё, что строго между ними, либо целиком внутри (останавливаемся), либо целиком снаружи (останавливаемся). Значит, посещённых узлов O(log n), и на каждом мы делаем O(1) работы.

Итеративная реализация: 2n ячеек и никакой рекурсии

Самый практичный вариант дерева отрезков — «снизу вверх» на массиве размера 2n (популяризирован заметкой Al.Cash на Codeforces). Листья лежат в t[n..2n), родитель узла i — это i // 2.

from typing import Callable, TypeVar

T = TypeVar("T")


class SegTree:
    """Итеративное дерево отрезков на моноиде (op, identity). Память 2n."""

    def __init__(self, data: list[T], op: Callable[[T, T], T], identity: T) -> None:
        self.op = op
        self.e = identity
        self.n = len(data)
        self.t = [identity] * (2 * self.n)
        self.t[self.n:] = data
        for i in range(self.n - 1, 0, -1):        # построение за O(n)
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def set(self, i: int, v: T) -> None:
        """a[i] = v. O(log n)."""
        i += self.n
        self.t[i] = v
        i >>= 1
        while i:
            self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])
            i >>= 1

    def query(self, l: int, r: int) -> T:
        """Агрегат по a[l..r). O(log n)."""
        resl, resr = self.e, self.e
        l += self.n
        r += self.n
        while l < r:
            if l & 1:                    # левая граница — правый ребёнок
                resl = self.op(resl, self.t[l])
                l += 1
            if r & 1:                    # правая граница — правый ребёнок
                r -= 1
                resr = self.op(self.t[r], resr)
            l >>= 1
            r >>= 1
        return self.op(resl, resr)

Здесь спрятана тонкость, на которой спотыкаются почти все. Обход идёт с двух сторон одновременно, и куски с левой границы встречаются до кусков с правой в порядке исходного массива. Поэтому нельзя копить всё в один аккумулятор: нужны два, resl накапливается слева направо, resr — справа налево, и склеиваются они в конце именно как op(resl, resr). Для суммы и минимума разницы нет — они коммутативны, и почти все примеры в интернете скрывают проблему. Но для композиции функций x ↦ kx + b или умножения матриц порядок критичен, и «упрощённая» версия молча вернёт мусор. Проверено: если ваша операция некоммутативна — пишите два аккумулятора.

Заметьте, что при n, не равном степени двойки, дерево из 2n элементов физически не является идеальным: его «уровни» кольцуются. Все запросы всё равно корректны для коммутативных операций, но для некоммутативных этот вариант требует дополнения n до степени двойки. Ниже мы так и делаем.

Рекурсивная реализация и спуск по дереву

Итеративная версия быстрее, но не умеет главного — спускаться по дереву с предикатом. Рекурсивная умеет, и это её главная ценность. Классическая задача: «найти первый индекс i ≥ l, для которого a[i] ≥ x». Наивно — бинпоиск по ответу с запросом максимума, O(log² n). Через спуск — O(log n): мы просто не заходим в поддеревья, максимум которых меньше x.

class MaxSeg:
    """Дерево максимумов с поиском первого подходящего элемента."""

    def __init__(self, data: list[int]) -> None:
        self.n = len(data)
        self.size = 1
        while self.size < self.n:          # дополняем до степени двойки
            self.size <<= 1
        self.t = [float("-inf")] * (2 * self.size)
        for i, v in enumerate(data):
            self.t[self.size + i] = v
        for i in range(self.size - 1, 0, -1):
            self.t[i] = max(self.t[2 * i], self.t[2 * i + 1])

    def first_at_least(self, l: int, x: int) -> int:
        """Первый индекс i >= l с a[i] >= x, иначе -1. O(log n)."""
        return self._go(1, 0, self.size, l, x)

    def _go(self, v: int, nl: int, nr: int, l: int, x: int) -> int:
        if nr <= l or self.t[v] < x:       # отсечение по максимуму поддерева
            return -1
        if nr - nl == 1:
            return nl
        mid = (nl + nr) // 2
        res = self._go(2 * v, nl, mid, l, x)
        return res if res != -1 else self._go(2 * v + 1, mid, nr, l, x)

Почему это O(log n), а не O(n)? Аргумент тот же, что и для запроса: узлы, полностью левее l, отсекаются первым условием; узлы, где ответа нет, отсекаются проверкой t[v] < x. «Живых» ветвей на каждом уровне не больше двух, а как только мы нашли первый лист — рекурсия сворачивается. Паддинг заполнен -inf, поэтому спуск никогда не забредёт в несуществующие индексы.

Этот приём — то, чего Фенвик не умеет в общем случае, и ради него одного стоит держать дерево отрезков в арсенале. На нём же строятся: поиск k-й порядковой статистики, «сколько подряд идущих единиц справа от позиции», задачи упаковки в контейнеры (first-fit за O(log n) вместо O(n)).

Отложенные операции (lazy propagation)

Пока что обновление было точечным. Но что если нужно «прибавить 5 ко всем элементам на [l, r)»? Наивно это O(r − l) точечных обновлений — снова линейно.

Решение основано на том же каноническом разбиении. Отрезок обновления покрывается O(log n) узлами; вместо того чтобы спускаться в них, мы записываем на узел пометку (тег): «ко всему моему поддереву нужно прибавить 5». Агрегат самого узла обновляем сразу — для суммы это t[v] += 5 * длина, для максимума t[v] += 5. А детей не трогаем, пока кто-нибудь не попытается в них спуститься; тогда мы «протолкнём» тег вниз (push).

Этот инвариант — «агрегат узла всегда актуален, тег относится только к детям» — и есть вся суть lazy propagation. Держите его в голове при отладке: если запрос возвращает мусор, почти всегда нарушен именно он.

class LazySegTree:
    """Прибавление на отрезке + максимум на отрезке. Обе операции O(log n)."""

    NEG = float("-inf")

    def __init__(self, data: list[int]) -> None:
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.t = [self.NEG] * (2 * self.size)
        self.lz = [0] * (2 * self.size)      # 0 — нейтральный тег для сложения
        for i, v in enumerate(data):
            self.t[self.size + i] = v
        for i in range(self.size - 1, 0, -1):
            self.t[i] = max(self.t[2 * i], self.t[2 * i + 1])

    def _apply(self, v: int, add: int) -> None:
        """Применить операцию к узлу целиком: агрегат обновляем, тег копим."""
        self.t[v] += add
        self.lz[v] += add                     # compose для сложения — это сложение

    def _push(self, v: int) -> None:
        """Протолкнуть тег детям и очистить его."""
        if self.lz[v]:
            self._apply(2 * v, self.lz[v])
            self._apply(2 * v + 1, self.lz[v])
            self.lz[v] = 0

    def add(self, l: int, r: int, val: int) -> None:
        self._add(1, 0, self.size, l, r, val)

    def _add(self, v: int, nl: int, nr: int, l: int, r: int, val: int) -> None:
        if r <= nl or nr <= l:                # нет пересечения
            return
        if l <= nl and nr <= r:               # целиком внутри — вешаем тег
            self._apply(v, val)
            return
        self._push(v)                         # частичное — сначала протолкнуть
        mid = (nl + nr) // 2
        self._add(2 * v, nl, mid, l, r, val)
        self._add(2 * v + 1, mid, nr, l, r, val)
        self.t[v] = max(self.t[2 * v], self.t[2 * v + 1])   # пересчёт снизу

    def max(self, l: int, r: int) -> int:
        return self._max(1, 0, self.size, l, r)

    def _max(self, v: int, nl: int, nr: int, l: int, r: int) -> int:
        if r <= nl or nr <= l:
            return self.NEG
        if l <= nl and nr <= r:
            return self.t[v]
        self._push(v)
        mid = (nl + nr) // 2
        return max(self._max(2 * v, nl, mid, l, r),
                   self._max(2 * v + 1, mid, nr, l, r))

Как проектировать свой lazy

Любая lazy-структура задаётся четырьмя вещами, и если аккуратно выписать все четыре, код пишется механически:

1. Тип агрегата T и его моноид (op, e). Для max это (max, −∞).
2. Тип тега F — множество допустимых операций над поддеревом.
3. apply(f, t, len) — как операция меняет агрегат. Для суммы нужна длина отрезка (t += f * len), для максимума — не нужна (t += f). Именно поэтому в сумме узлы часто хранят свой размер.
4. compose(new, old) — как склеить два тега. Тег old уже висит на узле, new пришёл позже; результат должен быть эквивалентен «сначала old, потом new».

Пункт 4 — источник большинства ошибок. Для «прибавить» композиция коммутативна и всё прощает. Но добавьте операцию «присвоить значение», и порядок станет критичен: присваивание стирает накопленное прибавление, а прибавление после присваивания — модифицирует его. Обычно тег кодируют парой (assign?, add) с правилами:

def compose(new, old):
    """Тег = (assign, add): сначала присвоить (если задано), потом прибавить."""
    n_assign, n_add = new
    o_assign, o_add = old
    if n_assign is not None:
        return (n_assign, n_add)          # новое присваивание стирает всё старое
    if o_assign is not None:
        return (o_assign, o_add + n_add)  # прибавление вливается в старое присваивание
    return (None, o_add + n_add)

Стоит проверить, что compose ассоциативна (compose(c, compose(b, a)) == compose(compose(c, b), a)) — это то же требование моноида, только на тегах. Хороший референс с формально выписанным контрактом — документация AtCoder Library lazy_segtree: там перечислены ровно эти свойства как предусловия.

Сложность с lazy остаётся O(log n) амортизированно и в худшем случае: мы посещаем те же O(log n) узлов, плюс на каждом делаем O(1) работы на push. Память — 2·2n (агрегаты + теги), то есть вдвое больше обычного дерева.

Что ещё умеет дерево отрезков

Каркас «иерархия отрезков + каноническое разбиение» переиспользуется гораздо шире, чем кажется. Короткий обзор, чтобы вы знали, что гуглить:

• Неявное (динамическое) дерево — узлы создаются лениво при первом обращении. Позволяет работать на диапазоне координат до 10¹⁸ без сжатия координат; память O(q log C) на q запросов.
• Персистентное дерево отрезков — при обновлении создаётся O(log n) новых узлов вместо копирования всего дерева, старые версии остаются доступны. Это основа ответов на запросы «k-я порядковая статистика на отрезке» и офлайн-задач. Идея восходит к Sarnak & Tarjan, «Planar Point Location Using Persistent Search Trees»; подробнее — в статье про персистентные структуры.
• Merge sort tree — в каждом узле хранится отсортированный список его отрезка. Отвечает на «сколько чисел > x на отрезке» за O(log² n), память O(n log n).
• Li Chao tree — дерево отрезков над множеством прямых, отвечает на «минимум всех прямых в точке x». Основа convex hull trick для динамического программирования.
• Segment tree beats — техника, позволяющая делать a[i] = min(a[i], x) на отрезке с суммарной сложностью O(n log² n) за счёт хранения двух максимумов в узле (оригинальный разбор).
• Дерево отрезков по значениям (а не по индексам) — превращается в структуру для порядковых статистик, конкурента сбалансированным деревьям.

Отдельно стоит помнить про статический случай: если массив не меняется вообще, для идемпотентных операций (min, max, gcd) sparse table даёт O(1) на запрос при O(n log n) предподсчёта — быстрее любого дерева. Классика здесь — Bender & Farach-Colton, «The LCA Problem Revisited».

Фенвик или дерево отрезков: как выбирать

Сводка по характеристикам:

Практическое правило: начинайте с Фенвика, если задача про суммы, и переходите на дерево отрезков, как только понадобился минимум, максимум, массовое присваивание или спуск по дереву. Переписать Фенвик в дерево отрезков — двадцать минут, а вот подпирать Фенвик костылями под задачу, для которой он не создан, можно бесконечно.

Типичные ошибки

Смешение 0-based и 1-based. Фенвик естественно 1-based (потому что lowbit(0) = 0 и цикл зациклится), дерево отрезков — 0-based. Выберите одну внешнюю конвенцию (рекомендую полуинтервалы [l, r) в 0-based) и конвертируйте строго на границе класса. Никогда не пишите while i <= n в одном методе и while i < n в другом.

Переполнение в дереве сумм. Корень хранит сумму всего массива. Если элементы до 10⁹, а их 10⁶, сумма до 10¹⁵ — int32 переполнится задолго до этого. В C++/Java/Go берите 64-битный тип для агрегата, даже если сами элементы 32-битные. В lazy-дереве опаснее вдвое: add * len может переполниться раньше, чем сама сумма.

Забытый push перед спуском. Самая коварная ошибка lazy-дерева: код работает на маленьких тестах и ломается на больших, потому что теги не успевают накопиться на нужной глубине. Правило простое — push вызывается всегда перед рекурсией в детей, и в обновлении, и в запросе. Запрос в lazy-дереве не может быть const.

Забытый пересчёт после рекурсии. Симметричная ошибка: спустились, обновили детей, но не выполнили t[v] = op(t[2v], t[2v+1]). Агрегат родителя остаётся устаревшим. Мнемоника: push вниз перед спуском, pull вверх после.

Один аккумулятор в итеративном запросе для некоммутативной операции. Разобрано выше; проверяйте свою реализацию на композиции функций, а не на суммах.

Использование Фенвика для минимума. Существуют варианты BIT для min, но они поддерживают только префиксный минимум и не умеют уменьшать значения (только монотонные обновления в одну сторону). Если увидели bit_min с произвольным обновлением — это баг, а не находка.

Нейтральный элемент, совпадающий с реальными данными. Если identity для min — это 0, а в массиве есть отрицательные числа, ответы будут занижены. Берите -inf/+inf или Optional, а не «достаточно большое число».

Паддинг до степени двойки, попадающий в ответ. При дополнении массива до size заполняйте хвост нейтральным элементом, а не нулями (для min/max это критично) — иначе спуск по дереву найдёт несуществующий индекс.

Где это живёт в проде

Дерево отрезков заслуженно считается «олимпиадной» структурой, но её частные случаи встречаются в реальном софте чаще, чем принято думать.

Адаптивное арифметическое кодирование. Это исходная мотивация статьи Фенвика: компрессору нужна таблица кумулятивных частот символов, которая обновляется после каждого закодированного байта. Точечное обновление + запрос префикса — ровно BIT. См. P. Fenwick, «A New Data Structure for Cumulative Frequency Tables», Software: Practice and Experience, 1994.

Prioritized Experience Replay в обучении с подкреплением. Буфер переигровки хранит переходы с приоритетами и должен сэмплировать пропорционально им, при этом приоритеты непрерывно меняются. Каноническая реализация (Schaul et al., 2015) использует «sum-tree» — дерево отрезков сумм со спуском по случайному числу, то есть буквально lower_bound из раздела выше.

Лидерборды и ранги. «Какое место у игрока с рейтингом X» — это подсчёт элементов с меньшим значением, то есть префиксная сумма по дереву над сжатыми значениями рейтинга. Обновление рейтинга — два точечных изменения. На миллионах игроков это единицы микросекунд против полного пересчёта.

Аллокаторы памяти. Buddy-аллокаторы часто реализуют как дерево максимумов над размерами свободных блоков: «найти самый левый блок, куда влезет запрос размера k» — это в точности спуск с предикатом за O(log n).

Совместное редактирование и CRDT. Чтобы перевести позицию курсора в идентификатор элемента при постоянных вставках/удалениях, нужны rank/select-запросы к последовательности. Реализации вроде Yjs и Automerge используют деревья с размерами поддеревьев — по сути дерево отрезков сумм над «жив/удалён».

Оконные агрегаты в потоковой обработке. Скользящие суммы и максимумы поверх меняющихся окон — либо monotonic deque (см. стеки и очереди), если окно движется монотонно, либо дерево отрезков, если запросы произвольные.

Чего в этом списке нет, и не случайно: реляционные СУБД для диапазонных запросов используют не деревья отрезков, а B+-деревья и колоночные min/max-индексы (zone maps). Причина — дисковая модель: дерево отрезков оптимизирует число операций, а не число обращений к блокам, и на диске проигрывает структурам с большим ветвлением.

Мини-итог

• Задача «агрегат по отрезку + изменения» решается иерархией предпосчитанных отрезков; и Фенвик, и дерево отрезков — две реализации одной идеи.
• Дерево Фенвика прячет иерархию в битах индекса: t[i] покрывает lowbit(i) элементов. n ячеек, ~20 строк, лучшая константа. Требует обратимой операции — на практике сумма/xor.
• Двумя BIT над массивом разностей получаются массовые обновления с запросом суммы — часто это всё, что нужно, и это проще lazy-дерева.
• Дерево отрезков работает с любым моноидом и опирается на каноническое разбиение: любой отрезок — объединение O(log n) узлов, а частичных узлов на уровне не больше двух.
• Lazy propagation задаётся четвёркой «агрегат, тег, apply, compose»; инвариант — «агрегат узла актуален, тег относится только к детям».
• Уникальная способность дерева отрезков — спуск с предикатом за O(log n) там, где бинпоиск дал бы O(log² n).
• Если массив статичен — не стройте дерево: префиксные суммы или sparse table быстрее.

Источники

• P. Fenwick. A New Data Structure for Cumulative Frequency Tables. Software: Practice and Experience, 24(3), 1994 — оригинальная статья про BIT.
• cp-algorithms: Fenwick Tree и Segment Tree — лучший бесплатный справочник с разбором всех вариаций.
• Al.Cash. Efficient and easy segment trees — итеративная реализация на 2n.
• AtCoder Library: segtree и lazy_segtree — промышленно вылизанный C++ API с формальными предусловиями на моноид.
• Segment tree beats — техника для chmin/chmax на отрезке.
• N. Sarnak, R. E. Tarjan. Planar Point Location Using Persistent Search Trees. CACM 29(7), 1986 — истоки персистентности.
• M. Bender, M. Farach-Colton. The LCA Problem Revisited — sparse table и статический RMQ.
• T. Schaul et al. Prioritized Experience Replay — sum-tree в продакшн-ML.
• CLRS, Introduction to Algorithms, 4-е издание, глава 17 «Augmenting Data Structures» — общая теория дополнения деревьев агрегатами.

Что дальше

Дерево отрезков даёт точные ответы ценой Θ(n) памяти. Но что если данных настолько много, что не помещается даже сам массив — миллиарды уникальных значений в потоке? Тогда приходится менять точность на память: следующая статья — Вероятностные структуры: Bloom filter, HyperLogLog, Count-Min Sketch. Любопытно, что Count-Min Sketch решает почти ту же задачу, что и Фенвик — частоты элементов, — но за O(1) памяти на элемент и с контролируемой вероятностью ошибки.