Fenwick/Segment tree на Python: как решать + 4 задачи с проверкой

Fenwick tree (дерево Фенвика) и Segment tree (дерево отрезков) — это способы хранить массив так, чтобы быстро делать много запросов и изменений. В олимпиадных задачах они появляются, когда есть длинный список значений (секции конвейера, фонари на улице, сила игроков) и поток операций: «прибавь в позиции i», «узнай сумму на префиксе/отрезке», «найди минимум/максимум», «посчитай количество инверсий».

Как распознать, что нужно именно это:

• в условии есть q запросов к массиву, и q большое (десятки тысяч и больше);
• есть обновления (чаще всего в одной позиции, иногда на отрезке);
• есть запросы вида «сумма/минимум/максимум/количество на отрезке [l..r]» или «сумма первых r»;
• прямой пересчёт за O(n) на каждый запрос не проходит по времени.

Суть приёма: вместо пересчёта целого отрезка мы храним агрегаты (например, суммы) в вершинах дерева. Обновление затрагивает только O(log n) вершин, и запрос тоже собирается из O(log n) кусочков. Fenwick — самый компактный вариант для префиксных сумм и точечных обновлений; segment tree — более универсален (любой «склеиваемый» ответ: сумма, минимум, максимум, количество, а с доп. идеями — и ленивые обновления).

С чего начать учиться:

• повтори префиксные суммы: чем они помогают и почему ломаются при изменениях;
• Fenwick: операции add(i, x) и sum(r), индексация с 1, идея «прыжков» по младшему установленному биту;
• переход к отрезку: sum(l..r) = sum(r) - sum(l-1);
• Segment tree: как хранить ответ в вершине и как «склеивать» два сына; рекурсивная или итеративная реализация;
• проверь типы данных (часто нужен long long) и граничные случаи.

Ниже — задачи с автопроверкой и разбором подхода: начнём с префиксных сумм через Fenwick и перейдём к более общим запросам через segment tree.