ট্রিপড়তে ৬ মিনিট লাগবে

ফেনউইক ট্রি (Fenwick Tree / BIT)

সেগমেন্ট ট্রির চেয়েও সহজে এবং বিটের জাদুতে শুরু থেকে শেষ পর্যন্ত যেকোনো যোগফল বের করা — মাত্র O(log n) স্পিডে

build: O(n log n)prefix query: O(log n)point update: O(log n)space: O(n)

ফেনউইক ট্রি (Fenwick tree), যাকে বাইনারি ইনডেক্সড ট্রি (Binary Indexed Tree বা BIT)-ও বলা হয়, হলো এমন একটা ডেটা স্ট্রাকচার যেটা দিয়ে খুব দ্রুত (O(log n) স্পিডে) প্রিফিক্স সাম (শুরু থেকে কোনো একটা পয়েন্ট পর্যন্ত যোগফল) বের করা যায় এবং যেকোনো একটা পয়েন্টের ডেটা আপডেট করা যায়। মজার ব্যাপার হলো, এর জন্য সত্যিকারের গাছ বা ট্রি-এর মতো কোনো জটিল পয়েন্টার বা স্ট্রাকচার লাগে না — কাজটা জাস্ট একটা সাধারণ অ্যারে দিয়েই হয়ে যায়!

১৯৯৪ সালে পিটার ফেনউইক (Peter Fenwick) এই জাদুকরী আইডিয়াটা বের করেন। সেগমেন্ট ট্রির মতোই ফাস্ট পারফরম্যান্স দিলেও, এর কোড অনেক সোজা এবং মেমোরিও কম লাগে। এর আসল রহস্য বা ম্যাজিকটা লুকিয়ে আছে বাইনারি নাম্বারের সবচেয়ে পেছনের ১-বিট (Least Significant Bit বা LSB) নিয়ে কারসাজির মধ্যে।

এটা আসল কোন সমস্যার সমাধান করে?

ধরুন আপনার কাছে একটা অ্যারে আছে আর আপনাকে দুটো কাজ খুব ঘন ঘন করতে হবে:

১ নম্বর ইনডেক্স থেকে 'i' নম্বর ইনডেক্স পর্যন্ত সব সংখ্যার যোগফল (prefix sum) বের করা: sum(1, i)
অ্যারের যেকোনো একটা নির্দিষ্ট সংখ্যা বা arr[i]-এর সাথে ডেল্টা (delta) বা নতুন কোনো ভ্যালু যোগ করা: arr[i] += delta

নরমাল অ্যারে দিয়ে কাজ করলে কোয়ারিতে বা যোগফল বের করতে O(n) সময় লাগে। আগে থেকে যোগফল বের করে রাখলে (Prefix sums Array) কোয়ারি O(1) হলেও আপডেট করতে আবার O(n) লেগে যায়। কিন্তু ফেনউইক ট্রি এই দুটো কাজই O(log n) স্পিডে করে দেয়!

◈ Explore Fenwick tree

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দ্রষ্টব্য: ফেনউইক ট্রির আসল ম্যাজিক: BIT-অ্যারের i নম্বর ঘরে ঠিক ওই i নম্বর ইনডেক্সে শেষ হওয়া 'lowbit(i)'-সংখ্যক এলিমেন্টের যোগফল সেভ করা থাকে। (যেখানে lowbit(i) = i & (-i) হলো সবচেয়ে পেছনের সেট করা ১-বিট)। আর এই ট্রির ভেতর দিয়ে ওপরে ওঠা বা নিচে নামা বলতে জাস্ট এই LSB-টাকে যোগ বা বিয়োগ করাকেই বোঝায়!

কীভাবে কাজ করে: lowbit ট্রিক

এর কোর বা আসল অপারেশনটাই হলো lowbit(i) = i & (-i), যেটা যেকোনো সংখ্যার একদম পেছনের সেট করা ১-বিটটাকে (1-bit) আলাদা করে আনে। উদাহরণস্বরূপ: lowbit(6) = 6 & (-6) = ...11111010 এর সাথে 00000110-এর AND অপারেশন = 000000010 = 2।

BIT অ্যারের প্রতিটা ইনডেক্স i মূলত [i - lowbit(i) + 1, i] রেঞ্জের সংখ্যাগুলোর যোগফল ধরে রাখে:

BIT[1] = arr[1] (lowbit(1)=1, তাই শুধু ১টা এলিমেন্ট ধরে)
BIT[2] = arr[1]+arr[2] (lowbit(2)=2, তাই ২টা এলিমেন্ট ধরে)
BIT[4] = arr[1]+arr[2]+arr[3]+arr[4] (lowbit(4)=4, তাই ৪টা এলিমেন্ট ধরে)
BIT[6] = arr[5]+arr[6] (lowbit(6)=2, তাই ২টা এলিমেন্ট ধরে)

প্রিফিক্স সাম (Prefix sum) বের করা

sum(1, i) বের করতে চাইলে: i থেকে শুরু করুন, BIT[i]-এর ভ্যালু যোগ করুন, তারপর লাফ দিয়ে i - lowbit(i)-তে চলে যান, এভাবে i-এর মান ০ হওয়ার আগ পর্যন্ত চলতে থাকুক।

pseudocode

def prefix_sum(i):
  total = 0
  while i > 0:
    total += BIT[i]
    i -= i & (-i)  # LSB বিয়োগ করে লাফ দেওয়া
  return total

এভাবে বড়জোর log₂(n)-বার লাফ দিতে হয় (প্রতি লাফে একটা করে ১-বিট মুছে যায়)।

পয়েন্ট আপডেট (Point update)

arr[i] এর মান delta পরিমাণ বাড়াতে চাইলে: i থেকে শুরু করুন, BIT[i]-এর সাথে delta যোগ করুন, তারপর লাফ দিয়ে i + lowbit(i)-তে চলে যান। এভাবে i-এর মান n পার না হওয়া পর্যন্ত চলতে থাকুক।

pseudocode

def update(i, delta):
  while i <= n:
    BIT[i] += delta
    i += i & (-i)  # LSB যোগ করে লাফ দেওয়া

মাঝখানের বা রেঞ্জ কোয়ারি (Range query)

l থেকে r পর্যন্ত যোগফল বের করার নিয়ম: sum(1, r) থেকে sum(1, l-1) বিয়োগ করে দিন। দুটো প্রিফিক্স কোয়ারি = কাজ শেষ সেই O(log n) স্পিডেই।

ফেনউইক বনাম সেগমেন্ট ট্রি

ফেনউইক ট্রি: কোড অনেক সোজা, মেমোরি কম লাগে, সিপিইউ-তেও ফাস্ট চলে। তবে এটা মূলত প্রিফিক্স কোয়ারি আর পয়েন্ট আপডেটের জন্যই বেস্ট।
সেগমেন্ট ট্রি: অনেক বেশি ফ্লেক্সিবল বা অলরাউন্ডার (রেঞ্জ আপডেট, রেঞ্জ Min/Max সব পারে), কিন্তু কোড একটু প্যাঁচানো আর মেমোরি বেশি খায়।

তাই যদি আপনার শুধু যোগফল (sum) আর পয়েন্ট আপডেটের দরকার হয়, তবে চোখ বন্ধ করে ফেনউইক ট্রি ব্যবহার করবেন — বাস্তবে এটা অনেক বেশি ফাস্ট আর নির্ভুলভাবে কোড করা পানির মতো সোজা।