Рекурсивное дерево отрезков
Вам дан массив из
n элементов. Нужно рекурсивно построить дерево отрезков (segment tree) и вычислить значение каждого узла в этом дереве. Значение каждого узла соответствует сумме подмассива, за который этот узел отвечает.Входные данные
В первой строке содержится целое число
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