---
title: "Дерево Фенвика / дерево отрезков"
url: https://algopath.pro/ru/patterns/fenwick-segment-tree
language: ru
summary: "Дерево над отрезками отвечает на запрос и принимает изменение, и то и другое за log n. Префиксные суммы второго не умеют."
updated: 2026-08-24
---

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

Дерево над отрезками отвечает на запрос и принимает изменение, и то и другое за log n. Префиксные суммы второго не умеют.

## Дерево Фенвика / дерево отрезков: как это работает?

Каждый узел дерева владеет отрезком и хранит ответ по нему. Корню принадлежит весь массив.

Ответ узла собирается из двух его потомков. Правилом слияния служит сумма, минимум, максимум или похожее.

Запрос разбивает нужный отрезок по дереву. Он останавливается на узлах, целиком лежащих внутри.

Больше двух узлов на уровень никогда не нужно. Отсюда и log n работы на запрос.

Изменение правит один лист и поднимается к корню. Меняются только узлы над этим листом.

Дерево Фенвика делает то же для префиксных сумм гораздо меньшим кодом. Дерево отрезков умеет ещё минимум, максимум и отложенные изменения.

- `листья: 3, 1, 4, 1` Массив это [3, 1, 4, 1]. Каждый лист владеет одной позицией.
- `уровень выше: 4 и 5` Каждый узел суммирует двух своих потомков.
- `корень = 9` В корне лежит сумма всего массива.
- `запрос с 1 по 2` Нужный отрезок это 1 плюс 4. Его точно накрывают два узла.
- `запись 6 в индекс 1` Меняются один лист и два узла над ним. Корень становится 14.

## Дерево Фенвика / дерево отрезков: когда применять?

- сумма или запрос на отрезке с точечными обновлениями вперемешку
- живой лидерборд или ранг, пока баллы меняются
- подсчёт инверсий или сколько более ранних значений больше
- запросы на отрезке, пока данные продолжают меняться

## Дерево Фенвика / дерево отрезков: с чем путают?

- **Префиксные суммы** - Префиксные суммы читаются быстрее, но ломаются при любом изменении. Здесь платят log n за право менять.
- **Массив разностей** - Он принимает много изменений на отрезках и одно чтение в конце. Здесь чтения и записи перемешаны.
- **Линия развёртки (подсчёт событий)** - Развёртка идёт по событиям в порядке сортировки и не оглядывается. Здесь запросы приходят в любом порядке.
- **Бинарный поиск (массив)** - Оба делят отрезок пополам на каждом шаге. Один ищет значение, другой сворачивает отрезок.

## Дерево Фенвика / дерево отрезков: сложность по времени и памяти

n до 1e6 и q смешанных операций дают O((n + q) log n). Память O(n) для дерева Фенвика.

## Дерево Фенвика / дерево отрезков: разбор примера

### Сколько меньших значений стоит справа

Для каждого элемента посчитайте, сколько более поздних элементов меньше него.

Вложенный цикл это O(n в квадрате), и он умирает на 1e5 элементов.

Идите по массиву справа налево, держа дерево Фенвика над значениями.

Для каждого элемента спросите, сколько меньших уже записано. Потом запишите текущий.

```javascript
function countSmaller(nums) {
    const sorted = [...new Set(nums)].sort((a, b) => a - b);
    const rank = new Map(sorted.map((v, i) => [v, i + 1])); // ranks start at 1

    const tree = new Array(sorted.length + 1).fill(0);

    const add = (i) => {
        for (; i < tree.length; i += i & -i) tree[i]++;
    };

    const countBelow = (i) => {
        let total = 0;
        for (; i > 0; i -= i & -i) total += tree[i];
        return total;
    };

    const answer = new Array(nums.length);
    for (let i = nums.length - 1; i >= 0; i--) {
        const r = rank.get(nums[i]);
        answer[i] = countBelow(r - 1); // strictly smaller values already seen
        add(r);
    }

    return answer;
}
```

## Дерево Фенвика / дерево отрезков: частые ошибки

- **Индексируют дерево Фенвика с нуля** Шагу по младшему биту нужны индексы с единицы. Нулевой индекс зацикливает цикл.
- **Берут его там, где ничего не меняется** Префиксный массив отвечает за O(1) и ничего не стоит при чтении. Платите за дерево, только когда есть изменения.
- **Забывают сжать значения** Дерево размером с диапазон значений умирает на числах до 1e9. Сначала переведите их в ранги.
- **Сливают отрезки неподходящим правилом** Сумма и минимум работают, потому что порядок им не важен. Правилу, зависящему от порядка, нужно больше в узле.

## Дерево Фенвика / дерево отрезков: задачи с собеседований

- **Сумма на отрезке с изменениями** Чтения и записи идут вперемешку в любом порядке.
- **Сколько меньших справа** Дерево Фенвика над сжатыми рангами.
- **Число сумм в диапазоне** Префиксные суммы, поданные в дерево.
- **Обратные пары** Подойдёт и сортировка слиянием, и дерево Фенвика.
- **Минимум на отрезке** Дерево отрезков, поскольку у минимума нет обратной операции.
- **Сумма на прямоугольнике с изменениями** Дерево, узлами которого служат другие деревья.
- **Мой календарь II** Дерево отрезков с отложенными изменениями на отрезке.

## JavaScript

```javascript
class Fenwick {
    constructor(n) { this.tree = new Array(n + 1).fill(0); }
    update(i, delta) {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }
    query(i) {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}
```

## Python

```python
class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total
```

## PHP

```php
class Fenwick {
    private array $tree;
    public function __construct(int $n) { $this->tree = array_fill(0, $n + 1, 0); }
    public function update(int $i, int $delta): void {
        for (; $i < count($this->tree); $i += $i & -$i) $this->tree[$i] += $delta;
    }
    public function query(int $i): int {
        $sum = 0;
        for (; $i > 0; $i -= $i & -$i) $sum += $this->tree[$i];
        return $sum;
    }
}
```