Segment Tree (Дерево отрезков)
TODO: более детальное объяснение структуры segment tree
Дерево отрезков (segment tree) — это структура данных, основанная на двоичном дереве и предназначенная для представления заданного массива или списка элементов. Каждый узел этого дерева соответствует определённому отрезку или подмассиву исходного массива.
В дереве отрезков корневой узел охватывает весь массив, а листья соответствуют отдельным элементам массива. Внутренние узлы дерева представляют собой промежуточные отрезки, которые получаются путём последовательного деления исходного массива на подмассивы.
Обычно, если узел отвечает за подмассив [l, r], то его левый потомок отвечает за подмассив [l, (l+r)/2], а правый — за [(l+r)/2 + 1, r]. Такое рекурсивное деление продолжается до тех пор, пока каждый лист дерева не будет соответствовать единственному элементу исходного массива.
Хранимое в узле значение зависит от задачи или запроса, который необходимо обрабатывать. Чаще всего дерево отрезков используют для эффективного вычисления агрегирующих значений, например, суммы, минимума, максимума или результатов других операций на некотором отрезке. Значение в каждом узле получается на основе значений в его дочерних узлах.
Дерево отрезков особенно полезно, если нужно выполнять диапазонные (range) запросы или обновления элементов массива. После построения такого дерева многие операции можно делать эффективно — за O(log N), где N — это размер исходного массива.
Таким образом, дерево отрезков является мощным инструментом для работы с операциями, определяемыми на подотрезках, и даёт возможность быстро выполнять как запросы, так и обновления. Оно широко используется в большом числе задач и алгоритмов, включая интервалные запросы, обновления целых подотрезков и многое другое.
Задание: Итеративное вычисление узлов дерева отрезков
Вам дан массив из
n элементов. Требуется итеративно построить дерево отрезков и вычислить значение в каждом его узле. Значение в узле равно сумме элементов подмассива, за который этот узел отвечает.Входные данные
В первой строке входных данных задано целое число
n (1 ≤ n ≤ 100 000), обозначающее количество элементов в массиве.Во второй строке даны
n разделённых пробелами целых чисел (), которые представляют элементы массива.Выходные данные
Выведите дерево отрезков со всеми значениями узлов. Каждый уровень дерева выводите в отдельной строке, значения разделяйте пробелом.
Примеры
Входные данные | Выходные данные |
4
1 2 3 4 | 10
3 7
1 2 3 4 |
8
3 7 9 6 2 1 5 4 | 37
25 12
10 15 3 9
3 7 9 6 2 1 5 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 10 MB