ট্রিপ (কার্তেসিয়ান ট্রি)#

ট্রিপ হলো একটি ডেটা স্ট্রাকচার যা বাইনারি ট্রি এবং বাইনারি হিপ একত্রিত করে (তাই নাম: tree + heap $\Rightarrow$ Treap)।

আরো নির্দিষ্টভাবে বলতে গেলে, ট্রিপ এমন একটি ডেটা স্ট্রাকচার যা $(X, Y)$ জোড়া একটি বাইনারি ট্রিতে এমনভাবে সংরক্ষণ করে যে এটি $X$ অনুসারে একটি বাইনারি সার্চ ট্রি এবং $Y$ অনুসারে একটি বাইনারি হিপ। যদি ট্রি-র কোনো নোডে মান $(X_0, Y_0)$ থাকে, তাহলে বাম সাবট্রির সব নোডে $X \leq X_0$, ডান সাবট্রির সব নোডে $X_0 \leq X$, এবং বাম ও ডান উভয় সাবট্রির সব নোডে $Y \leq Y_0$।

ট্রিপকে প্রায়ই “কার্তেসিয়ান ট্রি”-ও বলা হয়, কারণ এটি সহজেই কার্তেসিয়ান সমতলে স্থাপন করা যায়:

ট্রিপ ১৯৮৯ সালে Raimund Siedel এবং Cecilia Aragon প্রস্তাব করেছিলেন।

এই ডেটা সংগঠনের সুবিধা#

এই ইমপ্লিমেন্টেশনে, $X$ মানগুলো হলো কী (এবং একই সাথে ট্রিপে সংরক্ষিত মান), এবং $Y$ মানগুলোকে প্রায়োরিটি বলা হয়। প্রায়োরিটি ছাড়া, ট্রিপটি $X$ অনুসারে একটি সাধারণ বাইনারি সার্চ ট্রি হতো, এবং একই $X$ মানের সেট অনেক ভিন্ন ট্রির সাথে সংশ্লিষ্ট হতে পারত, কিছু অধঃপতিত (উদাহরণস্বরূপ, লিঙ্কড লিস্টের আকারে), এবং তাই অত্যন্ত ধীর (প্রধান অপারেশনগুলোর কমপ্লেক্সিটি $O(N)$ হতো)।

একই সাথে, প্রায়োরিটি (যখন তারা অনন্য) ট্রিটিকে অনন্যভাবে নির্দিষ্ট করতে দেয় যা তৈরি হবে (অবশ্যই, এটি মান যোগ করার ক্রমের উপর নির্ভর করে না), যা সংশ্লিষ্ট উপপাদ্য দিয়ে প্রমাণ করা যায়। স্পষ্টতই, যদি আপনি এলোমেলোভাবে প্রায়োরিটি বেছে নেন, আপনি গড়ে অধঃপতিত-নয় এমন ট্রি পাবেন, যা প্রধান অপারেশনগুলোর জন্য $O(\log N)$ কমপ্লেক্সিটি নিশ্চিত করবে। তাই এই ডেটা স্ট্রাকচারের আরেকটি নাম - র‍্যান্ডমাইজড বাইনারি সার্চ ট্রি।

অপারেশন#

একটি ট্রিপ নিম্নলিখিত অপারেশন প্রদান করে:

