EN
RU
ES
ZH
FR
DE
PT
AR
HI
Recursive construction of a balanced tree from prefix sums
C++
Hard
recursion
Task «Recursive construction of a balanced tree from prefix sums»
Given an array of integers A of size N. It is required to recursively build a binary tree, where each node contains the prefix sum of elements on the interval [l, r), as well as the indices l and r. The root corresponds to the interval [0, N). Recursively divide the interval in half (left half [l, mid), right half [mid, r)) until the interval length becomes 1. For each node, compute the sum of elements in its interval. Output the tree in depth-first order (pre-order): for each node, output l, r, and the sum. Use recursion. N <= 100, numbers in the array modulo <= 10^6.
Input Format
First line: integer N (1 <= N <= 100). Second line: N integers A[i] (-10^6 <= A[i] <= 10^6).
Output Format
For each node in pre-order order, output three numbers: l, r, sum. Each node on a separate line. If the segment is empty (l == r), output nothing.
Examples
Example 1
INPUT
4
1 2 3 4
OUTPUT
0 4 10
0 2 3
0 1 1
1 2 2
2 4 7
2 3 3
3 4 4
Example 2
INPUT
2
-5 5
OUTPUT
0 2 0
0 1 -5
1 2 5
main.cpp