Segment Tree এবং Fenwick Tree (বা Binary Indexed Tree) দুটি অত্যন্ত শক্তিশালী ডেটা স্ট্রাকচার যা বিশেষ করে রেঞ্জ কুয়েরি এবং রেঞ্জ আপডেট অপারেশনগুলির জন্য ব্যবহৃত হয়। এগুলি মূলত বড় ডেটা সেটে দ্রুত অগ্রগতির জন্য ডিজাইন করা হয়েছে, যেখানে একাধিক মানকে একটি নির্দিষ্ট রেঞ্জের মধ্যে সংরক্ষণ এবং পরিবর্তন করতে হয়।
Segment Tree
Segment Tree একটি বিশেষ ধরনের বিনামূলক গাছ (binary tree) যা একটি অ্যারে বা তালিকায় নির্দিষ্ট রেঞ্জের উপাদানগুলির উপর বিভিন্ন ধরনের অপারেশন (যেমন যোগফল, গড়, সর্বোচ্চ/সর্বনিম্ন মান) দ্রুত করতে ব্যবহৃত হয়।
Segment Tree এর গঠন:
- নোড: প্রতিটি নোড রেঞ্জের ফলাফল ধারণ করে, যেমন রেঞ্জের যোগফল বা সর্বোচ্চ মান।
- Leaves: পাতার নোডগুলোতে অ্যারের উপাদানগুলি সংরক্ষিত থাকে।
- Internal Nodes: অভ্যন্তরীণ নোডগুলো তাদের সন্তানের রেঞ্জের উপর নির্ভর করে মান ধারণ করে।
সুবিধা:
- O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন করতে পারে।
- এটি বড় আকারের ডেটাসেটের জন্য কার্যকরী, যেখানে একাধিক রেঞ্জ কুয়েরি এবং আপডেট করতে হয়।
উদাহরণ: Segment Tree for Range Sum Query
ধরা যাক, আমাদের একটি অ্যারে আছে, এবং আমরা বিভিন্ন রেঞ্জের যোগফল বের করতে চাই।
class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int[] arr) {
n = arr.length;
tree = new int[4 * n];
build(arr, 0, 0, n - 1);
}
// Build the segment tree
private void build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
int leftChild = 2 * node + 1;
int rightChild = 2 * node + 2;
build(arr, leftChild, start, mid);
build(arr, rightChild, mid + 1, end);
tree[node] = tree[leftChild] + tree[rightChild];
}
}
// Query the sum of range [l, r]
public int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
private int query(int node, int start, int end, int l, int r) {
if (r < start || l > end) {
return 0; // Out of range
}
if (l <= start && end <= r) {
return tree[node]; // Exact match
}
int mid = (start + end) / 2;
int leftChild = 2 * node + 1;
int rightChild = 2 * node + 2;
int leftResult = query(leftChild, start, mid, l, r);
int rightResult = query(rightChild, mid + 1, end, l, r);
return leftResult + rightResult; // Combine results
}
// Update the element at index idx to val
public void update(int idx, int val) {
update(0, 0, n - 1, idx, val);
}
private void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
int leftChild = 2 * node + 1;
int rightChild = 2 * node + 2;
if (start <= idx && idx <= mid) {
update(leftChild, start, mid, idx, val);
} else {
update(rightChild, mid + 1, end, idx, val);
}
tree[node] = tree[leftChild] + tree[rightChild]; // Recalculate node value
}
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
SegmentTree st = new SegmentTree(arr);
System.out.println("Sum of range (1, 3): " + st.query(1, 3)); // Output: 15
st.update(1, 10); // Update arr[1] = 10
System.out.println("Sum of range (1, 3) after update: " + st.query(1, 3)); // Output: 22
}
}
উপরের কোডের কার্যকারিতা:
- build(): Segment tree তৈরি করে।
- query(): একটি নির্দিষ্ট রেঞ্জের যোগফল বের করে।
- update(): নির্দিষ্ট ইনডেক্সে মান আপডেট করে।
Fenwick Tree (Binary Indexed Tree)
Fenwick Tree বা Binary Indexed Tree (BIT) একটি ডেটা স্ট্রাকচার যা সমষ্টি (sum) এবং আপডেট (update) অপারেশনকে দ্রুত করতে সক্ষম। এটি বিশেষত তখন কার্যকরী, যখন আমরা একটি অ্যারের মধ্যে রেঞ্জ কুয়েরি করতে চাই এবং তাতে পরিবর্তন (update) করতে চাই। Fenwick Tree তে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন O(log n) সময়ে করা যায়।
Fenwick Tree এর গঠন:
- এটি একটি অ্যারের মত গঠন, কিন্তু প্রতিটি পজিশনে প্রিসাম (prefix sum) সংরক্ষণ করা হয়।
- আপডেট অপারেশনে একটি নির্দিষ্ট পজিশনে মান যোগ/বিয়োগ করা হয় এবং আপডেট করা মান পরবর্তী পজিশনে প্রভাব ফেলতে থাকে।
সুবিধা:
- O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন করা সম্ভব।
- এটি সাধারণত ছোট আকারের ডেটাসেট এবং গতিশীল রেঞ্জ কুয়েরি সমস্যার জন্য কার্যকরী।
উদাহরণ: Fenwick Tree for Range Sum Query
class FenwickTree {
private int[] tree;
private int n;
public FenwickTree(int n) {
this.n = n;
this.tree = new int[n + 1];
}
// Update the Fenwick Tree with value at index
public void update(int index, int value) {
while (index <= n) {
tree[index] += value;
index += index & (-index); // Move to the next index
}
}
// Query the prefix sum up to index
public int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & (-index); // Move to the parent index
}
return sum;
}
// Query the range sum between two indices
public int rangeQuery(int left, int right) {
return query(right) - query(left - 1);
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {0, 1, 3, 4, 8, 6, 1, 4, 2, 3};
FenwickTree fenwickTree = new FenwickTree(arr.length);
// Build the Fenwick Tree
for (int i = 1; i < arr.length; i++) {
fenwickTree.update(i, arr[i]);
}
// Query range sum
System.out.println("Range sum (1, 5): " + fenwickTree.rangeQuery(1, 5)); // Output: 22
// Update the array
fenwickTree.update(3, 6); // arr[3] = 10
// Query range sum again
System.out.println("Range sum (1, 5) after update: " + fenwickTree.rangeQuery(1, 5)); // Output: 28
}
}
উপরের কোডের কার্যকারিতা:
- update(): একটি নির্দিষ্ট পজিশনে মান যোগ করে বা বিয়োগ করে।
- query(): একটি নির্দিষ্ট ইনডেক্স পর্যন্ত যোগফল বের করে।
- rangeQuery(): নির্দিষ্ট রেঞ্জের যোগফল বের করে।
সারাংশ
Segment Tree এবং Fenwick Tree দুটি শক্তিশালী ডেটা স্ট্রাকচার যা রেঞ্জ কুয়েরি এবং রেঞ্জ আপডেট অপারেশন দ্রুত করতে ব্যবহৃত হয়। Segment Tree আরও সাধারণ এবং জটিল কুয়েরি সমাধানে ব্যবহৃত হয়, যেখানে Fenwick Tree সহজ এবং ছোট আকারের রেঞ্জ কুয়েরি সমস্যা সমাধানে কার্যকরী। দুটি ডেটা স্ট্রাকচারই O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন করার ক্ষমতা রাখে, যা বড় ডেটা সেটে দ্রুত কর্মক্ষমতা প্রদান করে।
Read more