• Insert (X,Y) $O(\log N)$-এ। ট্রি-তে একটি নতুন নোড যোগ করে। একটি সম্ভব্য ভ্যারিয়ান্ট হলো শুধু $X$ পাস করা এবং অপারেশনের ভেতরে এলোমেলোভাবে $Y$ তৈরি করা।
• Search (X) $O(\log N)$-এ। নির্দিষ্ট কী মান $X$ এর একটি নোড খোঁজে। ইমপ্লিমেন্টেশন সাধারণ বাইনারি সার্চ ট্রির মতোই।
• Erase (X) $O(\log N)$-এ। নির্দিষ্ট কী মান $X$ এর একটি নোড খুঁজে ট্রি থেকে সরিয়ে দেয়।
• Build ($X_1$, …, $X_N$) $O(N)$-এ। মানের তালিকা থেকে একটি ট্রি তৈরি করে। এটি লিনিয়ার সময়ে করা যায় (ধরে নিচ্ছি $X_1, ..., X_N$ সাজানো আছে)।
• Union ($T_1$, $T_2$) $O(M \log (N/M))$-এ। দুটি ট্রি মার্জ করে, ধরে নিচ্ছি সব উপাদান ভিন্ন। মার্জের সময় ডুপ্লিকেট উপাদান সরানো হলেও একই কমপ্লেক্সিটি অর্জন করা সম্ভব।
• Intersect ($T_1$, $T_2$) $O(M \log (N/M))$-এ। দুটি ট্রির ছেদ খোঁজে (অর্থাৎ তাদের সাধারণ উপাদান)। এই অপারেশনের ইমপ্লিমেন্টেশন এখানে আলোচনা করা হবে না।

এছাড়াও, ট্রিপ একটি বাইনারি সার্চ ট্রি হওয়ায়, এটি অন্যান্য অপারেশনও ইমপ্লিমেন্ট করতে পারে, যেমন $K$-তম বৃহত্তম উপাদান খোঁজা বা কোনো উপাদানের ইনডেক্স বের করা।

ইমপ্লিমেন্টেশন বর্ণনা#

ইমপ্লিমেন্টেশনের দিক থেকে, প্রতিটি নোডে $X$, $Y$ এবং বাম ($L$) ও ডান ($R$) সন্তানের পয়েন্টার থাকে।

আমরা সব প্রয়োজনীয় অপারেশন শুধু দুটি সহায়ক অপারেশন ব্যবহার করে ইমপ্লিমেন্ট করবো: স্প্লিট এবং মার্জ।

স্প্লিট#

Split ($T$, $X$) ট্রি $T$ কে ২টি সাবট্রি $L$ ও $R$ এ আলাদা করে (যেগুলো স্প্লিটের রিটার্ন ভ্যালু) যেন $L$ তে কী $X_L \le X$ এর সব উপাদান থাকে, এবং $R$ তে কী $X_R > X$ এর সব উপাদান থাকে। এই অপারেশনের কমপ্লেক্সিটি $O (\log N)$ এবং এটি পরিষ্কার রিকার্শন দিয়ে ইমপ্লিমেন্ট করা হয়:

১. যদি রুট নোডের (R) মান $\le X$ হয়, তাহলে L অন্তত R->L এবং R নিয়ে গঠিত হবে। তারপর আমরা R->R এ স্প্লিট কল করি, এবং এর স্প্লিট ফলাফলকে L' এবং R' বলি। পরিশেষে, L-তে L'-ও থাকবে, এবং R = R'। ২. যদি রুট নোডের (R) মান $> X$ হয়, তাহলে R অন্তত R এবং R->R নিয়ে গঠিত হবে। তারপর আমরা R->L এ স্প্লিট কল করি, এবং এর স্প্লিট ফলাফলকে L' এবং R' বলি। পরিশেষে, L=L', এবং R-তে R'-ও থাকবে।

সুতরাং, স্প্লিট অ্যালগরিদম হলো:

১. রুট নোড কোন সাবট্রিতে যাবে (বাম বা ডান) তা ঠিক করো ২. এর একটি সন্তানের উপর রিকার্সিভভাবে স্প্লিট কল করো ৩. রিকার্সিভ স্প্লিট কলের ফলাফল পুনরায় ব্যবহার করে চূড়ান্ত ফলাফল তৈরি করো।

মার্জ#

Merge ($T_1$, $T_2$) দুটি সাবট্রি $T_1$ এবং $T_2$ সংযুক্ত করে এবং নতুন ট্রি রিটার্ন করে। এই অপারেশনেরও কমপ্লেক্সিটি $O (\log N)$। এটি কাজ করে এই ধারণায় যে $T_1$ এবং $T_2$ ক্রমানুসারে সাজানো ($T_1$ এর সব কী $X$ $T_2$ এর কী-গুলোর চেয়ে ছোট)। সুতরাং, প্রায়োরিটি $Y$ এর ক্রম ভঙ্গ না করে আমাদের এই ট্রিগুলো সংযুক্ত করতে হবে। এর জন্য, আমরা রুট হিসেবে সেই ট্রিটি বেছে নিই যার রুট নোডে প্রায়োরিটি $Y$ বেশি, এবং রিকার্সিভভাবে অন্য ট্রি ও নির্বাচিত রুট নোডের সংশ্লিষ্ট সাবট্রির জন্য মার্জ কল করি।

