Привет, сообщество Codeforces! Меня зовут Адитья. Я занимаюсь спортивным программированием и учусь на факультете информатики. Долгое время Segment Tree меня пугало. Каждый туториал, который я читал, либо предполагал слишком много знаний, либо объяснял слишком мало. Поэтому это именно тот блог, который я хотел бы найти, когда только начинал. Что такое Segment Tree на самом деле? Представьте, что у вас есть массив из 8 чисел, и кто-то постоянно спрашивает вас: "Какова сумма элементов с индекса 2 по 6?" "Теперь измени элемент с индексом 4 на 100. Какова сумма с индекса 1 по 7?" Метод грубой силы даёт O(N) на каждый запрос. С Segment Tree вы получаете O(log N) как на запрос, так и на обновление. Segment Tree — это просто бинарное дерево, где каждый лист хранит один элемент массива, а каждый внутренний узел хранит результат объединения двух дочерних узлов, например сумму, минимум или максимум. Вот и всё. Правда. Строим дерево — шаг за шагом Допустим, наш массив: 1 3 5 7 9 11 Мы строим дерево, где узел с индексом i охватывает некоторый диапазон массива. Корень охватывает весь массив.
include bits/stdc++.h
using namespace std; const int MAXN = 1e5 + 5; int tree[4 * MAXN], arr[MAXN]; int n; void build(int node, int start, int end) { if (start == end) { tree[node] = arr[start]; } else { int mid = (start + end) / 2; build(2node, start, mid); build(2node+1, mid+1, end); tree[node] = tree[2node] + tree[2node+1]; } } Почему размер дерева 4 умножить на N? Потому что в худшем случае, когда N не является степенью двойки, дерево может содержать до 4N узлов. Безопасное правило: всегда выделяйте 4 умножить на N. Запрос на диапазон int query(int node, int start, int end, int l, int r) { if (r < start || end < l) return 0; if (l <= start && end <= r) return tree[node]; int mid = (start + end) / 2; int left = query(2node, start, mid, l, r); int right = query(2node+1, mid+1, end, l, r); return left + right; } Три случая, которые нужно запомнить: Случай 1 — Нет пересечения: вернуть нейтральный элемент, то есть 0 для суммы и INF для минимума Случай 2 — Полное вхождение: вернуть сохранённое значение напрямую Случай 3 — Частичное пересечение: рекурсивно обработать оба дочерних узла Обновление значения void update(int node, int start, int end, int idx, int val) { if (start == end) { arr[idx] = val; tree[node] = val; } else { int mid = (start + end) / 2; if (idx <= mid) update(2node, start, mid, idx, val); else update(2node+1, mid+1, end, idx, val); tree[node] = tree[2node] + tree[2node+1]; } } Как вызывать эти функции int main() { n = 6; arr[1]=1; arr[2]=3; arr[3]=5; arr[4]=7; arr[5]=9; arr[6]=11; build(1, 1, n);
cout << query(1, 1, n, 2, 5) << "\n"; update(1, 1, n, 4, 100); cout << query(1, 1, n, 2, 5) << "\n"; } Сумма с индекса 2 по 5 до обновления равна 24. После замены элемента с индексом 4 на 100 она становится равной 117. 3 вещи, которые меня запутали Первое — Почему индексация с единицы? Индексация массивов с 1 позволяет сделать так, что левый дочерний узел равен 2 умножить на node, а правый — 2 умножить на node плюс 1. Это работает чисто и удобно. При индексации с нуля нужно использовать 2 умножить на node плюс 1 и 2 умножить на node плюс 2, что менее удобно. Второе — Что такое нейтральный элемент? Для запросов суммы возвращайте 0 при отсутствии пересечения. Для минимума — INT_MAX. Для максимума — INT_MIN. Это должен быть нейтральный элемент вашей операции объединения. Третье — Когда использовать Segment Tree, а когда BIT (дерево Фенвика)? BIT проще в реализации и быстрее для запросов префиксных сумм. Segment Tree обрабатывает произвольные запросы на диапазон: минимум, максимум, НОД и пользовательские операции слияния. Если вы не уверены во время соревнования — Segment Tree является более безопасным выбором. Задачи для закрепления материала CSES — Range Sum Queries II: https://cses.fi/problemset/task/1648 CSES — Range Minimum Queries: https://cses.fi/problemset/task/1649 Codeforces 339D — Xenia and Bit Operations: https://mirror.codeforces.com/problemset/problem/339/D Codeforces 380C — Sereja and Brackets: https://mirror.codeforces.com/problemset/problem/380/C Итоги Построение дерева занимает O(N) времени. Запрос занимает O(log N) времени. Обновление занимает O(log N) времени. Память — O(N). Segment Tree — один из самых мощных инструментов в спортивном программировании. Как только вы по-настоящему поймёте его, следующим естественным шагом станет Ленивая Propagation для обновлений на диапазонах — об этом я расскажу в следующем блоге. Если это помогло вам, пожалуйста, поставьте плюс — так я понимаю, о чём писать дальше. Оставляйте вопросы в комментариях, я читаю всё. — Адитья (apmoggie01)
