পরিচয়
ফ্ল্যাট অ্যারে তুলনায় ফেনউইক ট্রি (Fenwick Tree) এলিমেন্ট আপডেট এবং প্রিফিক্স সাম কম্পিউটেশন-এ উভয় অপারেশনে ভালো ব্যালেন্স প্রদান করে। ফ্ল্যাট অ্যারেতে যেকোনো একটি অপারেশন লিনিয়ার টাইম নেয়, অন্যটি কনস্ট্যান্ট টাইমে হয়। ফেনউইক ট্রি দুটি অপারেশনই O(log m) টাইমে করে।
এটি সংখ্যাগুলোকে একটি ট্রি হিসেবে রিপ্রেজেন্ট করে যেখানে প্রতিটি নোডের ভ্যালু সাবট্রির সংখ্যাগুলোর যোগফল। ট্রি স্ট্রাকচারের কারণে O(log m) নোড অ্যাক্সেসে অপারেশন সম্পন্ন হয়।
কর্যক্রম
ওয়ান-বেসড অ্যারে বিবেচনা করলে: যেসব ইনডেক্স j যা ২-এর ঘাত, সেগুলো প্রথম j টি এলিমেন্টের যোগফল ধারণ করে। যেসব ইনডেক্স দুটি ভিন্ন ২-এর ঘাতের যোগফল, সেগুলো পূর্ববর্তী ২-এর ঘাত থেকে এলিমেন্টের যোগফল ধারণ করে। মূলত প্রতিটি এলিমেন্ট তার প্যারেন্ট থেকে বর্তমান পর্যন্ত মানগুলোর যোগফল ধারণ করে, প্যারেন্ট খুঁজে বের করা হয় ইনডেক্সের লিস্ট সিগনিফিক্যান্ট বিট ক্লিয়ার করে।
কোনো পজিশন পর্যন্ত যোগফল বের করতে পজিশনের বাইনারি এক্সপ্যানশনে ১ বিটগুলো কোরেসপন্ডিং এলিমেন্ট যোগ করতে হয়।
উদাহরণ: প্রথম ১১টি ভ্যালুর যোগফল বের করতে। ১১ বাইনারিতে 1011। তিনটি ১ বিট আছে, তাই তিনটি এলিমেন্ট যোগ করতে হবে: 1000, 1010, 1011। এগুলো যথাক্রমে ১-৮, ৯-১০, ১১ নম্বর ভ্যালুর যোগফল।
সিম্পল 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);
}
