একটি সেগমেন্ট ট্রি এবং একটি Fenwick ট্রি (Binary Indexed Tree, BIT) উভয়ই রেঞ্জ কোয়েরি (যেমন [l, r] এর উপর যোগফল) এবং পয়েন্ট আপডেট কে O(log n) এ উত্তর দেয়, যা বোকা স্ক্যানের জন্য O(n) বা prefix-sum অ্যারের জন্য O(n) আপডেটের বিপরীতে।
একটি সেগমেন্ট ট্রি এবং একটি Fenwick ট্রি (Binary Indexed Tree, BIT) উভয়ই রেঞ্জ কোয়েরি (যেমন [l, r] এর উপর যোগফল) এবং পয়েন্ট আপডেট কে O(log n) এ উত্তর দেয়, যা বোকা স্ক্যানের জন্য O(n) বা prefix-sum অ্যারের জন্য O(n) আপডেটের বিপরীতে।
Array + many "sum of range [l,r]" and "update index i" calls:
naive prefix sums: query O(1) but UPDATE is O(n)
segment/Fenwick: query O(log n) AND update O(log n)
class Fenwick:
def __init__(self, n):
self.t = [0]*(n+1)
def update(self, i, delta): # O(log n)
i += 1
while i < len(self.t):
self.t[i] += delta
i += i & (-i) # jump to next responsible node
def prefix(self, i): # sum of [0..i], O(log n)
i += 1; s = 0
while i > 0:
s += self.t[i]
i -= i & (-i)
return s
def range_sum(self, l, r):
return self.prefix(r) - self.prefix(l-1)
একটি সেগমেন্ট ট্রি একটি বাইনারি ট্রিতে প্রতিটি অ্যারে সেগমেন্টের জন্য একটি সমষ্টি সংরক্ষণ করে, যেকোনো সহযোগী অপারেশন (যোগফল, ন্যূনতম, সর্বোচ্চ, gcd) সমর্থন করে এবং, lazy propagation সহ, রেঞ্জ আপডেট ও সমর্থন করে।
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | সেগমেন্ট ট্রি | |
|---|---|---|
| কোয়েরি / আপডেট | O(log n) | O(log n) |
| স্থান | O(n) | O(2n) |
| অপারেশন | যোগফল (বিপরীতযোগ্য) | যেকোনো সহযোগী অপ |
| রেঞ্জ আপডেট | কঠিন | সহজ (lazy propagation) |
| কোড আকার | ক্ষুদ্র | বৃহত্তর |
এই স্ট্রাকচারগুলি "একটি মান আপডেট করুন, তারপর একটি রেঞ্জ জুড়ে একটি সমষ্টি কোয়েরি করুন" দ্রুত করে — যা প্রতিযোগিতামূলক প্রোগ্রামিং, বিশ্লেষণ উইন্ডো এবং ব্যবধান সমস্যার জন্য অপরিহার্য।
তাদের মধ্যে নির্বাচন করা একটি ট্রেড-অফ: একটি Fenwick ট্রি যোগফলের জন্য ছোট এবং দ্রুত, যখন একটি সেগমেন্ট ট্রি min/max/রেঞ্জ-আপডেট ওয়ার্কলোডের জন্য আরও নমনীয়।