ইনসার্ট#

এখন Insert ($X$, $Y$) এর ইমপ্লিমেন্টেশন স্পষ্ট হয়ে যায়। প্রথমে আমরা ট্রিতে নামি (X অনুসারে সাধারণ বাইনারি সার্চ ট্রির মতো), এবং প্রথম নোডে থামি যেখানে প্রায়োরিটি মান $Y$ এর চেয়ে কম। আমরা সেই জায়গা পেয়ে গেছি যেখানে নতুন উপাদান বসাবো। এরপর, আমরা পাওয়া নোড থেকে শুরু করে সাবট্রিতে Split (T, X) কল করি, এবং রিটার্ন হওয়া সাবট্রি $L$ ও $R$ কে নতুন নোডের বাম ও ডান সন্তান হিসেবে ব্যবহার করি।

বিকল্পভাবে, ইনসার্ট প্রাথমিক ট্রিপকে $X$ এ স্প্লিট করে এবং নতুন নোডের সাথে ২টি মার্জ করেও করা যায় (ছবি দেখুন)।

ইরেজ#

Erase ($X$) এর ইমপ্লিমেন্টেশনও স্পষ্ট। প্রথমে আমরা ট্রিতে নামি ($X$ অনুসারে সাধারণ বাইনারি সার্চ ট্রির মতো), যে উপাদান মুছতে চাই তা খুঁজি। নোড পাওয়া গেলে, আমরা এর সন্তানদের উপর Merge কল করি এবং অপারেশনের রিটার্ন ভ্যালু যে উপাদান মুছছি তার জায়গায় বসাই।

বিকল্পভাবে, আমরা ২টি স্প্লিট অপারেশন দিয়ে $X$ ধারণকারী সাবট্রি আলাদা করে বাকি ট্রিপগুলো মার্জ করতে পারি (ছবি দেখুন)।

বিল্ড#

আমরা Build অপারেশন $O (N \log N)$ কমপ্লেক্সিটিতে $N$ টি Insert কল দিয়ে ইমপ্লিমেন্ট করি।

ইউনিয়ন#

Union ($T_1$, $T_2$) এর তাত্ত্বিক কমপ্লেক্সিটি $O (M \log (N / M))$, কিন্তু ব্যবহারিকভাবে এটি খুব ভালো কাজ করে, সম্ভবত অত্যন্ত ছোট লুকায়িত ধ্রুবক সহ। ধরি সাধারণতার ক্ষতি ছাড়া $T_1 \rightarrow Y > T_2 \rightarrow Y$, অর্থাৎ $T_1$ এর রুট ফলাফলের রুট হবে। ফলাফল পেতে, আমাদের $T_1 \rightarrow L$, $T_1 \rightarrow R$ এবং $T_2$ ট্রি দুটি ট্রিতে মার্জ করতে হবে যা $T_1$ রুটের সন্তান হতে পারে। এর জন্য, আমরা Split ($T_2$, $T_1\rightarrow X$) কল করি, এভাবে $T_2$ কে দুটি ভাগে L ও R এ বিভক্ত করি, যেগুলো তারপর রিকার্সিভভাবে $T_1$ এর সন্তানদের সাথে সংযুক্ত করি: Union ($T_1 \rightarrow L$, $L$) এবং Union ($T_1 \rightarrow R$, $R$), এভাবে ফলাফলের বাম ও ডান সাবট্রি পাই।

ইমপ্লিমেন্টেশন#

