সেগমেন্ট ট্রি এবং ফেনউইক ট্রি (বা বিট ট্রি) হল দুইটি ডেটা স্ট্রাকচার যা অ্যারে বা তালিকা থেকে বিভিন্ন রেঞ্জ কোয়েরি (range query) পরিচালনা এবং আপডেট করার জন্য ব্যবহৃত হয়। উভয়ই কার্যকরী এবং বিভিন্ন সমস্যা সমাধানের জন্য ব্যবহৃত হয়।
১. সেগমেন্ট ট্রি
সেগমেন্ট ট্রি একটি বাইনারি ট্রি যা একটি অ্যারের সেগমেন্টের উপরে বিভিন্ন অপারেশন, যেমন যোগফল, গুণফল, মিনিমাম, অথবা ম্যাক্সিমাম খোঁজার জন্য ব্যবহৃত হয়। এটি একটি নোডের মধ্যে একটি সেগমেন্টের সংক্ষিপ্ত তথ্য ধারণ করে এবং এটি রেঞ্জ কোয়েরি এবং আপডেটের জন্য কার্যকর।
বৈশিষ্ট্য:
- গঠন: প্রতিটি নোড একটি নির্দিষ্ট সেগমেন্টের তথ্য ধারণ করে।
- দৈর্ঘ্য: গাছের উচ্চতা সাধারণত O(logn)O(logn) হয়, যেখানে nn হলো অ্যারের আকার।
- আপডেট এবং কোয়েরি: উভয় অপারেশনই O(logn)O(logn) সময়ে করা যায়।
উদাহরণ (Python Implementation):
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (2 * self.n)
self.build(arr)
def build(self, arr):
# Leaf nodes
for i in range(self.n):
self.tree[self.n + i] = arr[i]
# Internal nodes
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
def update(self, idx, value):
# Update leaf node
idx += self.n
self.tree[idx] = value
# Update internal nodes
while idx > 1:
idx //= 2
self.tree[idx] = self.tree[idx * 2] + self.tree[idx * 2 + 1]
def query(self, left, right):
# Query sum in the interval [left, right)
result = 0
left += self.n
right += self.n
while left < right:
if left % 2:
result += self.tree[left]
left += 1
if right % 2:
right -= 1
result += self.tree[right]
left //= 2
right //= 2
return result
# উদাহরণ ব্যবহার
arr = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(arr)
print("Sum of values in range [1, 5):", seg_tree.query(1, 5)) # আউটপুট হবে 24
seg_tree.update(3, 10) # arr[3] কে 10 এ আপডেট
print("Sum of values in range [1, 5) after update:", seg_tree.query(1, 5)) # আউটপুট হবে 27
২. ফেনউইক ট্রি (Fenwick Tree)
ফেনউইক ট্রি, যাকে বিট ট্রি (Binary Indexed Tree) বলা হয়, একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা অ্যারের উপরে রেঞ্জ কোয়েরি এবং আপডেট অপারেশন করতে ব্যবহৃত হয়। এটি সেগমেন্ট ট্রির চেয়ে সামান্য বেশি স্থান অর্থনৈতিক এবং কিছু পরিস্থিতিতে সহজ।
বৈশিষ্ট্য:
- গঠন: প্রতিটি নোড একটি নির্দিষ্ট ইনডেক্সের জন্য যোগফল ধারণ করে।
- দৈর্ঘ্য: গাছের উচ্চতা O(logn)O(logn) হয়।
- আপডেট এবং কোয়েরি: উভয় অপারেশনই O(logn)O(logn) সময়ে করা যায়।
উদাহরণ (Python Implementation):
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index, value):
# Update the value at the specified index
while index <= self.size:
self.tree[index] += value
index += index & -index
def query(self, index):
# Query the prefix sum from 1 to index
result = 0
while index > 0:
result += self.tree[index]
index -= index & -index
return result
def range_query(self, left, right):
return self.query(right) - self.query(left - 1)
# উদাহরণ ব্যবহার
arr = [1, 3, 5, 7, 9, 11]
fenwick_tree = FenwickTree(len(arr))
for idx, value in enumerate(arr):
fenwick_tree.update(idx + 1, value)
print("Sum of values in range [1, 5]:", fenwick_tree.range_query(1, 5)) # আউটপুট হবে 24
fenwick_tree.update(4, 3) # arr[3] কে 10 এ আপডেট
print("Sum of values in range [1, 5] after update:", fenwick_tree.range_query(1, 5)) # আউটপুট হবে 27
সারসংক্ষেপ
- সেগমেন্ট ট্রি:
- একটি বাইনারি ট্রি যা একটি অ্যারের বিভিন্ন সেগমেন্টের উপর কার্যকরী অপারেশন করে।
- আপডেট এবং কোয়েরি অপারেশন O(log n) সময়ে করা যায়।
- ফেনউইক ট্রি:
- একটি স্পেশালাইজড ডেটা স্ট্রাকচার যা রেঞ্জ কোয়েরি এবং আপডেটের জন্য ব্যবহৃত হয়।
- সেগমেন্ট ট্রির তুলনায় কিছু পরিস্থিতিতে বেশি স্থান অর্থনৈতিক।
এই ডেটা স্ট্রাকচারগুলি টেক্সট প্রক্রিয়াকরণ, ডেটা বিশ্লেষণ, এবং অন্যান্য সমস্যায় ব্যবহৃত হয় যেখানে রেঞ্জ কোয়েরি এবং আপডেটের প্রয়োজন হয়। আপনি যদি এই বিষয়ে আরও বিস্তারিত আলোচনা বা উদাহরণ চান, তাহলে জানাতে পারেন!
