सी ++ में बाइनरी इंडेक्स ट्री या फेनविक ट्री?

संख्याओं की एक सपाट सरणी के साथ तुलना करने के मामले में, फेनविक ट्री दो कार्यों के बीच एक बेहतर संतुलन का परिणाम देता है:तत्व अद्यतन और उपसर्ग योग गणना। एम संख्याओं की एक सपाट सरणी के मामले में, हम या तो तत्वों को स्टोर कर सकते हैं, या उपसर्ग रकम। पहले उदाहरण के मामले में, उपसर्ग योगों की गणना के लिए रैखिक समय की आवश्यकता होती है; दूसरे उदाहरण के मामले में, सरणी तत्वों को संशोधित या अद्यतन करने के लिए रैखिक समय की आवश्यकता होती है (दोनों उदाहरणों में, अन्य ऑपरेशन निरंतर समय में पूरा किया जा सकता है)। फेनविक पेड़ दोनों कार्यों को ओ (लॉग एम) समय में पूरा करने की अनुमति देते हैं। यह एक पेड़ के रूप में संख्याओं का प्रतिनिधित्व करके प्राप्त किया जाता है, जहां प्रत्येक नोड के मूल्य को उस उपट्री में संख्याओं के योग के रूप में माना जाता है। वृक्ष संरचना केवल ओ (लॉग एम) नोड एक्सेस का उपयोग करके संचालन को पूरा करने की अनुमति देती है।

एक-आधारित सरणी पर विचार करके, एक फेनविक पेड़ को सबसे आसानी से समझा जा सकता है। प्रत्येक तत्व जिसका सूचकांक j 2 की शक्ति है, में पहले j तत्वों का योग होता है। जिन तत्वों के सूचकांक 2 की दो (विशिष्ट) शक्तियों के योग को इंगित करते हैं, उनमें 2 की पूर्ववर्ती शक्ति के बाद से तत्वों का योग होता है। मूल रूप से, प्रत्येक तत्व में पेड़ में अपने माता-पिता के बाद से मूल्यों का योग होता है, और वह माता-पिता है इंडेक्स में न्यूनतम या कम से कम महत्वपूर्ण बिट को साफ़ करके पाया जाता है।

किसी भी स्थिति या सूचकांक के योग की गणना करने के लिए, स्थिति या सूचकांक के द्विआधारी विस्तार पर विचार करें, और उन तत्वों को जोड़ें जो द्विआधारी रूप में प्रत्येक 1 बिट के अनुरूप हों।

उदाहरण के लिए, मान लीजिए कि कोई पहले ग्यारह मानों के योग की गणना करना चाहता है। ग्यारह बाइनरी में 1011 है। इसमें तीन 1 बिट होते हैं, इसलिए तीन तत्वों को जोड़ा जाना चाहिए:1000, 1010, और 1011। इनमें क्रमशः 1-8, 9-10 और 11 के मानों का योग होता है।

एक साधारण सी कार्यान्वयन इस प्रकार है।

उदाहरण

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
   int sum = 0;
   while (i > 0)
   sum += A1[i], i -= LSB(i);
   return sum;
}
void add(int i, int k) // Adds k to element with index i{
   while (i < SIZE)
   A1[i] += k, i += LSB(i);
}