struct item {
	int key, prior;
	item *l, *r;
	item () { }
	item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
	item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

এটি আমাদের আইটেম সংজ্ঞা। লক্ষ্য করুন দুটি সন্তান পয়েন্টার আছে, এবং একটি পূর্ণসংখ্যা কী (BST এর জন্য) ও একটি পূর্ণসংখ্যা প্রায়োরিটি (হিপের জন্য)। প্রায়োরিটি একটি র‍্যান্ডম নম্বর জেনারেটর ব্যবহার করে নির্ধারণ করা হয়।

void split (pitem t, int key, pitem & l, pitem & r) {
	if (!t)
		l = r = NULL;
	else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
	else
        split (t->l, key, l, t->l),  r = t;
}

t হলো স্প্লিট করার ট্রিপ, এবং key হলো BST মান যা দিয়ে স্প্লিট করতে হবে। লক্ষ্য করুন আমরা কোথাও ফলাফল return করি না, বরং এভাবে ব্যবহার করি:

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);
if (l) cout << "Left subtree size: " << (l->size) << endl;
if (r) cout << "Right subtree size: " << (r->size) << endl;

এই split ফাংশনটি বুঝতে কঠিন হতে পারে, কারণ এতে পয়েন্টার (pitem) এবং সেই পয়েন্টারের রেফারেন্স (pitem &l) উভয়ই আছে। আসুন split(t, k, l, r) ফাংশন কলের অর্থ বুঝি: “ট্রিপ t কে মান k দিয়ে দুটি ট্রিপে স্প্লিট করো, এবং বাম ট্রিপ l এ ও ডান ট্রিপ r এ সংরক্ষণ করো”। এখন, আসুন এই সংজ্ঞা দুটি রিকার্সিভ কলে প্রয়োগ করি, পূর্ববর্তী বিভাগে বিশ্লেষিত কেস ওয়ার্ক ব্যবহার করে: (প্রথম if শর্তটি খালি ট্রিপের জন্য একটি তুচ্ছ ভিত্তি ক্ষেত্র)

১. যখন রুট নোডের মান $\le$ key, আমরা split (t->r, key, t->r, r) কল করি, যার অর্থ: “ট্রিপ t->r (t এর ডান সাবট্রি) কে মান key দিয়ে স্প্লিট করো এবং বাম সাবট্রি t->r এ ও ডান সাবট্রি r এ সংরক্ষণ করো”। এরপর, আমরা l = t সেট করি। লক্ষ্য করুন এখন l ফলাফল মানে t->l, t এবং t->r (যা আমাদের রিকার্সিভ কলের ফলাফল) সবই ইতিমধ্যে সঠিক ক্রমে মার্জ হয়ে আছে! আপনার থামা উচিত নিশ্চিত করতে যে l ও r এর এই ফলাফল আগে ইমপ্লিমেন্টেশন বর্ণনায় আমরা যা আলোচনা করেছি তার সাথে ঠিক মিলে যায়। ২. যখন রুট নোডের মান key এর চেয়ে বড়, আমরা split (t->l, key, l, t->l) কল করি, যার অর্থ: “ট্রিপ t->l (t এর বাম সাবট্রি) কে মান key দিয়ে স্প্লিট করো এবং বাম সাবট্রি l এ ও ডান সাবট্রি t->l এ সংরক্ষণ করো”। এরপর, আমরা r = t সেট করি। লক্ষ্য করুন এখন r ফলাফল মানে t->l (যা আমাদের রিকার্সিভ কলের ফলাফল), t এবং t->r, সবই ইতিমধ্যে সঠিক ক্রমে মার্জ হয়ে আছে! আপনার থামা উচিত নিশ্চিত করতে যে l ও r এর এই ফলাফল আগে ইমপ্লিমেন্টেশন বর্ণনায় আমরা যা আলোচনা করেছি তার সাথে ঠিক মিলে যায়।

