Как деревья сегментов и деревья Фенвика (BIT) поддерживают быстрые запросы диапазона?

Question

Accepted Answer

**Дерево сегментов** и **дерево Фенвика** (Binary Indexed Tree, BIT) отвечают как на **запросы диапазона** (например, сумму по `[l, r]`), так и на **точечные обновления** в **O(log n)**, в отличие от O(n) для наивного сканирования или O(n) обновлений для массива префиксных сумм.

## Проблема, которую они решают

```text
Array + many "sum of range [l,r]" and "update index i" calls:
  naive prefix sums: query O(1) but UPDATE is O(n)
  segment/Fenwick:   query O(log n) AND update O(log n)
```

## Дерево Фенвика (BIT) — компактное и элегантное

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # jump to next responsible node
    def prefix(self, i):               # sum of [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## Дерево сегментов — более универсальное

Дерево сегментов хранит агрегированное значение для каждого сегмента массива в двоичном дереве, поддерживая **любую ассоциативную операцию** (сумму, минимум, максимум, НОД) и, с ленивым распространением, также **диапазонные обновления**.

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... down to single elements
```

## Сравнение

| | Фенвика (BIT) | Дерево сегментов |
|---|---|---|
| Запрос / обновление | O(log n) | O(log n) |
| Память | O(n) | O(2n) |
| Операции | суммы (обратимые) | любая ассоциативная операция |
| Диапазонные обновления | сложнее | легко (ленивое распространение) |
| Размер кода | минимальный | больший |

## Почему это важно

Эти структуры делают "обновить значение, затем запросить агрегат над диапазоном" быстрым — критично для соревновательного программирования, аналитических окон и задач на интервалы.

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

	Фенвика (BIT)	Дерево сегментов
Запрос / обновление	O(log n)	O(log n)
Память	O(n)	O(2n)
Операции	суммы (обратимые)	любая ассоциативная операция
Диапазонные обновления	сложнее	легко (ленивое распространение)
Размер кода	минимальный	больший