HI
RU
EN
ES
ZH
FR
DE
PT
AR
यहाँ दिए गए प्रोग्रामिंग कार्य का हिंदी अनुवाद है: प्रीफिक्स योगों से संतुलित ट्री का पुनरावर्ती निर्माण
C++
Hard
recursion
कार्य «यहाँ दिए गए प्रोग्रामिंग कार्य का हिंदी अनुवाद है: प्रीफिक्स योगों से संतुलित ट्री का पुनरावर्ती निर्माण»
दिया गया है पूर्णांकों का एक सरणी A जिसका आकार N है। एक बाइनरी ट्री को पुनरावर्ती रूप से बनाना आवश्यक है, जहाँ प्रत्येक नोड में अंतराल [l, r) पर तत्वों का प्रीफिक्स योग, साथ ही l और r सूचकांक शामिल हों। मूल (root) अंतराल [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