RU
EN
ES
ZH
FR
DE
PT
AR
HI
Рекурсивное построение сбалансированного дерева из префиксных сумм
C++
Сложный
recursion
Задача «Рекурсивное построение сбалансированного дерева из префиксных сумм»
Дан массив целых чисел A размера N. Требуется рекурсивно построить бинарное дерево, где каждый узел содержит префиксную сумму элементов на отрезке [l, r), а также индексы l и r. Корень соответствует отрезку [0, N). Рекурсивно делите отрезок пополам (левая половина [l, mid), правая [mid, r)), пока длина отрезка не станет 1. Для каждого узла вычислите сумму элементов на его отрезке. Выведите дерево в порядке обхода в глубину (pre-order): для каждого узла выведите l, r и сумму. Используйте рекурсию. N <= 100, числа в массиве по модулю <= 10^6.
Формат ввода
Первая строка: целое N (1 <= N <= 100). Вторая строка: N целых чисел A[i] (-10^6 <= A[i] <= 10^6).
Формат вывода
Для каждого узла в порядке pre-order выводите три числа: l, r, sum. Каждый узел на отдельной строке. Если отрезок пустой (l == r), не выводите ничего.
Примеры
Пример 1
ВВОД
4
1 2 3 4
ВЫВОД
0 4 10
0 2 3
0 1 1
1 2 2
2 4 7
2 3 3
3 4 4
Пример 2
ВВОД
2
-5 5
ВЫВОД
0 2 0
0 1 -5
1 2 5
main.cpp