## Теоретическая база↵
↵
Если вы давно решаете задачи Div1-Div2 на Codeforces, то наверняка уже слышали про **сегментное дерево**. Звучит возможно для кого-то страшно и не понятно, но на деле это очень полезная структура данных. Проще говоря, сегментное дерево — это такое бинарное дерево, в узлах которого хранятся агрегированные данные о каком-то отрезке массива. За счёт этой древовидной структуры мы можем быстро отвечать на запросы о произвольных сегментах массива да и не только отвечать, но и обновлять элементы.↵
↵
Представьте, что у нас есть массив, и требуется многократно узнавать что-то про подотрезки этого массива, например, сумму элементов, минимум, максимум, количество каких-то значений и т.д. Сегментное дерево позволяет делать такие запросы очень быстро — обычно за O(log n) на каждый запрос вместо тривиального O(n) перебора. При этом оно достаточно гибкое, поддерживает изменение отдельных элементов, а с дополнительными трюками (ленивые пропагации) может даже массово обновлять целые диапазоны за то же логарифмическое время. В общем, сегментник может довольно хорошо оптимизировать алгоритм программы, когда обычных массивов и сортировок уже не хватает.↵
↵
_Пример сегментного дерева, построенного для массива arr = {1, 3, 5, 7, 9, 11}. Каждый узел хранит сумму на соответствующем отрезке: корень содержит 36 (сумма на всём отрезке [0;5]), его дети – суммы на [0;2] и [3;5] (9 и 27) и так далее._↵
↵
↵
↵
#### Как это работает?↵
↵
Мы рекурсивно делим массив пополам, пока не дойдём до отдельных элементов. Эти элементы — листья дерева. Затем начинаем “склеивать” информацию снизу вверх: каждый внутренний узел вычисляется из двух дочерних. Например, если нам нужны суммы, то значение узла = сумма левого сына + сумма правого сына. Если нужны минимумы — берём минимум из двух детей, и т.д. В итоге корень хранит агрегат (сумму/мин/макс и пр.) по всему массиву, а путь от корня к листу соответствует делению отрезка на подотрезки.↵
↵
#### Когда это нужно?↵
↵
Сегментное дерево может быть использовано, когда:↵
1. Нужно эффективно отвечать на запросы о подмножествах элементов массива (сумма на отрезке, максимум на отрезке, НОД на отрезке и т.п.) и при этом между запросами могут происходить изменения отдельных элементов или целых диапазонов, то есть данные динамические. В таком случае простое предвычисление всех ответов не поможет↵
2. Запросов и обновлений много (десятки и сотни тысяч) и делать их за линейное время слишком медленно↵
↵
Сегментное дерево обеспечивает ~O,2025-03-19(log n) на один запрос или обновление, что обычно укладывается в лимиты при n и количестве запросов порядка 10^5. При этом память сегментника ~4*n элементов для массива размера n — тоже вполне ок.↵
↵
#### Примеры задач, решаемых сегментным деревом↵
↵
Диапазонные суммы, поиск минимума/максимума на отрезке, количество определённых элементов на отрезке, проверка упорядоченности сегмента, даже поиск k-го по счёту элемента. Например, с помощью сегментного дерева можно легко узнать, сколько нулей в заданном диапазоне или найти индекс k-го нуля в массиве. Кстати, именно такую задачу мы сейчас рассмотрим на практике.↵
↵
## Практическая часть↵
↵
Давайте на примере рассмотрим задачу [problem:2075F] с недавнего контеста [contest:2075], решив её при помощи сегментного дерева и проведём аналогию в сравнении с решением "в лоб".↵
↵
Рассмотрим решение данной задачи от [user:wishgoodluck,2025-03-19] — [submission:311252841]. Идея данного алгоритма основана на «событийном подходе». Мы предварительно вычисляем два массива (назовём их l и r), которые фиксируют важные границы в исходной последовательности. Эти массивы помогают определить, для каких отрезков происходит «изменение» (увеличение или уменьшение вклада в итоговый ответ). Затем формируется вектор событий — каждый элемент этого вектора задаёт, что на определённом отрезке надо добавить или убрать некоторое значение. В финале итоговая длина искомой последовательности получается как максимальное суммарное изменение.↵
↵
Ключевая задача заключается в том, чтобы быстро и эффективно обрабатывать множество событий, которые влияют на диапазоны индексов. Именно для этого и используется сегментное дерево.↵
↵
В данном решении сегментное дерево применяется для двух операций:↵
↵
- Диапазонное обновление (Range Update). Каждое событие из вектора v задаёт, что на отрезке [l,r] нужно прибавить либо +1, либо -1. Сегментное дерево с ленивыми обновлениями позволяет за O(log n) за одно событие обновить сразу весь отрезок, не проходясь по каждому элементу отдельно.↵
- Запрос максимума (Range Query). После каждого обновления нам нужно быстро узнать, каково максимальное значение на всём диапазоне. Корень дерева (Tree[1].v) всегда хранит максимум среди всех элементов. Это позволяет мгновенно (за O(1) после O(log n) обновлений) узнать текущее оптимальное значение, которое потом используется для вычисления ответа.↵
↵
Таким образом, сегментное дерево здесь выступает как «агрегатор» всех событий, аккумулируя их влияние на заданных отрезках и позволяя быстро находить максимум.↵
↵
Представьте себе задачу, где нужно на каждом шаге для каждого события обновить все элементы отрезка. Если диапазон имеет длину m, то наивное обновление занимает O(m) операций. При m∼n и O(n) событиях получаем O(n^2) операций. Это решение быстро станет неприемлемым по времени даже для средних размеров входных данных.↵
↵
В отличие от этого, сегментное дерево позволяет обновлять целые диапазоны за ↵
O(log n) благодаря ленивой пропагации. Таким образом, даже если событий много, общая сложность становится ↵
O(n*log n).↵
↵
## Подводные камни и советы↵
↵
Сегментное дерево — штука мощная, но при реализации можно допустить несколько типовых ошибок:↵
↵
- Неправильное слияние результатов. Забудете, что нужно суммировать детей, или перепутаете левый/правый и вся логика разрушится. Внимательно определяйте, что хранит узел, и как это получается из информации детей.↵
- Границы отрезков. Легко ошибиться с индексами left, right и middle. Условились, что сегмент [left..right] включительный. Тогда middle = (left+right)/2 – левая часть [left..middle], правая [middle+1..right]. Если забудете +1 где нужно – получите перекрывающиеся или пропущенные индексы. Совет: отладьте на маленьком массиве, например, n=4 и выпишите на бумажке сегменты каждого узла, проверьте, что покрывают массив без пробелов и наложений.↵
- Рекурсия vs итерация. Мы рассмотрели рекурсивное решение для простоты понимания, но при n ~ 10^5 глубина рекурсии ~17 – это ок, а вот если бы n ~ 10^7, глубина ~24, всё ещё ок. При сильно больших n и особенно при большом количестве операций иногда предпочитают итеративные реализации во избежание накладных расходов и риска переполнения стека.↵
- Ленивые обновления. В нашем примере мы как раз их использовали, обновляя сразу целый диапазон. Обратите внимание, что реализация ленивых тегов сложнее — легко напутать с распространением изменений на детей. Если задача требует сегментник с lazy, тестируйте на простых примерах усиленно. Типичные ошибки: забыли запушить лейзи-тег перед дальнейшим спуском или перед подсчётом в узле — получите некорректные данные. Совет: написать отдельную функцию push(v) для распространения тега из узла v на детей, и вызывать где нужно, например перед переходом в поддеревья.↵
- Выбор между Fenwick (BIT) и сегментным деревом. Часто они взаимозаменяемы для простых задач на суммы, порядковую статистику. Fenwick легче кодится и требует ~n,2025-03-19 памяти, но сегментное дерево более универсально, поддерживает сложные операций слияния. Если задача допускает Fenwick и вы не хотите тратить время на реализацию дерева — дерзайте с Fenwick, однако сегментник — must know для Div1-Div2 уровня.↵
↵
Напоследок дам небольшой лайфхак — если задача просто требует многократных запросов суммы на отрезке без обновлений, то и сегментное дерево не нужно, достаточно просто будет заранее посчитать префиксные суммы за O(n) и потом каждый запрос отвечать заTheoretical basis↵
↵
If you have been solving Div1-Div2 problems on Codeforces for a long time, you have probably heard about **segment tree**. It may sound scary and confusing to some people, but in fact it is a very useful data structure. To put it simply, a segment tree — is a binary tree whose nodes store aggregated data about some segment of an array. Due to this tree structure we can quickly respond to queries about arbitrary array segments, and not only respond, but also update elements.↵
↵
Imagine that we have an array and we need to repeatedly learn something about the array's sub segments, for example, the sum of elements, minimum, maximum, number of some values, etc. A segment tree allows us to do such queries very quickly — usually in O(log n) per query instead of a trivial O(n) enumeration. At the same time, it is quite flexible, supports changing individual elements, and with additional tricks (lazy propagations) can even mass update entire ranges in the same logarithmic time. In general, a segment tree can optimize a program algorithm quite well when conventional arrays and sorts are no longer sufficient.↵
↵
_Example of a segment tree constructed for the array arr = {1, 3, 5, 7, 9, 11}. Each node stores the sum on the corresponding segment: the root contains 36 (the sum on the whole segment [0;5]), its children are the sums on [0;2] and [3;5] (9 and 27), and so on._↵
↵
↵
↵
#### How does it work?↵
↵
We recursively split the array in half until we get to the individual elements. These elements are — leaves of the tree. Then we start “gluing” the information from bottom to top: each internal node is calculated from the two children. For example, if we need sums, then the value of the node = sum of the left son + sum of the right son. If we need minima — we take the minimum of the two children, etc. As a result, the root stores the aggregate (sum/min/max, etc.) over the entire array, and the path from the root to the leaf corresponds to dividing the segment into sub segments.↵
↵
#### When is it necessary?↵
↵
A segment tree can be used when:↵
1. You need to efficiently answer queries about subsets of array elements (sum on a segment, maximum on a segment, GCD on a segment, etc.) and individual elements or entire ranges may change between queries, i.e. the data is dynamic. In this case, simple pre-calculation of all answers will not help you↵
2. There are many queries and updates (tens and hundreds of thousands) and doing them in linear time is too slow↵
↵
Segment tree provides ~O,2025-03-19(log n) per query or update, which is usually within the limits for n and number of queries of about 10^5. At the same time, segment tree memory of ~4*n elements for an array of size n — is also quite ok.↵
↵
#### Examples of problems solved by a segment tree↵
↵
Range sums, finding the minimum/maximum on a segment, the number of certain elements on a segment, checking the ordering of a segment, even finding the k-th element. For example, with the help of a segment tree you can easily find out how many zeros there are in a given range or find the index of the k-th zero in an array. By the way, this is exactly the task we are about to consider in practice.↵
↵
## Practical part↵
↵
Let's take the problem [problem:2075F] from the recent contest [contest:2075] as an example, solving it using a segment tree and drawing an analogy in comparison with a head-on solution.↵
↵
Let's consider the solution to this problem from [user:wishgoodluck,2025-03-19] — [submission:311252841]. The idea of this algorithm is based on an “event-driven approach”. We precompute two arrays (let's call them l and r) that capture important edges in the original sequence. These arrays help to determine for which segments there is a “change” (an increase or decrease in the contribution to the final answer). Then an event vector is formed — each element of this vector specifies that some value should be added or removed at a certain segment. Finally, the final length of the desired sequence is obtained as the maximum total change.↵
↵
The key challenge is to quickly and efficiently handle the multitude of events that affect the index ranges. This is exactly what a segment tree is used for.↵
↵
In this solution, the segment tree is used for two operations:↵
↵
- Range Update. Each event from vector v specifies that either +1 or -1 should be added on the segment [l,r]. A segment tree with lazy updates allows for O(log n) per event to update the entire segment at once, without going through each element separately.↵
- Range Query. After each update we need to quickly find out what is the maximum value on the whole range. The root of the tree (Tree[1].v) always stores the maximum among all elements. This allows us to know instantly (in O(1) after O(log n) updates) the current optimal value, which is then used to compute the answer.↵
↵
Thus, the segment tree here acts as an “aggregator” of all events, accumulating their influence on the given segments and allowing us to quickly find the maximum.↵
↵
Imagine a problem where we need to update all elements of a segment at each step for each event. If the range has length m, then the naive update takes O(m) operations. Given m∼n and O(n) events, we get O(n^2) operations. This solution will quickly become time unacceptable even for medium-sized input data.↵
↵
In contrast, the segmental tree allows whole ranges to be updated in ↵
O(log n) due to lazy propagation. Thus, even if there are many events, the overall complexity becomes ↵
O(n*log n).↵
↵
## Pitfalls and tips↵
↵
Segment tree — thing is powerful, but you can make some typical mistakes when implementing it:↵
↵
- Incorrect merging of results. Forget that you need to summarize children, or confuse left/right and the whole logic will be destroyed. Carefully define what the node stores and how it is derived from the children's information.↵
- Segment Boundaries. It's easy to make mistakes with the indices left, right, and middle. Assume that the segment [left..right] is inclusive. Then middle = (left+right)/2 — left part [left..middle], right part [middle+1..right]. If you forget +1 where you need it, you will get overlapping or missing indexes. Tip: debug on a small array, for example, n=4 and write out the segments of each node on a piece of paper, check that they cover the array without gaps and overlaps.↵
- Recursion vs iteration. We considered a recursive solution for ease of understanding, but when n ~ 10^5 the depth of recursion is ~17 is ok, but if n ~ 10^7, the depth is ~24, it's still ok. When n is very large, and especially when the number of operations is large, iterative implementations are sometimes preferred to avoid overhead and risk of stack overflow↵
- Lazy updates. In our example we just used them, updating a whole range at once. Note that implementing lazy tags is more complicated — it's easy to mess with propagating changes to children. If the task requires a segmenter with lazy, test on simple examples hard. Typical mistakes: forgot to run a lazy tag before further descent or before counting in a node — you will get incorrect data. Tip: write a separate push(v) function to propagate the tag from node v to children, and call it where needed, e.g. before moving to subtrees.↵
- Choosing between Fenwick (BIT) and segment tree. They are often interchangeable for simple problems on sums, ordinal statistics. Fenwick is easier to code and requires ~n,2025-03-19 memory, but the segment tree is more versatile, supporting complex merge operations. If the problem allows Fenwick and you don't want to spend time implementing the tree — go ahead with Fenwick, but segment tree — must know for Div1-Div2 level.↵
↵
Finally, I'll give you a little hint — if the problem simply requires multiple sum queries on a segment without updates, you don't need a segment tree, it will be enough to calculate prefix sums for O(n) in advance and then answer each query for O(1).
↵
Если вы давно решаете задачи Div1-Div2 на Codeforces, то наверняка уже слышали про **сегментное дерево**. Звучит возможно для кого-то страшно и не понятно, но на деле это очень полезная структура данных. Проще говоря, сегментное дерево — это такое бинарное дерево, в узлах которого хранятся агрегированные данные о каком-то отрезке массива. За счёт этой древовидной структуры мы можем быстро отвечать на запросы о произвольных сегментах массива да и не только отвечать, но и обновлять элементы.↵
↵
Представьте, что у нас есть массив, и требуется многократно узнавать что-то про подотрезки этого массива, например, сумму элементов, минимум, максимум, количество каких-то значений и т.д. Сегментное дерево позволяет делать такие запросы очень быстро — обычно за O(log n) на каждый запрос вместо тривиального O(n) перебора. При этом оно достаточно гибкое, поддерживает изменение отдельных элементов, а с дополнительными трюками (ленивые пропагации) может даже массово обновлять целые диапазоны за то же логарифмическое время. В общем, сегментник может довольно хорошо оптимизировать алгоритм программы, когда обычных массивов и сортировок уже не хватает.↵
↵
_Пример сегментного дерева, построенного для массива arr = {1, 3, 5, 7, 9, 11}. Каждый узел хранит сумму на соответствующем отрезке: корень содержит 36 (сумма на всём отрезке [0;5]), его дети – суммы на [0;2] и [3;5] (9 и 27) и так далее._↵
↵
↵
↵
#### Как это работает?↵
↵
Мы рекурсивно делим массив пополам, пока не дойдём до отдельных элементов. Эти элементы — листья дерева. Затем начинаем “склеивать” информацию снизу вверх: каждый внутренний узел вычисляется из двух дочерних. Например, если нам нужны суммы, то значение узла = сумма левого сына + сумма правого сына. Если нужны минимумы — берём минимум из двух детей, и т.д. В итоге корень хранит агрегат (сумму/мин/макс и пр.) по всему массиву, а путь от корня к листу соответствует делению отрезка на подотрезки.↵
↵
#### Когда это нужно?↵
↵
Сегментное дерево может быть использовано, когда:↵
1. Нужно эффективно отвечать на запросы о подмножествах элементов массива (сумма на отрезке, максимум на отрезке, НОД на отрезке и т.п.) и при этом между запросами могут происходить изменения отдельных элементов или целых диапазонов, то есть данные динамические. В таком случае простое предвычисление всех ответов не поможет↵
2. Запросов и обновлений много (десятки и сотни тысяч) и делать их за линейное время слишком медленно↵
↵
Сегментное дерево обеспечивает ~O,2025-03-19(log n) на один запрос или обновление, что обычно укладывается в лимиты при n и количестве запросов порядка 10^5. При этом память сегментника ~4*n элементов для массива размера n — тоже вполне ок.↵
↵
#### Примеры задач, решаемых сегментным деревом↵
↵
Диапазонные суммы, поиск минимума/максимума на отрезке, количество определённых элементов на отрезке, проверка упорядоченности сегмента, даже поиск k-го по счёту элемента. Например, с помощью сегментного дерева можно легко узнать, сколько нулей в заданном диапазоне или найти индекс k-го нуля в массиве. Кстати, именно такую задачу мы сейчас рассмотрим на практике.↵
↵
## Практическая часть↵
↵
Давайте на примере рассмотрим задачу [problem:2075F] с недавнего контеста [contest:2075], решив её при помощи сегментного дерева и проведём аналогию в сравнении с решением "в лоб".↵
↵
Рассмотрим решение данной задачи от [user:wishgoodluck,2025-03-19] — [submission:311252841]. Идея данного алгоритма основана на «событийном подходе». Мы предварительно вычисляем два массива (назовём их l и r), которые фиксируют важные границы в исходной последовательности. Эти массивы помогают определить, для каких отрезков происходит «изменение» (увеличение или уменьшение вклада в итоговый ответ). Затем формируется вектор событий — каждый элемент этого вектора задаёт, что на определённом отрезке надо добавить или убрать некоторое значение. В финале итоговая длина искомой последовательности получается как максимальное суммарное изменение.↵
↵
Ключевая задача заключается в том, чтобы быстро и эффективно обрабатывать множество событий, которые влияют на диапазоны индексов. Именно для этого и используется сегментное дерево.↵
↵
В данном решении сегментное дерево применяется для двух операций:↵
↵
- Диапазонное обновление (Range Update). Каждое событие из вектора v задаёт, что на отрезке [l,r] нужно прибавить либо +1, либо -1. Сегментное дерево с ленивыми обновлениями позволяет за O(log n) за одно событие обновить сразу весь отрезок, не проходясь по каждому элементу отдельно.↵
- Запрос максимума (Range Query). После каждого обновления нам нужно быстро узнать, каково максимальное значение на всём диапазоне. Корень дерева (Tree[1].v) всегда хранит максимум среди всех элементов. Это позволяет мгновенно (за O(1) после O(log n) обновлений) узнать текущее оптимальное значение, которое потом используется для вычисления ответа.↵
↵
Таким образом, сегментное дерево здесь выступает как «агрегатор» всех событий, аккумулируя их влияние на заданных отрезках и позволяя быстро находить максимум.↵
↵
Представьте себе задачу, где нужно на каждом шаге для каждого события обновить все элементы отрезка. Если диапазон имеет длину m, то наивное обновление занимает O(m) операций. При m∼n и O(n) событиях получаем O(n^2) операций. Это решение быстро станет неприемлемым по времени даже для средних размеров входных данных.↵
↵
В отличие от этого, сегментное дерево позволяет обновлять целые диапазоны за ↵
O(log n) благодаря ленивой пропагации. Таким образом, даже если событий много, общая сложность становится ↵
O(n*log n).↵
↵
## Подводные камни и советы↵
↵
Сегментное дерево — штука мощная, но при реализации можно допустить несколько типовых ошибок:↵
↵
- Неправильное слияние результатов. Забудете, что нужно суммировать детей, или перепутаете левый/правый и вся логика разрушится. Внимательно определяйте, что хранит узел, и как это получается из информации детей.↵
- Границы отрезков. Легко ошибиться с индексами left, right и middle. Условились, что сегмент [left..right] включительный. Тогда middle = (left+right)/2 – левая часть [left..middle], правая [middle+1..right]. Если забудете +1 где нужно – получите перекрывающиеся или пропущенные индексы. Совет: отладьте на маленьком массиве, например, n=4 и выпишите на бумажке сегменты каждого узла, проверьте, что покрывают массив без пробелов и наложений.↵
- Рекурсия vs итерация. Мы рассмотрели рекурсивное решение для простоты понимания, но при n ~ 10^5 глубина рекурсии ~17 – это ок, а вот если бы n ~ 10^7, глубина ~24, всё ещё ок. При сильно больших n и особенно при большом количестве операций иногда предпочитают итеративные реализации во избежание накладных расходов и риска переполнения стека.↵
- Ленивые обновления. В нашем примере мы как раз их использовали, обновляя сразу целый диапазон. Обратите внимание, что реализация ленивых тегов сложнее — легко напутать с распространением изменений на детей. Если задача требует сегментник с lazy, тестируйте на простых примерах усиленно. Типичные ошибки: забыли запушить лейзи-тег перед дальнейшим спуском или перед подсчётом в узле — получите некорректные данные. Совет: написать отдельную функцию push(v) для распространения тега из узла v на детей, и вызывать где нужно, например перед переходом в поддеревья.↵
- Выбор между Fenwick (BIT) и сегментным деревом. Часто они взаимозаменяемы для простых задач на суммы, порядковую статистику. Fenwick легче кодится и требует ~n,2025-03-19 памяти, но сегментное дерево более универсально, поддерживает сложные операций слияния. Если задача допускает Fenwick и вы не хотите тратить время на реализацию дерева — дерзайте с Fenwick, однако сегментник — must know для Div1-Div2 уровня.↵
↵
Напоследок дам небольшой лайфхак — если задача просто требует многократных запросов суммы на отрезке без обновлений, то и сегментное дерево не нужно, достаточно просто будет заранее посчитать префиксные суммы за O(n) и потом каждый запрос отвечать за
↵
If you have been solving Div1-Div2 problems on Codeforces for a long time, you have probably heard about **segment tree**. It may sound scary and confusing to some people, but in fact it is a very useful data structure. To put it simply, a segment tree — is a binary tree whose nodes store aggregated data about some segment of an array. Due to this tree structure we can quickly respond to queries about arbitrary array segments, and not only respond, but also update elements.↵
↵
Imagine that we have an array and we need to repeatedly learn something about the array's sub segments, for example, the sum of elements, minimum, maximum, number of some values, etc. A segment tree allows us to do such queries very quickly — usually in O(log n) per query instead of a trivial O(n) enumeration. At the same time, it is quite flexible, supports changing individual elements, and with additional tricks (lazy propagations) can even mass update entire ranges in the same logarithmic time. In general, a segment tree can optimize a program algorithm quite well when conventional arrays and sorts are no longer sufficient.↵
↵
_Example of a segment tree constructed for the array arr = {1, 3, 5, 7, 9, 11}. Each node stores the sum on the corresponding segment: the root contains 36 (the sum on the whole segment [0;5]), its children are the sums on [0;2] and [3;5] (9 and 27), and so on._↵
↵
↵
↵
#### How does it work?↵
↵
We recursively split the array in half until we get to the individual elements. These elements are — leaves of the tree. Then we start “gluing” the information from bottom to top: each internal node is calculated from the two children. For example, if we need sums, then the value of the node = sum of the left son + sum of the right son. If we need minima — we take the minimum of the two children, etc. As a result, the root stores the aggregate (sum/min/max, etc.) over the entire array, and the path from the root to the leaf corresponds to dividing the segment into sub segments.↵
↵
#### When is it necessary?↵
↵
A segment tree can be used when:↵
1. You need to efficiently answer queries about subsets of array elements (sum on a segment, maximum on a segment, GCD on a segment, etc.) and individual elements or entire ranges may change between queries, i.e. the data is dynamic. In this case, simple pre-calculation of all answers will not help you↵
2. There are many queries and updates (tens and hundreds of thousands) and doing them in linear time is too slow↵
↵
Segment tree provides ~O,2025-03-19(log n) per query or update, which is usually within the limits for n and number of queries of about 10^5. At the same time, segment tree memory of ~4*n elements for an array of size n — is also quite ok.↵
↵
#### Examples of problems solved by a segment tree↵
↵
Range sums, finding the minimum/maximum on a segment, the number of certain elements on a segment, checking the ordering of a segment, even finding the k-th element. For example, with the help of a segment tree you can easily find out how many zeros there are in a given range or find the index of the k-th zero in an array. By the way, this is exactly the task we are about to consider in practice.↵
↵
## Practical part↵
↵
Let's take the problem [problem:2075F] from the recent contest [contest:2075] as an example, solving it using a segment tree and drawing an analogy in comparison with a head-on solution.↵
↵
Let's consider the solution to this problem from [user:wishgoodluck,2025-03-19] — [submission:311252841]. The idea of this algorithm is based on an “event-driven approach”. We precompute two arrays (let's call them l and r) that capture important edges in the original sequence. These arrays help to determine for which segments there is a “change” (an increase or decrease in the contribution to the final answer). Then an event vector is formed — each element of this vector specifies that some value should be added or removed at a certain segment. Finally, the final length of the desired sequence is obtained as the maximum total change.↵
↵
The key challenge is to quickly and efficiently handle the multitude of events that affect the index ranges. This is exactly what a segment tree is used for.↵
↵
In this solution, the segment tree is used for two operations:↵
↵
- Range Update. Each event from vector v specifies that either +1 or -1 should be added on the segment [l,r]. A segment tree with lazy updates allows for O(log n) per event to update the entire segment at once, without going through each element separately.↵
- Range Query. After each update we need to quickly find out what is the maximum value on the whole range. The root of the tree (Tree[1].v) always stores the maximum among all elements. This allows us to know instantly (in O(1) after O(log n) updates) the current optimal value, which is then used to compute the answer.↵
↵
Thus, the segment tree here acts as an “aggregator” of all events, accumulating their influence on the given segments and allowing us to quickly find the maximum.↵
↵
Imagine a problem where we need to update all elements of a segment at each step for each event. If the range has length m, then the naive update takes O(m) operations. Given m∼n and O(n) events, we get O(n^2) operations. This solution will quickly become time unacceptable even for medium-sized input data.↵
↵
In contrast, the segmental tree allows whole ranges to be updated in ↵
O(log n) due to lazy propagation. Thus, even if there are many events, the overall complexity becomes ↵
O(n*log n).↵
↵
## Pitfalls and tips↵
↵
Segment tree — thing is powerful, but you can make some typical mistakes when implementing it:↵
↵
- Incorrect merging of results. Forget that you need to summarize children, or confuse left/right and the whole logic will be destroyed. Carefully define what the node stores and how it is derived from the children's information.↵
- Segment Boundaries. It's easy to make mistakes with the indices left, right, and middle. Assume that the segment [left..right] is inclusive. Then middle = (left+right)/2 — left part [left..middle], right part [middle+1..right]. If you forget +1 where you need it, you will get overlapping or missing indexes. Tip: debug on a small array, for example, n=4 and write out the segments of each node on a piece of paper, check that they cover the array without gaps and overlaps.↵
- Recursion vs iteration. We considered a recursive solution for ease of understanding, but when n ~ 10^5 the depth of recursion is ~17 is ok, but if n ~ 10^7, the depth is ~24, it's still ok. When n is very large, and especially when the number of operations is large, iterative implementations are sometimes preferred to avoid overhead and risk of stack overflow↵
- Lazy updates. In our example we just used them, updating a whole range at once. Note that implementing lazy tags is more complicated — it's easy to mess with propagating changes to children. If the task requires a segmenter with lazy, test on simple examples hard. Typical mistakes: forgot to run a lazy tag before further descent or before counting in a node — you will get incorrect data. Tip: write a separate push(v) function to propagate the tag from node v to children, and call it where needed, e.g. before moving to subtrees.↵
- Choosing between Fenwick (BIT) and segment tree. They are often interchangeable for simple problems on sums, ordinal statistics. Fenwick is easier to code and requires ~n,2025-03-19 memory, but the segment tree is more versatile, supporting complex merge operations. If the problem allows Fenwick and you don't want to spend time implementing the tree — go ahead with Fenwick, but segment tree — must know for Div1-Div2 level.↵
↵
Finally, I'll give you a little hint — if the problem simply requires multiple sum queries on a segment without updates, you don't need a segment tree, it will be enough to calculate prefix sums for O(n) in advance and then answer each query for O(1).