আপনার যদি ইমপ্লিমেন্টেশন বুঝতে এখনো সমস্যা হয়, আপনার এটিকে আরোহী পদ্ধতিতে দেখা উচিত, অর্থাৎ: রিকার্সিভ কলগুলো বারবার ভেঙে দেখার চেষ্টা করবেন না। ধরে নিন স্প্লিট ইমপ্লিমেন্টেশন খালি ট্রিপে সঠিকভাবে কাজ করে, তারপর একটি একক নোড ট্রিপে চালানোর চেষ্টা করুন, তারপর দুই নোড ট্রিপে, এভাবে এগিয়ে যান, প্রতিবার আপনার জ্ঞান ব্যবহার করুন যে ছোট ট্রিপে স্প্লিট কাজ করে।

void insert (pitem & t, pitem it) {
	if (!t)
		t = it;
	else if (it->prior > t->prior)
		split (t, it->key, it->l, it->r),  t = it;
	else
		insert (t->key <= it->key ? t->r : t->l, it);
}

void merge (pitem & t, pitem l, pitem r) {
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
	if (t->key == key) {
		pitem th = t;
		merge (t, t->l, t->r);
		delete th;
	}
	else
		erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
	if (!l || !r)  return l ? l : r;
	if (l->prior < r->prior)  swap (l, r);
	pitem lt, rt;
	split (r, l->key, lt, rt);
	l->l = unite (l->l, lt);
	l->r = unite (l->r, rt);
	return l;
}

সাবট্রির আকার সংরক্ষণ#

ট্রিপের কার্যকারিতা বাড়াতে, প্রায়ই প্রতিটি নোডের সাবট্রিতে নোডের সংখ্যা সংরক্ষণ করা প্রয়োজন - item স্ট্রাকচারে int cnt ফিল্ড। উদাহরণস্বরূপ, এটি ট্রি-র $K$-তম বৃহত্তম উপাদান $O (\log N)$-এ খুঁজতে, অথবা সাজানো তালিকায় উপাদানের ইনডেক্স একই কমপ্লেক্সিটিতে বের করতে ব্যবহার করা যায়। এই অপারেশনগুলোর ইমপ্লিমেন্টেশন সাধারণ বাইনারি সার্চ ট্রির মতোই হবে।

যখন ট্রি পরিবর্তন হয় (নোড যোগ বা সরানো হয় ইত্যাদি), কিছু নোডের cnt সেই অনুযায়ী আপডেট করা উচিত। আমরা দুটি ফাংশন তৈরি করবো: cnt() বর্তমান cnt এর মান রিটার্ন করবে অথবা নোড না থাকলে ০, এবং upd_cnt() এই নোডের cnt এর মান আপডেট করবে ধরে নিয়ে যে এর সন্তান L ও R এর cnt মান ইতিমধ্যে আপডেট হয়ে আছে। স্পষ্টতই cnt মান হালনাগাদ রাখতে insert, erase, split এবং merge এর শেষে upd_cnt() কল যোগ করাই যথেষ্ট।

int cnt (pitem t) {
	return t ? t->cnt : 0;
}

