সংখ্যার সমতল অ্যারের সাথে তুলনা করার ক্ষেত্রে, ফেনউইক ট্রি দুটি ক্রিয়াকলাপের মধ্যে অনেক ভাল ভারসাম্যের ফলাফল দেয়:উপাদান আপডেট এবং উপসর্গ যোগফল গণনা। m সংখ্যার সমতল অ্যারের ক্ষেত্রে, আমরা হয় উপাদান সংরক্ষণ করতে পারি, অথবা উপসর্গের যোগফল। প্রথম উদাহরণের ক্ষেত্রে, উপসর্গ যোগফল গণনা করার জন্য রৈখিক সময় প্রয়োজন; দ্বিতীয় দৃষ্টান্তের ক্ষেত্রে, অ্যারের উপাদানগুলিকে সংশোধন বা আপডেট করার জন্য রৈখিক সময়ের প্রয়োজন (উভয় ক্ষেত্রেই, অন্যান্য ক্রিয়াকলাপ ধ্রুবক সময়ে সম্পন্ন করা যেতে পারে)। ফেনউইক গাছ উভয় অপারেশনকে O(লগ মি) সময়ে সম্পন্ন করার অনুমতি দেয়। এটি একটি ট্রি হিসাবে সংখ্যাগুলিকে উপস্থাপন করে প্রাপ্ত করা হয়, যেখানে প্রতিটি নোডের মানটিকে সেই সাবট্রিতে থাকা সংখ্যার যোগফল হিসাবে বিবেচনা করা হয়। গাছের কাঠামো শুধুমাত্র O(log m) নোড অ্যাক্সেস ব্যবহার করে কাজগুলি সম্পন্ন করার অনুমতি দেয়৷
একটি এক-ভিত্তিক অ্যারে বিবেচনা করে, একটি ফেনউইক গাছ সবচেয়ে সহজে বোঝা যায়। প্রতিটি উপাদান যার সূচী 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);
}
