ট্রিপড়তে ৭ মিনিট লাগবে

সেগমেন্ট ট্রি (Segment Tree)

অ্যারের মাঝখানের যেকোনো রেঞ্জের যোগফল বের করা বা আপডেট করা — শুধু চোখের পলকে (O(log n)-এ)
build: O(n)query: O(log n)update: O(log n)space: O(n)

সেগমেন্ট ট্রি (Segment tree) হলো একটা স্পেশাল ট্রি, যেটাকে একটা সাধারণ অ্যারের ওপর ভিত্তি করে বানানো হয়। এর মূল কাজই হলো অ্যারের যেকোনো রেঞ্জের উত্তর দেওয়া (যেমন: "৩ নম্বর থেকে ৮ নম্বর ইনডেক্স পর্যন্ত সংখ্যাগুলোর যোগফল কত?") এবং অ্যারের যেকোনো একটা সংখ্যা আপডেট করা — আর এই দুটো কাজই সে মাত্র O(log n) বা চোখের পলকে করে ফেলতে পারে।

সেগমেন্ট ট্রি ছাড়া, একটা রেঞ্জের যোগফল বের করতে নরমালি O(n) সময় লাগে (কারণ লুপ চালিয়ে সব যোগ করতে হয়)। প্রিফিক্স সাম (Prefix sum) অ্যারে দিয়ে O(1)-এ কোয়ারি করা যায়, তবে আপডেটে O(n) লাগে। কিন্তু সেগমেন্ট ট্রি দিয়ে প্রথমে একবার O(n) সময় খরচ করে ট্রি-টা গুছিয়ে নিলে, এরপর হাজার হাজার রেঞ্জের প্রশ্ন করলেও সে প্রতিটার উত্তর O(log n) স্পিডেই দিয়ে দেয় — যেটা কম্পিটিটিভ প্রোগ্রামিংয়ে বিশাল একটা সুবিধা।

আসল বুদ্ধিটা হলো: ভাগ করুন আর শাসন করুন (Divide and conquer)

একটা সেগমেন্ট ট্রি মূলত আলাদা আলাদা রেঞ্জের রেজাল্ট বা যোগফল সেভ করে রাখে। ট্রির একদম মাথায় বা রুটে থাকে পুরো অ্যারের যোগফল। এরপর রুট তার রেঞ্জটাকে সমান দুই ভাগে ভাগ করে তার দুই বাচ্চাকে দিয়ে দেয়। এভাবে ভাঙতে ভাঙতে একেবারে পাতা বা লিফ (leaf) নোডগুলোতে গিয়ে অ্যারের অরিজিনাল সিঙ্গেল সংখ্যাগুলো বসে থাকে।

ধরুন ৮ সাইজের একটা অ্যারে: [১, ৩, ৫, ৭, ৯, ১১, ১৩, ১৫]

pseudocode
1
2
3
4
[০..৭] = ৬৪
          [০..৩] = ১৬        [৪..৭] = ৪৮
       [০..১]=৪  [২..৩]=১২  [৪..৫]=২০  [৬..৭]=২৮
      ১   ৩     ৫   ৭      ৯   ১১    ১৩   ১৫

এখন যদি কেউ (২ থেকে ৬)-এর যোগফল চায়: আমরা শুধু ট্রির ওপর থেকে নিচের দিকে নামবো, আর যে যে সেগমেন্টগুলো বা নোডগুলো (২ থেকে ৬) রেঞ্জের সাথে মিলে যায়, শুধু তাদের ভ্যালুগুলো যোগ করে দেব। এতে প্রতি লেভেলে বড়জোর ২টা নোডে যেতে হয় → তাই সময় লাগে মাত্র O(log n)।

◈ Explore segment tree

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

দ্রষ্টব্য: সেগমেন্ট ট্রি শুধু 'যোগফল'-এর জন্যই নয়, বরং একটা রেঞ্জের মধ্যে সবচেয়ে ছোট সংখ্যা (min), সবচেয়ে বড় সংখ্যা (max), গসাগু (GCD) বা এক্স-অর (XOR) বের করার জন্যও সমানভাবে কাজ করে — শুধু প্রতিটা নোডে কী সেভ করবেন আর ওদেরকে কীভাবে মেলাবেন, সেই নিয়মটা একটু বদলে নিলেই হলো।

ট্রি বানানো (Building the tree)

ট্রি-টা বানানো হয় একদম নিচ থেকে ওপরে (bottom-up): প্রথমে অ্যারের সংখ্যাগুলোকে পাতায় বা লিফে বসানো হয়, এরপর প্রতিটা বাপ নোড তার দুই বাচ্চার ভ্যালু যোগ করে নিজের ভ্যালু সেট করে। এর জন্য সময় লাগে O(n)।