void upd_cnt (pitem t) {
	if (t)
		t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

$O (N)$-এ অফলাইন মোডে ট্রিপ তৈরি#

কী-গুলোর একটি সাজানো তালিকা দেওয়া আছে, একটি একটি করে কী ইনসার্ট করে ট্রিপ তৈরির চেয়ে ($O(N \log N)$ সময় লাগে) দ্রুততর উপায়ে ট্রিপ তৈরি করা সম্ভব। যেহেতু কী-গুলো সাজানো, একটি সুষম বাইনারি সার্চ ট্রি সহজেই লিনিয়ার সময়ে তৈরি করা যায়। হিপ মান $Y$ এলোমেলোভাবে ইনিশিয়ালাইজ করা হয় এবং তারপর কী $X$ থেকে স্বাধীনভাবে $O(N)$-এ হিপ তৈরি করা যায়।

void heapify (pitem t) {
	if (!t) return;
	pitem max = t;
	if (t->l != NULL && t->l->prior > max->prior)
		max = t->l;
	if (t->r != NULL && t->r->prior > max->prior)
		max = t->r;
	if (max != t) {
		swap (t->prior, max->prior);
		heapify (max);
	}
}

pitem build (int * a, int n) {
	// Construct a treap on values {a[0], a[1], ..., a[n - 1]}
	if (n == 0) return NULL;
	int mid = n / 2;
	pitem t = new item (a[mid], rand ());
	t->l = build (a, mid);
	t->r = build (a + mid + 1, n - mid - 1);
	heapify (t);
	upd_cnt(t)
	return t;
}

দ্রষ্টব্য: upd_cnt(t) কল শুধু তখনই প্রয়োজন যখন আপনার সাবট্রির আকার দরকার।

উপরের পদ্ধতি সবসময় একটি পুরোপুরি সুষম ট্রি দেয়, যা সাধারণত ব্যবহারিক উদ্দেশ্যে ভালো, কিন্তু প্রতিটি নোডে প্রাথমিকভাবে নির্ধারিত প্রায়োরিটি সংরক্ষিত না থাকার মূল্যে। তাই, এই পদ্ধতি নিম্নলিখিত সমস্যা সমাধানে কাজে আসবে না:

এখানে একটি সম্ভব্য সমাধান হলো প্রতিটি উপাদানের জন্য বাম ও ডানে সবচেয়ে কাছের উপাদান খোঁজা যাদের প্রায়োরিটি এই উপাদানের চেয়ে ছোট। এই দুটি উপাদানের মধ্যে, বড় প্রায়োরিটি বিশিষ্টটি বর্তমান উপাদানের প্যারেন্ট হতে হবে।

এই সমস্যা মিনিমাম স্ট্যাক পরিবর্তন দিয়ে লিনিয়ার সময়ে সমাধানযোগ্য:

void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}

pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

ইমপ্লিসিট ট্রিপ#

ইমপ্লিসিট ট্রিপ হলো সাধারণ ট্রিপের একটি সরল পরিবর্তন যা একটি অত্যন্ত শক্তিশালী ডেটা স্ট্রাকচার। প্রকৃতপক্ষে, ইমপ্লিসিট ট্রিপকে নিম্নলিখিত প্রক্রিয়াগুলো ইমপ্লিমেন্ট করা একটি অ্যারে হিসেবে বিবেচনা করা যায় (সবই অনলাইন মোডে $O (\log N)$-এ):

• অ্যারের যেকোনো স্থানে উপাদান ইনসার্ট করা
• যেকোনো উপাদান সরানো
• যেকোনো ব্যবধানে যোগফল, সর্বনিম্ন / সর্বোচ্চ উপাদান ইত্যাদি বের করা
• যেকোনো ব্যবধানে যোগ, রং করা
• যেকোনো ব্যবধানে উপাদান উল্টানো

ধারণাটি হলো কী-গুলো হওয়া উচিত অ্যারেতে উপাদানগুলোর শূন্য-ভিত্তিক ইনডেক্স। কিন্তু আমরা এই মানগুলো সুস্পষ্টভাবে সংরক্ষণ করবো না (অন্যথায়, উদাহরণস্বরূপ, একটি উপাদান ইনসার্ট করলে ট্রি-র $O (N)$ নোডের কী পরিবর্তন করতে হতো)।

লক্ষ্য করুন একটি নোডের কী হলো তার চেয়ে ছোট নোডের সংখ্যা (এরকম নোড শুধু এর বাম সাবট্রিতেই নয়, এর পূর্বপুরুষদের বাম সাবট্রিতেও থাকতে পারে)। আরো নির্দিষ্টভাবে, কোনো নোড T এর ইমপ্লিসিট কী হলো এই নোডের বাম সাবট্রিতে শীর্ষের সংখ্যা $cnt (T \rightarrow L)$ যোগ নোড T এর প্রতিটি পূর্বপুরুষ P এর জন্য অনুরূপ মান $cnt (P \rightarrow L) + 1$, যদি T P এর ডান সাবট্রিতে থাকে।

এখন স্পষ্ট কীভাবে বর্তমান নোডের ইমপ্লিসিট কী দ্রুত গণনা করা যায়। যেহেতু সব অপারেশনে আমরা ট্রিতে নেমে যেকোনো নোডে পৌঁছাই, আমরা এই যোগফল জমা করে ফাংশনে পাস করতে পারি। যদি আমরা বাম সাবট্রিতে যাই, জমানো যোগফল পরিবর্তন হয় না, যদি ডান সাবট্রিতে যাই তা $cnt (T \rightarrow L) +1$ বেড়ে যায়।

