Привет, Хабр!
Кто-то приходит в Rust ради безопасной работы с памятью, кто-то — ради скорости, а кто-то просто потому, что «все нормальные языки уже попробовал». Но что бы ни привело вас в этот уголок низкоуровневой мощи, без хорошего знания алгоритмов далеко не уедешь.
Писать код на Rust — это не просто бороться с borrow checker, но и делать его действительно эффективным. Ведь никакой язык не спасет от тормозов, если алгоритмы выбраны неудачно.
В этой статье мы разберем пять фундаментальных алгоритмов, которые важны для разработки на Rust. Они помогут лучше понимать работу с данными, оптимизировать производительность и писать код, который не стыдно показать.
Бинарный поиск – быстрый способ находить элементы в отсортированных данных.
Сортировка слиянием – надежный метод сортировки с гарантированной сложностью O(n log n).
Алгоритм Дейкстры – лучший друг тех, кто строит кратчайшие пути.
Поиск подстроки (Рабин-Карп) – мощный алгоритм для работы с текстами.
Дерево отрезков – структура данных, которая кажется сложной, пока не поймешь, как она работает.
Разберем каждый алгоритм подробно: как он устроен, где его можно применять и какие нюансы могут возникнуть при реализации.
Бинарный поиск
Бинарный поиск — это один из самых быстрых способов поиска элемента в отсортированном массиве. В отличие от наивного линейного поиска O(n), который просто перебирает элементы один за другим, бинарный поиск разделяет массив пополам на каждом шаге, что снижает сложность до O(log n).
Допустим, есть отсортированный массив [1, 3, 5, 7, 9, 11, 15]. Если мы ищем число 7, бинарный поиск будет работать так:
Берем середину массива → arr[mid] = arr[3] = 7
Сравниваем с искомым числом → 7 равно 7
Нашли элемент!
Если бы мы искали 9, алгоритм бы:
Взял середину (7), увидел, что 9 > 7, отбросил левую половину
Взял середину оставшегося массива (9), нашел нужный элемент
Таким образом, мы значительно сокращаем количество проверок, что важно для очень больших массивов.
Алгоритм бинарного поиска работает по следующей схеме:
Устанавливаем два указателя: left (начало массива) и right (конец массива).
Пока left < right, берем середину массива:
mid = left + (right - left) / 2здесь используется
left + (right - left) / 2, а не(left + right) / 2, чтобы избежать переполнения)Если
arr[mid]совпадает с искомым числом — возвращаем его индекс.Если
arr[mid] < target, значит, искомый элемент находится справа, обновляемleft = mid + 1.Если
arr[mid] > target, значит, искомый элемент слева, обновляемright = mid.Повторяем процесс, пока
left < right. Если не нашли — возвращаемNone.
Реализация классического варианта
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
let (mut left, mut right) = (0, arr.len()); // Устанавливаем границы поиска
while left < right {
let mid = left + (right - left) / 2; // Находим середину массива
if arr[mid] == target {
return Some(mid); // Если элемент найден, возвращаем индекс
} else if arr[mid] < target {
left = mid + 1; // Ищем в правой половине
} else {
right = mid; // Ищем в левой половине
}
}
None // Если элемент не найден, возвращаем None
}
fn main() {
let arr = [1, 3, 5, 7, 9, 11, 15];
let target = 7;
match binary_search(&arr, target) {
Some(index) => println!("Элемент найден на позиции {}", index),
None => println!("Элемент отсутствует в массиве"),
}
}Алгоритм гарантированно работает за O(log n), даже если массив состоит из миллионов элементов.
Рекурсивный вариант
Иногда бинарный поиск удобнее записать через рекурсию. Это делает код более читаемым, но требует дополнительного места в стеке вызовов (O(log n)).
fn binary_search_recursive(arr: &[i32], target: i32, left: usize, right: usize) -> Option<usize> {
if left >= right {
return None; // База рекурсии: массив пуст, элемент не найден
}
let mid = left + (right - left) / 2;
if arr[mid] == target {
return Some(mid);
} else if arr[mid] < target {
return binary_search_recursive(arr, target, mid + 1, right);
} else {
return binary_search_recursive(arr, target, left, mid);
}
}
fn main() {
let arr = [1, 3, 5, 7, 9, 11, 15];
let target = 7;
match binary_search_recursive(&arr, target, 0, arr.len()) {
Some(index) => println!("Элемент найден на позиции {}", index),
None => println!("Элемент отсутствует в массиве"),
}
}Так код может выглядеть понятнее, если работа с рекурсией привычнее, но при этом есть минус, он использует дополнительную память.
Поиск "первого вхождения"
Допустим, в массиве есть повторяющиеся элементы, и нужно найти первое появление target, а не любое.
Пример:
arr = [1, 3, 3, 3, 5, 7, 9]
target = 3 // нужно вернуть индекс 1, а не 2 или 3fn binary_search_first(arr: &[i32], target: i32) -> Option<usize> {
let (mut left, mut right) = (0, arr.len());
let mut result = None;
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] >= target {
if arr[mid] == target {
result = Some(mid); // Запоминаем текущий индекс
}
right = mid; // Ищем левее
} else {
left = mid + 1;
}
}
result
}
fn main() {
let arr = [1, 3, 3, 3, 5, 7, 9];
let target = 3;
match binary_search_first(&arr, target) {
Some(index) => println!("Первое вхождение элемента {} на позиции {}", target, index),
None => println!("Элемент отсутствует"),
}
}В чем разница? Обычный бинарный поиск может вернуть любое вхождение, а этот вариант гарантированно находит самое левое вхождение.
Возможные проблемки
Если массив неотсортирован, бинарный поиск не сработает.
let arr = [5, 1, 7, 3, 9, 11, 15];
binary_search(&arr, 3); // Непредсказуемый результат!Перед поиском массив нужно отсортировать:
let mut arr = [5, 1, 7, 3, 9, 11, 15];
arr.sort();Если использовать mid = (left + right) / 2, при очень больших значениях left и right может случиться переполнение.
Правильный вариант:
let mid = left + (right - left) / 2;Итак, подходя к концу блока про эот алгоритм резюмируем:
Алгоритм работает только с отсортированными данными.
Всегда используйте mid = left + (right - left) / 2, чтобы избежать переполнения.
Если нужно найти первое вхождение, используйте модифицированную версию.
Переходим к следующему алгоритму.
Сортировка слиянием
Сортировка слиянием — это один из лучших алгоритмов сортировки, так как он гарантированно работает за O(n log n) в любом случае, в отличие от быстрой сортировки (O(n²) в худшем сценарии).
Алгоритм подходит для больших объемов данных и случаев, когда важна стабильность сортировки (не меняет порядок равных элементов).
Сортировка слиянием использует принцип "разделяй и властвуй".
Разделяем массив пополам.
Рекурсивно сортируем каждую половину.
Объединяем две отсортированные половины в один массив.
На каждом шаге массив делится на две части, а затем собирается обратно, поэтому глубина рекурсии составляет O(log n), а на каждом уровне выполняется O(n) операций слияния, что дает итоговую сложность O(n log n).
Реализация сортировки слиянием
fn merge_sort(arr: &mut [i32]) {
if arr.len() <= 1 {
return; // База рекурсии: если 1 элемент или пустой массив — сортировать не нужно
}
let mid = arr.len() / 2;
let mut left = arr[..mid].to_vec(); // Копируем левую половину
let mut right = arr[mid..].to_vec(); // Копируем правую половину
merge_sort(&mut left); // Рекурсивная сортировка левой части
merge_sort(&mut right); // Рекурсивная сортировка правой части
merge(arr, &left, &right); // Объединяем отсортированные части
}
fn merge(arr: &mut [i32], left: &[i32], right: &[i32]) {
let (mut i, mut j, mut k) = (0, 0, 0);
// Пока в обеих половинах есть элементы, выбираем минимальный и добавляем в arr
while i < left.len() && j < right.len() {
if left[i] <= right[j] {
arr[k] = left[i];
i += 1;
} else {
arr[k] = right[j];
j += 1;
}
k += 1;
}
// Добавляем оставшиеся элементы из левой части (если есть)
while i < left.len() {
arr[k] = left[i];
i += 1;
k += 1;
}
// Добавляем оставшиеся элементы из правой части (если есть)
while j < right.len() {
arr[k] = right[j];
j += 1;
k += 1;
}
}
fn main() {
let mut arr = [5, 2, 9, 1, 5, 6];
merge_sort(&mut arr);
println!("{:?}", arr); // [1, 2, 5, 5, 6, 9]
}merge_sort рекурсивно делит массив на две части, пока длина не станет ≤ 1 (такие массивы уже отсортированы). Т.к Rust не позволяет изменять части массива одновременно, left и right создаются как копии. Затем обе половины сортируются рекурсивно (merge_sort(&mut left), merge_sort(&mut right)) и объединяются в merge, где два указателя iи j последовательно выбирают минимальный элемент из left и right, вставляя его в arr, а оставшиеся элементы копируются в конец.
Избегаем лишнего копирования
to_vec() создает новые копии массивов при каждом разбиении. Это затратно по памяти и может замедлять выполнение.
Чтобы избежать лишних аллокаций, можно передавать временные буферы вместо выделения памяти каждый раз:
fn merge_sort_in_place(arr: &mut [i32], buffer: &mut Vec<i32>) {
if arr.len() <= 1 {
return;
}
let mid = arr.len() / 2;
let (left, right) = arr.split_at_mut(mid);
merge_sort_in_place(left, buffer);
merge_sort_in_place(right, buffer);
buffer.clear();
buffer.extend_from_slice(left);
let (mut i, mut j, mut k) = (0, 0, 0);
while i < mid && j < right.len() {
if buffer[i] <= right[j] {
arr[k] = buffer[i];
i += 1;
} else {
arr[k] = right[j];
j += 1;
}
k += 1;
}
while i < mid {
arr[k] = buffer[i];
i += 1;
k += 1;
}
}
fn main() {
let mut arr = [5, 2, 9, 1, 5, 6];
let mut buffer = Vec::new();
merge_sort_in_place(&mut arr, &mut buffer);
println!("{:?}", arr);
}Таким образом мы снизили аллокации, т.к используем один буфер вместо множества временных векторов. А так же вышло меньше копирований: уменьшена нагрузка на сборщик мусора и выделение памяти.
Альтернативные версии
Можно избежать рекурсии, используя итеративную сортировку слиянием, но это сложнее для понимания:
fn merge_sort_iterative(arr: &mut Vec<i32>) {
let mut step = 1;
let len = arr.len();
while step < len {
let mut temp = arr.clone();
let mut left = 0;
while left < len {
let mid = usize::min(left + step, len);
let right = usize::min(left + 2 * step, len);
let (mut i, mut j, mut k) = (left, mid, left);
while i < mid && j < right {
if arr[i] <= arr[j] {
temp[k] = arr[i];
i += 1;
} else {
temp[k] = arr[j];
j += 1;
}
k += 1;
}
while i < mid {
temp[k] = arr[i];
i += 1;
k += 1;
}
while j < right {
temp[k] = arr[j];
j += 1;
k += 1;
}
left += 2 * step;
}
arr.copy_from_slice(&temp);
step *= 2;
}
}
fn main() {
let mut arr = vec![5, 2, 9, 1, 5, 6];
merge_sort_iterative(&mut arr);
println!("{:?}", arr);
}Используем итеративный вариант тогда, когда нельзя использовать рекурсию (например, при ограничении глубины стека) или когда работа с маленькими массивами (он лучше использует кэш-память процессора).
Сортировка слиянием — надежный алгоритм, который работает за O(n log n) в любом случае. Плавно переходим к следующему алгоритму.
Алгоритм Дейкстры
Если вы когда-нибудь строили маршрут в Google Maps, то поздравляю — вы уже пользовались этим алгоритмом. Дейкстра решает классическую задачу поиска кратчайшего пути в графе с неотрицательными весами.
Где он используется:
Навигация (карты, GPS, логистика).
Компьютерные сети (оптимальные маршруты передачи данных).
Игровые движки (AI-поведение NPC, генерация лабиринтов).
Но есть нюанс: алгоритм не работает с отрицательными рёбрами. Если вдруг в графе можно "телепортироваться" из одной вершины в другую с отрицательной стоимостью, Дейкстра впадает в экзистенциальный кризис и даёт неверный результат. В таких случаях нужен уже Беллман-Форд.
Как работает Дейкстра:
Берем стартовую вершину, расстояние до неё — 0, до остальных — ∞ (то есть они пока недостижимы).
Выбираем ближайшую нерассмотренную вершину.
Обновляем пути до её соседей, если можем улучшить их расстояние.
Повторяем, пока не обработаем все вершины.
Всегда идем к самой близкой непосещенной точке.
Реализация Дейкстры на Rust
Идея: храним расстояния (dist), изначально бесконечные (usize::MAX). Используем приоритетную очередь (BinaryHeap), чтобы всегда брать ближайшую вершину. Проходимся по соседям текущей вершины, обновляем минимальные расстояния.
use std::collections::BinaryHeap;
use std::cmp::Ordering;
#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
cost: usize,
position: usize,
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost) // Инверсия порядка, т.к. BinaryHeap — это max-куча
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn dijkstra(graph: &[Vec<(usize, usize)>], start: usize) -> Vec<usize> {
let mut dist = vec![usize::MAX; graph.len()];
let mut heap = BinaryHeap::new();
dist[start] = 0;
heap.push(State { cost: 0, position: start });
while let Some(State { cost, position }) = heap.pop() {
// Если вершина уже обработана с меньшим расстоянием — пропускаем
if cost > dist[position] {
continue;
}
for &(next, weight) in &graph[position] {
let next_cost = cost + weight;
// Если нашли более короткий путь — обновляем
if next_cost < dist[next] {
heap.push(State { cost: next_cost, position: next });
dist[next] = next_cost;
}
}
}
dist
}
fn main() {
let graph = vec![
vec![(1, 2), (2, 4)], // Вершина 0 соединена с 1 (вес 2) и 2 (вес 4)
vec![(2, 1), (3, 7)], // Вершина 1 соединена с 2 (вес 1) и 3 (вес 7)
vec![(3, 3)], // Вершина 2 соединена с 3 (вес 3)
vec![], // Вершина 3 никуда не ведёт
];
let dist = dijkstra(&graph, 0);
println!("{:?}", dist); // Выведет: [0, 2, 3, 6] (кратчайшие пути от вершины 0)
}Сначала создаём массив dist, где все расстояния равны usize::MAX, кроме стартовой вершины (0). Затем инициализируем приоритетную очередь (BinaryHeap), которая работает как max-куча, поэтому порядок сортировки инвертируем (other.cost.cmp(&self.cost)) — так можно мгновенно извлекать вершину с минимальным расстоянием (O(log V)). Далее обходим граф: вытаскиваем ближайшую вершину (heap.pop()), проверяем пути до её соседей и, если находим более короткий маршрут, обновляем dist[next] и добавляем вершину обратно в очередь.
Можно реализовать Дейкстру без BinaryHeap, используя обычную очередь VecDeque, но тогда сложность будет O(V²), потому что мы каждый раз ищем минимальную вершину вручную.
BinaryHeap снижает сложность до O((V + E) log V), что намного лучше при работе с большими графами.
Хранение предыдущих вершин
Допустим, мы не просто хотим узнать длину кратчайшего пути, но и восстановить сам маршрут.
Решение тут простое: добавляем массив prev, который хранит "родителя" каждой вершины.
fn dijkstra_with_path(graph: &[Vec<(usize, usize)>], start: usize) -> (Vec<usize>, Vec<Option<usize>>) {
let mut dist = vec![usize::MAX; graph.len()];
let mut prev = vec![None; graph.len()]; // Храним предыдущие вершины
let mut heap = BinaryHeap::new();
dist[start] = 0;
heap.push(State { cost: 0, position: start });
while let Some(State { cost, position }) = heap.pop() {
if cost > dist[position] {
continue;
}
for &(next, weight) in &graph[position] {
let next_cost = cost + weight;
if next_cost < dist[next] {
heap.push(State { cost: next_cost, position: next });
dist[next] = next_cost;
prev[next] = Some(position); // Запоминаем путь
}
}
}
(dist, prev)
}
// Восстановление пути из prev
fn get_path(prev: &[Option<usize>], mut end: usize) -> Vec<usize> {
let mut path = vec![];
while let Some(p) = prev[end] {
path.push(end);
end = p;
}
path.push(end);
path.reverse();
path
}
fn main() {
let graph = vec![
vec![(1, 2), (2, 4)],
vec![(2, 1), (3, 7)],
vec![(3, 3)],
vec![],
];
let (dist, prev) = dijkstra_with_path(&graph, 0);
println!("Кратчайшие расстояния: {:?}", dist);
println!("Путь до 3-й вершины: {:?}", get_path(&prev, 3));
}Итак:
Дейкстра находит кратчайший путь в графе с неотрицательными весами.
BinaryHeap позволяет делать это эффективно (O((V + E) log V)).
Можно легко восстановить маршрут, храня предыдущие вершины.
А теперь поговорим про алгоритм поиска подстроки (Рабин-Карп).
Алгоритм поиска подстроки (Рабин-Карп)
Представим, что у нас есть огромный текст и нужно быстро найти в нем слово. Можно, конечно, использовать наивный O(n*m) алгоритм (перебирать подстроку в каждой позиции), но на больших объемах это звучит уже как то не очень.
Алгоритм Рабина-Карпа — это оптимизированный способ поиска подстроки за O(n + m), который использует хэш-функцию вместо перебора.
Применяется в поиске ключевых слов в поисковых системах, а так же в поиске дубликатов в анализе данных.
Как работает Рабин-Карп:
Вместо того чтобы сравнивать подстроку с каждой позицией строки посимвольно, алгоритм:
Вычисляет хэш подстроки (то, что мы ищем).
Берет хэш каждого куска строки такой же длины.
Если хэши совпали, выполняет обычное посимвольное сравнение (на случай коллизий).
Двигает окно дальше без пересчета хэша с нуля, а обновляет его за O(1).
Именно последний шаг делает его быстрым. Мы не пересчитываем хэш заново, а корректируем его, вычитая первый символ и добавляя новый.
Реализация в Rust
const P: u64 = 31; // Основание полиномиального хэша
const MOD: u64 = 1_000_000_007; // Простое число для предотвращения переполнения
fn compute_hash(s: &str) -> u64 {
s.chars().fold(0, |hash, c| (hash * P + (c as u64)) % MOD)
}
fn rabin_karp(text: &str, pattern: &str) -> Vec<usize> {
let n = text.len();
let m = pattern.len();
if m > n {
return vec![]; // Подстрока длиннее текста — ничего не найдём
}
let pattern_hash = compute_hash(pattern);
let mut current_hash = compute_hash(&text[..m]);
let mut results = vec![];
let highest_pow = P.pow((m - 1) as u32) % MOD; // P^(m-1) для обновления хэша
for i in 0..=n - m {
if current_hash == pattern_hash {
if &text[i..i + m] == pattern {
results.push(i);
}
}
if i < n - m {
let first_char = text.chars().nth(i).unwrap() as u64;
let new_char = text.chars().nth(i + m).unwrap() as u64;
current_hash = ((current_hash + MOD - (first_char * highest_pow) % MOD) * P + new_char) % MOD;
}
}
results
}
fn main() {
let text = "абракадабра";
let pattern = "бра";
let positions = rabin_karp(text, pattern);
println!("Подстрока найдена в позициях: {:?}", positions);
}Алгоритм начинается с вычисления хэша искомой подстроки и хэша первого окна текста длиной m. Для этого используется полиномиальный хэш, который кодирует строку в число, учитывая порядок символов. Основание p (обычно 31 или 53) и большое mod уменьшают вероятность коллизий. После вычисления начального хэша алгоритм начинает проход по тексту, сдвигая "окно" на один символ вправо на каждом шаге.
Чтобы не пересчитывать хэш заново (O(m)), используется обновление хэша за O(1):
Удаляем старый символ, вычитая его вклад.
Сдвигаем порядок разрядов умножением на p.
Добавляем новый символ в конец.
После каждого шага хэш сравнивается с хэшем подстроки. Если они совпадают, выполняется посимвольная проверка (из-за возможных коллизий). Если подстрока найдена, сохраняем её индекс. В итоге возвращается список всех позиций в тексте, где встречается искомая строка.
Иногда разные строки дают одинаковый хэш (например, "abcd" и "efgh"). Для решения этой проблему стоит использовать разные p и mod (например, p = 53, mod = 998244353) и проверять подстроку вручную после совпадения хэша.
Переходим к последнему алгоритму.
Дерево отрезков
Если вы хоть раз писали код, где надо быстро изменять массив и одновременно получать агрегированные данные (сумму, минимум, максимум, GCD), то рано или поздно сталкивались с проблемой: обычные массивы работают медленно.
Пример: есть массив из миллиона элементов, и нужно многократно:
Обновлять отдельные значения.
Запрашивать сумму/минимум/максимум на отрезке [L, R].
Если сделать это в лоб (через for), получим O(n), что при n = 10^6 и тысячах запросов становится настоящей болью. Дерево отрезков решает эту проблему, обеспечивая O(log n) на запрос и обновление.
Где используется:
Обработки больших массивов с частыми изменениями.
В компиляторных оптимизациях (анализ кода).
В графике и обработке изображений (быстро считать области).
Как оно работает?
Дерево отрезков — это структура данных, которая хранит информацию о подотрезках массива, позволяя быстро получать результаты.
Как строится:
Исходный массив разбивается пополам, рекурсивно, пока не останутся отдельные элементы.
В каждом узле хранится агрегированное значение (например, сумма или минимум).
Дерево строится за O(n), а запросы выполняются за O(log n).
Как оно обрабатывает запросы:
Если запрос полностью покрывает отрезок — мгновенно возвращаем сохранённое значение.
Если частично пересекает — идём в левую и правую половины, складываем их результаты.
Если не пересекает — просто возвращаем 0 (или бесконечность, если ищем минимум).
Реализация в Rust
Стандартная версия для суммы на отрезке + обновления элемента:
struct SegmentTree {
n: usize,
tree: Vec<i32>,
}
impl SegmentTree {
// Создаём дерево
fn new(arr: &[i32]) -> Self {
let n = arr.len();
let mut tree = vec![0; 4 * n]; // Достаточно памяти для хранения всего дерева
let mut seg_tree = SegmentTree { n, tree };
seg_tree.build(arr, 0, 0, n - 1);
seg_tree
}
// Рекурсивно строим дерево
fn build(&mut self, arr: &[i32], node: usize, left: usize, right: usize) {
if left == right {
self.tree[node] = arr[left];
} else {
let mid = (left + right) / 2;
let left_child = 2 * node + 1;
let right_child = 2 * node + 2;
self.build(arr, left_child, left, mid);
self.build(arr, right_child, mid + 1, right);
self.tree[node] = self.tree[left_child] + self.tree[right_child];
}
}
// Запрос суммы на отрезке [ql, qr]
fn query(&self, node: usize, left: usize, right: usize, ql: usize, qr: usize) -> i32 {
if ql > right || qr < left {
return 0; // Отрезок не пересекается
}
if ql <= left && qr >= right {
return self.tree[node]; // Полностью покрывает
}
let mid = (left + right) / 2;
let left_sum = self.query(2 * node + 1, left, mid, ql, qr);
let right_sum = self.query(2 * node + 2, mid + 1, right, ql, qr);
left_sum + right_sum
}
// Обновление элемента (изменить arr[idx] на new_val)
fn update(&mut self, node: usize, left: usize, right: usize, idx: usize, new_val: i32) {
if left == right {
self.tree[node] = new_val;
} else {
let mid = (left + right) / 2;
if idx <= mid {
self.update(2 * node + 1, left, mid, idx, new_val);
} else {
self.update(2 * node + 2, mid + 1, right, idx, new_val);
}
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2];
}
}
// Внешние методы для удобства
fn sum(&self, ql: usize, qr: usize) -> i32 {
self.query(0, 0, self.n - 1, ql, qr)
}
fn modify(&mut self, idx: usize, new_val: i32) {
self.update(0, 0, self.n - 1, idx, new_val);
}
}
fn main() {
let arr = [1, 3, 5, 7, 9, 11];
let mut seg_tree = SegmentTree::new(&arr);
println!("Сумма от 1 до 3: {}", seg_tree.sum(1, 3)); // 3 + 5 + 7 = 15
seg_tree.modify(1, 10); // arr[1] = 10
println!("Сумма от 1 до 3 после изменения: {}", seg_tree.sum(1, 3)); // 10 + 5 + 7 = 22
}build строит дерево: если отрезок — один элемент, заполняем узел, иначе рекурсивно создаём левую и правую половины, суммируя их значения. query обрабатывает запрос: если диапазон не пересекается — возвращаем 0, если полностью покрывается — используем готовое значение, если частично — идём в обе половины и складываем результаты. update обновляет элемент: если нашли нужный узел — меняем значение, иначе рекурсивно спускаемся в нужную половину, после чего пересчитываем родительские узлы. sum(L, R) обёртка для query, modify(index, value) обновляет элемент в массиве и перестраивает дерево.
Что еще можно улучшить? Ну, как минимум хранить не сумму, а минимум/максимум/GCD — просто заменяем + на нужную операцию. Использовать VecDeque для хранения дерева — если важна производительность. Добавить ленивое обновление — если изменения касаются целых отрезков.
Итак, дерево отрезков спасает, когда обычный массив уже не тянет.
Заключение
Алгоритмы, которые мы сегодня разобрали — это фундамент, на котором строится вся разработка. Но это далеко не предел. Мир алгоритмов огромен, и если вам интересно продолжить разбор, то какие темы вас волнуют больше? Пишите в комментариях — разберем вместе.
