Сигнал задачи
Когда применять
Когда массив меняется между запросами и пересчитывать префиксы или весь диапазон после каждого обновления слишком дорого.
Разбор механики
Дерево Фенвика: префиксы через двоичные блоки
Вместо явного дерева хранится массив частичных сумм. Ячейка с внутренним индексом i отвечает за блок, который заканчивается в i и имеет длину lowbit(i) = i & -i. Эти блоки позволяют разложить любой префикс на O(log n) непересекающихся частей.
Инвариант
tree[i] равен сумме элементов на внутренних индексах от i - lowbit(i) + 1 до i включительно. Внешние индексы 0..n-1 переводятся во внутренние 1..n.
Как работает
- Точечное обновление добавляет delta сначала в блок текущего элемента, затем в каждый более крупный блок, который его содержит: i += i & -i.
- Префиксная сумма движется в обратную сторону: добавляет текущий блок и удаляет младший установленный бит через i -= i & -i, пока индекс не станет нулём.
- Сумма полуинтервала [left, right) получается как prefix(right) - prefix(left). Разность корректна для суммы, потому что у сложения есть обратная операция.
- Память остаётся линейной, а обновление и префиксный запрос проходят не больше числа битов индекса: O(log n).
Когда выбирать
- Выбирайте Fenwick для точечных изменений и префиксных или диапазонных сумм, когда нужен компактный код и не требуется хранить сложное состояние сегмента.
- Не переносите формулу разности на минимум или максимум: у этих операций нет обратного элемента, который удаляет левый префикс.
Референсная реализация
Обе версии выражают один контракт и запускаются в автоматической проверке проекта.
C++17: точечное добавление и сумма [left, right)
#include <iostream>
#include <stdexcept>
#include <vector>
class FenwickTree {
public:
explicit FenwickTree(int size) {
if (size < 0) {
throw std::invalid_argument("size must be non-negative");
}
tree_.assign(static_cast<std::size_t>(size) + 1, 0);
}
void add(int index, long long delta) {
check_index(index);
for (int i = index + 1; i < static_cast<int>(tree_.size()); i += i & -i) {
tree_[i] += delta;
}
}
long long prefix_sum(int end) const {
if (end < 0 || end >= static_cast<int>(tree_.size())) {
throw std::out_of_range("end is outside [0, size]");
}
long long result = 0;
for (int i = end; i > 0; i -= i & -i) {
result += tree_[i];
}
return result;
}
long long range_sum(int left, int right) const {
if (left < 0 || left > right || right >= static_cast<int>(tree_.size())) {
throw std::out_of_range("invalid half-open range");
}
return prefix_sum(right) - prefix_sum(left);
}
private:
std::vector<long long> tree_;
void check_index(int index) const {
if (index < 0 || index + 1 >= static_cast<int>(tree_.size())) {
throw std::out_of_range("index is outside the array");
}
}
};
int main() {
std::vector<int> values{3, -1, 4, 1, 5};
FenwickTree fenwick(static_cast<int>(values.size()));
for (int i = 0; i < static_cast<int>(values.size()); ++i) {
fenwick.add(i, values[i]);
}
std::cout << fenwick.prefix_sum(0) << '\n';
std::cout << fenwick.range_sum(0, static_cast<int>(values.size())) << '\n';
std::cout << fenwick.range_sum(1, 4) << '\n';
fenwick.add(2, 6);
std::cout << fenwick.range_sum(1, 4) << '\n';
}Python 3: тот же контракт полуинтервала
class FenwickTree:
def __init__(self, size: int) -> None:
if size < 0:
raise ValueError("size must be non-negative")
self._tree = [0] * (size + 1)
def add(self, index: int, delta: int) -> None:
self._check_index(index)
i = index + 1
while i < len(self._tree):
self._tree[i] += delta
i += i & -i
def prefix_sum(self, end: int) -> int:
if not 0 <= end < len(self._tree):
raise IndexError("end is outside [0, size]")
result = 0
i = end
while i > 0:
result += self._tree[i]
i -= i & -i
return result
def range_sum(self, left: int, right: int) -> int:
if not 0 <= left <= right < len(self._tree):
raise IndexError("invalid half-open range")
return self.prefix_sum(right) - self.prefix_sum(left)
def _check_index(self, index: int) -> None:
if not 0 <= index < len(self._tree) - 1:
raise IndexError("index is outside the array")
values = [3, -1, 4, 1, 5]
fenwick = FenwickTree(len(values))
for index, value in enumerate(values):
fenwick.add(index, value)
print(fenwick.prefix_sum(0))
print(fenwick.range_sum(0, len(values)))
print(fenwick.range_sum(1, 4))
fenwick.add(2, 6)
print(fenwick.range_sum(1, 4))Разбор механики
Дерево отрезков: иерархия агрегатов
Корень отвечает за весь массив, его дети — за две половины, а листья — за отдельные элементы. Запрос разбивается на небольшое число узлов, чьи интервалы целиком лежат внутри нужного диапазона.
Инвариант
Каждый узел хранит combine агрегатов двух детей и точно описывает свой полуинтервал. Операция combine должна быть ассоциативной, а пустому пересечению нужен нейтральный элемент.
Как работает
- Построение создаёт листья из элементов и пересчитывает внутренние узлы снизу вверх за O(n). В референсной итеративной форме база листьев округляется до следующей степени двойки: так каждый узел остаётся одним непрерывным полуинтервалом, а массив занимает меньше 4n ячеек.
- Точечное обновление меняет один лист и пересчитывает O(log n) предков. Запрос [left, right) поднимает границы вверх и добавляет только полностью покрытые узлы.
- Рекурсивная запись явно показывает интервалы и проще расширяется; итеративная обычно компактнее и экономит служебный стек для точечных обновлений и диапазонных запросов.
- Lazy propagation хранит отложенную операцию у целого сегмента и передаёт её детям только перед частичным спуском. Это отдельное усложнение для диапазонных обновлений, а не обязательная часть обычного дерева.
Когда выбирать
- Выбирайте дерево отрезков, если нужен минимум, максимум, НОД или составной агрегат, либо в будущем появятся диапазонные обновления.
- Сначала сформулируйте combine, нейтральный элемент и действие обновления на агрегат; без этого структура не определена.
Референсная реализация
Обе версии выражают один контракт и запускаются в автоматической проверке проекта.
C++17: итеративное дерево сумм
#include <iostream>
#include <stdexcept>
#include <vector>
class SegmentTree {
public:
explicit SegmentTree(const std::vector<int>& values)
: size_(static_cast<int>(values.size())) {
while (capacity_ < size_) {
capacity_ *= 2;
}
tree_.assign(2 * capacity_, 0);
for (int i = 0; i < size_; ++i) {
tree_[capacity_ + i] = values[i];
}
for (int i = capacity_ - 1; i > 0; --i) {
tree_[i] = tree_[2 * i] + tree_[2 * i + 1];
}
}
void set(int index, long long value) {
check_index(index);
int position = index + capacity_;
tree_[position] = value;
for (position /= 2; position > 0; position /= 2) {
tree_[position] = tree_[2 * position] + tree_[2 * position + 1];
}
}
long long range_sum(int left, int right) const {
if (left < 0 || left > right || right > size_) {
throw std::out_of_range("invalid half-open range");
}
long long left_result = 0;
long long right_result = 0;
for (left += capacity_, right += capacity_; left < right; left /= 2, right /= 2) {
if (left % 2 == 1) {
left_result += tree_[left++];
}
if (right % 2 == 1) {
right_result = tree_[--right] + right_result;
}
}
return left_result + right_result;
}
private:
int size_;
int capacity_ = 1;
std::vector<long long> tree_;
void check_index(int index) const {
if (index < 0 || index >= size_) {
throw std::out_of_range("index is outside the array");
}
}
};
int main() {
SegmentTree tree({2, 1, 5, 3, 4});
std::cout << tree.range_sum(0, 0) << '\n';
std::cout << tree.range_sum(0, 5) << '\n';
std::cout << tree.range_sum(1, 5) << '\n';
tree.set(2, 8);
std::cout << tree.range_sum(1, 5) << '\n';
}Python 3: итеративное дерево сумм
class SegmentTree:
def __init__(self, values: list[int]) -> None:
self._size = len(values)
self._capacity = 1
while self._capacity < self._size:
self._capacity *= 2
self._tree = [0] * (2 * self._capacity)
self._tree[self._capacity:self._capacity + self._size] = values
for index in range(self._capacity - 1, 0, -1):
self._tree[index] = self._tree[2 * index] + self._tree[2 * index + 1]
def set(self, index: int, value: int) -> None:
self._check_index(index)
position = index + self._capacity
self._tree[position] = value
position //= 2
while position > 0:
self._tree[position] = self._tree[2 * position] + self._tree[2 * position + 1]
position //= 2
def range_sum(self, left: int, right: int) -> int:
if not 0 <= left <= right <= self._size:
raise IndexError("invalid half-open range")
left_result = 0
right_result = 0
left += self._capacity
right += self._capacity
while left < right:
if left % 2 == 1:
left_result += self._tree[left]
left += 1
if right % 2 == 1:
right -= 1
right_result = self._tree[right] + right_result
left //= 2
right //= 2
return left_result + right_result
def _check_index(self, index: int) -> None:
if not 0 <= index < self._size:
raise IndexError("index is outside the array")
tree = SegmentTree([2, 1, 5, 3, 4])
print(tree.range_sum(0, 0))
print(tree.range_sum(0, 5))
print(tree.range_sum(1, 5))
tree.set(2, 8)
print(tree.range_sum(1, 5))Разбор механики
Как выбрать структуру для запросов на диапазоне
Выбор определяется не названием задачи, а двумя осями: меняется ли массив и какая операция объединяет части ответа. Самая простая структура, которая покрывает контракт, обычно даёт меньше ошибок.
Инвариант
Подготовка и обновления должны сохранять именно тот агрегат, который запрашивает задача; асимптотика имеет смысл только вместе с числом запросов и изменений.
Как работает
- Для неизменяемых сумм используйте префиксные суммы: O(n) подготовка и O(1) на запрос.
- Для неизменяемой идемпотентной операции вроде минимума и очень многих запросов подходит sparse table: O(n log n) подготовка, O(1) запрос, но без дешёвых обновлений.
- Для точечных изменений и сумм Fenwick даёт O(log n) с меньшим кодом и константами. Для более общего combine берите дерево отрезков.
- Диапазонные обновления требуют отдельной техники: разностного массива в пакетном сценарии, пары Fenwick для некоторых сумм или lazy propagation в дереве отрезков.
Когда выбирать
- Сравните число запросов, число обновлений, тип операции, ограничения памяти и допустимую сложность реализации до выбора структуры.
Как выбрать подход
- Fenwick проще и компактнее для точечных изменений и префиксных сумм; произвольная сумма [l, r] получается разностью двух префиксов.
- Дерево отрезков выбирают для произвольной ассоциативной операции с нейтральным элементом: суммы, минимума, максимума или составного состояния.
- Ленивое распространение нужно, когда и обновления, и запросы покрывают диапазоны; отложенная операция должна корректно действовать на агрегат узла.
- Сжатие координат помогает при разреженных индексах, если важен их порядок, но само по себе не превращает запросы по значениям в запросы по исходным координатам.
Сложность
- Fenwick: префиксный запрос и точечное обновление O(log n), память O(n); специальное построение возможно за O(n).
- Обычное дерево отрезков: построение O(n), запрос диапазона и точечное обновление O(log n), память O(n).
- Дерево отрезков с lazy propagation: диапазонный запрос и совместимое диапазонное обновление O(log n) для стандартных операций, память O(n).
Границы и ошибки
- Fenwick обычно индексируется с единицы: обновление индекса 0 зациклится, если не отделить внешнюю индексацию от внутренней.
- Разность префиксов работает не для любой операции; для минимума обратной операции нет.
- Ошибочная длина сегмента или порядок композиции lazy-тегов портит агрегаты после пересекающихся обновлений.
- Несогласованные полуинтервалы и замкнутые отрезки дают ошибки на границах.
- В референсном C++ коде суммы должны помещаться в long long. Python int расширяется автоматически, но стоимость арифметики растёт вместе с числом разрядов.