Теоретическая база
Если вы давно решаете задачи Div1-Div2 на Codeforces, то наверняка уже слышали про сегментное дерево. Звучит возможно для кого-то страшно и не понятно, но на деле это очень полезная структура данных. Проще говоря, сегментное дерево — это такое бинарное дерево, в узлах которого хранятся агрегированные данные о каком-то отрезке массива. За счёт этой древовидной структуры мы можем быстро отвечать на запросы о произвольных сегментах массива да и не только отвечать, но и обновлять элементы.
Представьте, что у нас есть массив, и требуется многократно узнавать что-то про подотрезки этого массива, например, сумму элементов, минимум, максимум, количество каких-то значений и т.д. Сегментное дерево позволяет делать такие запросы очень быстро — обычно за O(log n) на каждый запрос вместо тривиального O(n) перебора. При этом оно достаточно гибкое, поддерживает изменение отдельных элементов, а с дополнительными трюками (ленивые пропагации) может даже массово обновлять целые диапазоны за то же логарифмическое время. В общем, сегментник может довольно хорошо оптимизировать алгоритм программы, когда обычных массивов и сортировок уже не хватает.
Пример сегментного дерева, построенного для массива arr = {1, 3, 5, 7, 9, 11}. Каждый узел хранит сумму на соответствующем отрезке: корень содержит 36 (сумма на всём отрезке [0;5]), его дети – суммы на [0;2] и [3;5] (9 и 27) и так далее.