pseudocode
1
2
3
4
5
6
7
8
def build(node, start, end):
  if start == end:
    tree[node] = arr[start]  # পাতা বা লিফ নোড
  else:
    mid = (start + end) // 2
    build(2*node, start, mid)      # বাঁ দিকের বাচ্চা
    build(2*node+1, mid+1, end)    # ডান দিকের বাচ্চা
    tree[node] = tree[2*node] + tree[2*node+1]  # দুই বাচ্চার যোগফল

রেঞ্জের উত্তর খোঁজা (Querying a range)

ধরি আমাকে [l, r] রেঞ্জের উত্তর খুঁজতে হবে: শুরু করবো রুট থেকে। বর্তমান সেগমেন্ট বা নোডটা যদি পুরোপুরি [l, r] রেঞ্জের ভেতরে থাকে, তবে ওই নোডের ভ্যালুটাই ফেরত দেব। আর যদি রেঞ্জের একদম বাইরে থাকে, তবে জিরো (0) ফেরত দেব। তা না হলে রেঞ্জটা অর্ধেক করে দুই বাচ্চার কাছে পাঠিয়ে তাদের রেজাল্ট যোগ করবো।

pseudocode
1
2
3
4
5
6
def query(node, start, end, l, r):
  if r < start or end < l: return 0         # রেঞ্জের বাইরে, ওভারল্যাপ নেই
  if l <= start and end <= r: return tree[node]  # পুরোপুরি রেঞ্জের ভেতরে
  mid = (start + end) // 2
  return query(2*node, start, mid, l, r) + \
         query(2*node+1, mid+1, end, l, r)

পয়েন্ট আপডেট (Point update)

অ্যারের কোনো একটা ইনডেক্সের ভ্যালু বদলাতে হলে (যেমন arr[i] = val): প্রথমে একদম নিচের পাতায় (leaf) গিয়ে ভ্যালুটা বদলাতে হয়, তারপর এক এক করে ওপরে উঠে তার বাপদের ভ্যালুও আপডেট করে রুটে পৌঁছাতে হয়। যেহেতু শুধু একটা লাইন ধরে ওপরে উঠতে হয়, তাই সময় লাগে O(log n)।

লেজি প্রপাগেশন (Lazy propagation)

যদি একসাথে অনেকগুলো সংখ্যা আপডেট বা রেঞ্জ আপডেট করতে বলা হয় (যেমন: ৩ থেকে ৮ নম্বর ইনডেক্সের সবার সাথে ৫ যোগ করুন), তবে নরমাল সেগমেন্ট ট্রিতে O(n) সময় লেগে যাবে। এই সমস্যার সমাধান হলো লেজি প্রপাগেশন (Lazy propagation) — সে কাজটা এখন না করে নোডের মধ্যে একটা চিরকুট বা 'pending update' লিখে রেখে দেয়, আর একেবারে ঠেলায় না পড়লে সেই আপডেটটা বাচ্চাদের কাছে পাঠায় না। এর ফলে রেঞ্জ আপডেটের স্পিডও রকেটের গতিতে O(log n)-এ নেমে আসে।

অ্যারে বনাম পয়েন্টার ইমপ্লিমেন্টেশন

সেগমেন্ট ট্রি সাধারণত পয়েন্টার দিয়ে না বানিয়ে 4n সাইজের একটা লম্বা অ্যারে দিয়ে বানানো হয়। এর ফলে i নম্বর নোডের বাঁ দিকের বাচ্চা থাকে 2i-এ আর ডান দিকের বাচ্চা থাকে 2i+1-এ। এতে মেমোরির খরচ বাঁচে আর সিপিইউ ক্যাশেও (CPU cache) ফাস্ট কাজ করে।

Complexity

বানানো (Build)
নিচ থেকে ওপরে সবগুলো 4n-সংখ্যক নোড ফিল-আপ করতে হয়
লিনিয়ার O(n)
রেঞ্জ খোঁজা (Range query)
সর্বোচ্চ 4 × log n নোড পর্যন্ত যেতে হতে পারে
খুব ফাস্ট O(log n)
সিঙ্গেল আপডেট (Point update)
নিচের পাতা থেকে একেবারে রুট পর্যন্ত উঠতে হয় — যার দৈর্ঘ্য ট্রির উচ্চতার সমান
খুব ফাস্ট O(log n)
রেঞ্জ আপডেট (লেজি দিয়ে)
অবশ্যই লেজি প্রপাগেশন (Lazy propagation) লাগবে; না হলে নরমালি O(n) লেগে যায়
খুব ফাস্ট O(log n)
জায়গা (Space)
4n সাইজের একটা লম্বা ট্রি অ্যারে লাগে
লিনিয়ার O(n)
Challenge

ছোট কুইজ

আপনার কাছে ১০ লাখ সংখ্যার একটা অ্যারে আছে আর আপনাকে ১০ লাখ বার বিভিন্ন রেঞ্জের যোগফল বের করতে হবে। সাধারণ লুপ আর সেগমেন্ট ট্রির সাহায্যে স্পিডের পার্থক্য কেমন হবে?

পড়া চালিয়ে যান