এখানে Split এবং Merge এর নতুন ইমপ্লিমেন্টেশন:

void merge (pitem & t, pitem l, pitem r) {
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
	upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
	if (!t)
		return void( l = r = 0 );
	int cur_key = add + cnt(t->l); //implicit key
	if (key <= cur_key)
		split (t->l, l, t->l, key, add),  r = t;
	else
		split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
	upd_cnt (t);
}

উপরের ইমপ্লিমেন্টেশনে, $split(T, T_1, T_2, k)$ কলের পর, ট্রি $T_1$ $T$ এর প্রথম $k$ টি উপাদান নিয়ে গঠিত হবে (অর্থাৎ যেসব উপাদানের ইমপ্লিসিট কী $k$ এর চেয়ে কম) এবং $T_2$ বাকি সব নিয়ে।

এখন ইমপ্লিসিট ট্রিপে বিভিন্ন অপারেশনের ইমপ্লিমেন্টেশন দেখা যাক:

• উপাদান ইনসার্ট। ধরি আমাদের $pos$ অবস্থানে একটি উপাদান ইনসার্ট করতে হবে। আমরা ট্রিপটিকে দুটি ভাগে ভাগ করি, যেগুলো $[0..pos-1]$ এবং $[pos..sz]$ অ্যারের সাথে সংশ্লিষ্ট; এর জন্য আমরা $split(T, T_1, T_2, pos)$ কল করি। তারপর আমরা ট্রি $T_1$ কে নতুন শীর্ষের সাথে $merge(T_1, T_1, \text{new item})$ কল করে সংযুক্ত করতে পারি (দেখা সহজ যে সব পূর্বশর্ত পূরণ হয়)। পরিশেষে, আমরা $T_1$ ও $T_2$ কে $merge(T, T_1, T_2)$ কল করে $T$ তে সংযুক্ত করি।
• উপাদান মুছে ফেলা। এই অপারেশন আরো সহজ: মুছতে হবে এমন উপাদান $T$ খুঁজুন, এর সন্তান $L$ ও $R$ এর মার্জ করুন, এবং মার্জের ফলাফল দিয়ে উপাদান $T$ প্রতিস্থাপন করুন। প্রকৃতপক্ষে, ইমপ্লিসিট ট্রিপে উপাদান মুছে ফেলা সাধারণ ট্রিপের মতোই।
• ব্যবধানে যোগফল / সর্বনিম্ন ইত্যাদি খোঁজা। প্রথমে, item স্ট্রাকচারে একটি অতিরিক্ত ফিল্ড $F$ তৈরি করুন এই নোডের সাবট্রির জন্য লক্ষ্য ফাংশনের মান সংরক্ষণ করতে। সাবট্রির আকার বজায় রাখার মতোই এই ফিল্ড বজায় রাখা সহজ: একটি ফাংশন তৈরি করুন যা সন্তানদের মানের উপর ভিত্তি করে একটি নোডের এই মান গণনা করে এবং ট্রি পরিবর্তনকারী সব ফাংশনের শেষে এই ফাংশনের কল যোগ করুন। দ্বিতীয়ত, যেকোনো ব্যবধান $[A; B]$ এর জন্য একটি কোয়েরি প্রক্রিয়া করতে হবে। ট্রির যে অংশ $[A; B]$ ব্যবধানের সাথে সংশ্লিষ্ট তা পেতে, আমাদের $split(T, T_2, T_3, B+1)$, তারপর $split(T_2, T_1, T_2, A)$ কল করতে হবে: এরপর $T_2$ $[A; B]$ ব্যবধানের সব উপাদান নিয়ে গঠিত হবে, এবং শুধু সেগুলোই। তাই কোয়েরির উত্তর $T_2$ এর রুটের $F$ ফিল্ডে সংরক্ষিত থাকবে। কোয়েরির উত্তর দেওয়ার পর, $merge(T, T_1, T_2)$ এবং $merge(T, T, T_3)$ কল করে ট্রি পুনরুদ্ধার করতে হবে।
• ব্যবধানে যোগ / রং করা। আমরা আগের অনুচ্ছেদের মতোই কাজ করি, কিন্তু F ফিল্ডের বদলে একটি add ফিল্ড সংরক্ষণ করবো যাতে সাবট্রিতে যোগ করা মান (বা সাবট্রিতে রং করার মান) থাকবে। কোনো অপারেশন করার আগে আমাদের এই মান সঠিকভাবে “পুশ” করতে হবে - অর্থাৎ $T \rightarrow L \rightarrow add$ ও $T \rightarrow R \rightarrow add$ পরিবর্তন করতে হবে, এবং প্যারেন্ট নোডে add পরিষ্কার করতে হবে। এভাবে ট্রিতে যেকোনো পরিবর্তনের পরও তথ্য হারাবে না।
• ব্যবধানে উল্টানো। এটিও আগের অপারেশনের মতো: আমাদের একটি বুলিয়ান ফ্ল্যাগ rev যোগ করতে হবে এবং বর্তমান নোডের সাবট্রি উল্টাতে হলে এটি true সেট করতে হবে। এই মান “পুশ” করা একটু জটিল - আমরা এই নোডের সন্তানদের অদলবদল করি এবং তাদের জন্য এই ফ্ল্যাগ true সেট করি।

