Ռեկուրսիվ Հատվածներով Ծառ
Ձեզ տրված է
n տարրից կազմված զանգված: Ձեր խնդիրն է ռեկուրսիվ կերպով կառուցել հատվածներով ծառ (Segment Tree) և հաշվել ծառի յուրաքանչյուր գագաթի արժեքը: Յուրաքանչյուր գագաթի արժեքը ցույց է տալիս տվյալ գագաթին համապատասխանող ենթազանգվածի էլեմենտների գումարը:Մուտք
Մուտքի առաջին տողում տրված է ամբողջ թիվ
n (1 ≤ n ≤ 100 000), որը ցույց է տալիս զանգվածի տարրերի քանակը:Երկրորդ տողում տրված են
n բնից բաժանված整数ներ (), որոնք ներկայացնում են զանգվածի տարրերը:Ելք
Տպեք հատվածներով ծառը (Segment Tree) նրա բոլոր գագաթների արժեքներով: Ծառի յուրաքանչյուր մակարդակ պետք է տպվի առանձին տողով, իսկ նույն մակարդակի գագաթները պետք է բաժանվեն բացատներով:
Օրինակներ
Մուտք | Ելք |
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