संख्याओं के एक फ्लैट सरणी की तुलना में, फेनविक ट्री दो ऑपरेशन्स के बीच बेहतर संतुलन प्रदान करता है: तत्व अद्यतन और प्रीफिक्स सम गणना। m संख्याओं के फ्लैट सरणी के मामले में, हम या तो तत्वों को संग्रहीत कर सकते हैं, या प्रीफिक्स योग को। पहले उदाहरण में, प्रीफिक्स योग की गणना के लिए रैखिक समय की आवश्यकता होती है; दूसरे उदाहरण में, सरणी तत्वों को संशोधित या अद्यतन करने के लिए रैखिक समय की आवश्यकता होती है (दोनों उदाहरणों में, अन्य ऑपरेशन को स्थिर समय में पूरा किया जा सकता है)। फेनविक ट्री दोनों ऑपरेशन्स को O(log m) समय में पूरा करने की अनुमति देते हैं। यह संख्याओं को एक ट्री के रूप में प्रस्तुत करके प्राप्त किया जाता है, जहां प्रत्येक नोड का मान उस सबट्री में संख्याओं के योग के रूप में माना जाता है। ट्री संरचना ऑपरेशन्स को केवल O(log m) नोड एक्सेस का उपयोग करके पूरा करने की अनुमति देती है।
एक-आधारित सरणी पर विचार करके, एक फेनविक ट्री को सबसे आसानी से समझा जा सकता है। प्रत्येक तत्व जिसका इंडेक्स j 2 की घात है, पहले j तत्वों का योग समाहित करता है। जिन तत्वों के इंडेक्स दो (अलग) 2 की घातों के योग को दर्शाते हैं, उनमें पिछली 2 की घात के बाद से तत्वों का योग होता है। मूल रूप से, प्रत्येक तत्व अपने पैरेंट के बाद से मानों के योग को समाहित करता है, और उस पैरेंट को इंडेक्स में न्यूनतम या लीस्ट-सिग्निफिकेंट बिट को क्लियर करके पाया जाता है।
किसी दिए गए स्थान या इंडेक्स तक योग की गणना करने के लिए, स्थान या इंडेक्स के बाइनरी विस्तार पर विचार करें, और उन तत्वों को जोड़ें जो बाइनरी रूप में प्रत्येक 1 बिट से मेल खाते हैं।
उदाहरण के लिए, मान लीजिए कोई पहले ग्यारह मानों का योग निकालना चाहता है। ग्यारह बाइनरी में 1011 है। इसमें तीन 1 बिट्स हैं, इसलिए तीन तत्वों को जोड़ा जाना चाहिए: 1000, 1010, और 1011। इनमें क्रमशः मान 1-8, 9-10, और 11 के योग होते हैं।
एक सरल C कार्यान्वयन निम्नानुसार है।
उदाहरण
#define LSB(i) ((i) & -(i)) // न्यूनतम या लीस्ट सिग्निफिकेंट बिट को छोड़कर सभी बिट्स को शून्य करता है int A1[SIZE]; int sum(int i) // इंडेक्स 1 से i तक का योग लौटाता है{ int sum = 0; while (i > 0) sum += A1[i], i -= LSB(i); return sum; } void add(int i, int k) // इंडेक्स i वाले तत्व में k जोड़ता है{ while (i < SIZE) A1[i] += k, i += LSB(i); }