এখানে ব্যবধানে উল্টানো সহ ইমপ্লিসিট ট্রিপের একটি উদাহরণ ইমপ্লিমেন্টেশন। প্রতিটি নোডে আমরা value নামে ফিল্ড সংরক্ষণ করি যা বর্তমান অবস্থানে অ্যারে উপাদানের প্রকৃত মান। আমরা output() ফাংশনেরও ইমপ্লিমেন্টেশন দিচ্ছি, যা ইমপ্লিসিট ট্রিপের বর্তমান অবস্থার সাথে সংশ্লিষ্ট অ্যারে আউটপুট করে।

typedef struct item * pitem;
struct item {
	int prior, value, cnt;
	bool rev;
	pitem l, r;
};

int cnt (pitem it) {
	return it ? it->cnt : 0;
}

void upd_cnt (pitem it) {
	if (it)
		it->cnt = cnt(it->l) + cnt(it->r) + 1;
}

void push (pitem it) {
	if (it && it->rev) {
		it->rev = false;
		swap (it->l, it->r);
		if (it->l)  it->l->rev ^= true;
		if (it->r)  it->r->rev ^= true;
	}
}

void merge (pitem & t, pitem l, pitem r) {
	push (l);
	push (r);
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
	upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
	if (!t)
		return void( l = r = 0 );
	push (t);
	int cur_key = add + cnt(t->l);
	if (key <= cur_key)
		split (t->l, l, t->l, key, add),  r = t;
	else
		split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
	upd_cnt (t);
}

void reverse (pitem t, int l, int r) {
	pitem t1, t2, t3;
	split (t, t1, t2, l);
	split (t2, t2, t3, r-l+1);
	t2->rev ^= true;
	merge (t, t1, t2);
	merge (t, t, t3);
}

void output (pitem t) {
	if (!t)  return;
	push (t);
	output (t->l);
	printf ("%d ", t->value);
	output (t->r);
}

সাহিত্য#

• Blelloch, Reid-Miller “Fast Set Operations Using Treaps”

অনুশীলন সমস্যা#

• SPOJ - Ada and Aphids
• SPOJ - Ada and Harvest
• Codeforces - Radio Stations
• SPOJ - Ghost Town
• SPOJ - Arrangement Validity
• SPOJ - All in One
• Codeforces - Dog Show
• Codeforces - Yet Another Array Queries Problem
• SPOJ - Mean of Array
• SPOJ - TWIST
• SPOJ - KOILINE
• CodeChef - The Prestige
• Codeforces - T-Shirts
• Codeforces - Wizards and Roads
• Codeforces - Yaroslav and Points