fanbase

যারা নতুন শুরু করেছো এবং কোথা থেকে কীভাবে শুরু করা উচিৎ সেটা বুঝতে পারছো না তারা এই লিংক থেকে নোটটি দেখে নাও। এটি কাজ করার কথা :3

SQRT Tree

Written by Munim Hasan Wasi on April 12, 2020
Data Structure , SQRT Algorithm , Tree





পরিচয়পর্ব :grinning:

আমাদের \(n\) সাইজের একটি আ্যরে \(a\) এবং একটি অপারেশন \(\circ\) দেওয়া আছে যা সংযোজন বিধি মেনে চলে অর্থাৎ যেকোনো $x$, $y$, $z$ এর জন্য $(x \circ y) \circ z = x \circ (y \circ z)$ ।

এমন অপারেশন এর মধ্যে রয়েছে যোগ (\(+\)), বিয়োগ (\(-\)), বাইনারি এন্ড (\(\wedge\)), বাইনারি অর(\(\vee\)), বাইনারি এক্স-অর (\(\oplus\)), গসাগু (\(gcd\)) ইত্যাদি।

আমাদের কিছু কুয়েরি দেওয়া হবে $q(l, r)$ আকারের. প্রতি কুয়েরিতে আমাদের $a_l \circ a_{l+1} \circ \dots \circ a_r$ উত্তর হিসেবে আউটপুট দিতে হবে।

স্ক্রট ডিকম্পোজিশন দিয়ে \(O(\sqrt n)\) এ এমন আপডেট ও কুয়েরি করা যায়। কিন্তু এসব নুব কম্প্লেক্সিটিতে কাজ করলে তো হবে না। স্ক্রট ট্রি এমন কুয়েরি $O(1)$ টাইম কম্প্লেক্সিটি তে করতে পারে । আর এজন্য শুধু $O(n \cdot \log \log n)$ প্রি-প্রসেসিং টাইম ও $O(n \cdot \log \log n)$ মেমোরি প্রযোজন হয়।


বর্ণনা


বিল্ড করা


আমরা প্রথমে একটি sqrt decomposition বানাবো। আমরা আমাদের অ্যারে \(a\) কে $\sqrt{n}$ টি ব্লকে ভাগ করবো, যেখানে প্রতিটি ব্লকের সাইজ হবে $\sqrt{n}$।প্রতিটি ব্লকের জন্য আমরা নিচের জিনিসগুলো ক্যালকুলেট করে ফেলবো:

  1. যেসব কুয়েরিগুলো কোনো একটা ব্লকের একেবারে শুরুতে শুরু হয়েছে এবং ওই ব্লকটির মধ্যেই কোথাও শেষ হয়েছে ($\text{prefixOp}$)
  2. যেসব কুয়েরিগুলো কোনো একটা ব্লকের ভিতরে যেকোনো যায়গায় শুরুতে শুরু হয়েছে এবং ওই ব্লকটির একেবারে শেষ প্রান্তে শেষ হয়েছে ($\text{suffixOp}$)

এর পাশাপাশি আমরা আরো একটা \(2D\) অ্যারে ক্যালকুলেট করবো যেটার নাম হবে \(b\) এবং আকার হবে \(\sqrt n * \sqrt n\):

  1. $\text{b}_{i, j}$ (সকল $i \le j$ এর জন্য) - যে কুয়েরিটি $i$ তম ব্লক এর প্রথম ইনডেক্স থেকে শুরু করে $j$ তম ব্লক এর শেষ ইনডেক্স এ এসে শেষ হয় তার উত্তর।এখানে দেখার বিষয় হচ্ছে যে আমাদের $\sqrt{n}$ টা ব্লক আছে, তাই অ্যারেটার টোটাল সাইজ হবে $O(\sqrt{n}^2) = O(n)$।

একটা ছোট উদাহরণ এর মাধ্যমে বিষয়টা পরিষ্কার করা যাক।

ধরি $\circ$ অপারেশনটি হচ্ছে $+$ (আমরা কুয়েরিতে যোগফল আউটপুট করবো) এবং আমাদের $a$ অ্যারেটি হচ্ছে:

\[a=\{1, 2, 3, 4, 5, 6, 7, 8, 9\}\]

এটি মোট \(\sqrt 9 = 3\) তিনটি ব্লকে বিভক্ত হবে: \(\{1, 2, 3\}, \{4, 5, 6\}\) এবং \(\{7, 8, 9\}\)।

প্রথম ব্লকটির জন্য $\text{prefixOp}$ হবে \(\{1, 3, 6\}\) এবং $\text{suffixOp}$ হবে \(\{6, 5, 3\}\)।

দ্বিতীয় ব্লকটির জন্য $\text{prefixOp}$ হবে \(\{4, 9, 15\}\) এবং $\text{suffixOp}$ হবে \(\{15, 11, 6\}\)।

তৃতীয় ব্লকটির জন্য $\text{prefixOp}$ হবে \(\{7, 15, 24\}\) এবং $\text{suffixOp}$ হবে \(\{24, 17, 9\}\)।

\(b\) অ্যারেটি হবে:

{
    {6, 21, 45},
    {0, 15, 39},
    {0, 0,  24}
}

( যেখানে $i > j$ হয় সেখানে \(0\) দিয়ে ভরাট করা হয়েছে)

এটা দেখাই যায় যে এই অ্যারেগুলো $O(n)$ টাইম এবং মেমোরিতে ক্যালকুলেট করা যায়.

এই অ্যারেগুলো ব্যবহার করে আমরা অলরেডি কিছু কুয়েরি এর উত্তর দিতে পারবো. যদি কোনো একটা কুয়েরি অনেকগুলো ব্লক নিয়ে গঠিত হয়, তখন আমরা কুয়েরিটাকে তিন ভাগে ভাগ করে উত্তর দিতে পারবো। কুয়েরিটা অবশ্যই কেনো একটা ব্লকের কোনো একটা ইনডেক্স থেকে শুরু হবে, তারপর কিছু ব্লকের (০ ও হতে পারে) পুরোটা নিয়ে নিব, তারপর শেষ ব্লক এর কোনো একটা ইনডেক্স এ এসে শেষ হবে। যে ব্লক থেকে শুরু হয়েছে ওই ব্লকের অংশের উত্তর আমরা $\text{suffixOp}$ থেকে, তারপর \(b\) অ্যারে থেকে একটানা কিছু ইনডেক্স এর উত্তর নিয়ে, এবং সবশেষে যে ব্লকে শেষ হয়েছে ওই ব্লকের উত্তর $\text{prefixOp}$ অ্যারে থেকে নিয়ে আমরা পূর্ণ উত্তর পেয়ে যাবো।

কিন্তু যদি এমন হয় যে কুয়েরির পুরোটাই একটা ব্লকের মধ্যে হয় তখন আমরা আর এই উপায়ে উত্তর বের করতে পারবো না। এজন্য একটু চালাকি করতে হবে।


ট্রি বানানো


একটা কুয়েরি পুরোপুরি একটা ব্লকের ভিতর থাকলে আমরা সেটার উত্তর বের করতে পারি না। কিন্তু যদি আমরা প্রতিটা ব্লকের জন্য আবার উপরের ডাটা স্ট্রাকচারটি বানাই তাহলে কী হবে? । হ্যাঁ, তখন আমাদের প্রকৃত উদ্দেশ্য হাসিল হবে। আমরা রিকার্সিভলি এভাবে ডাটা স্ট্রাকচারটি বানাতে থাকবো যতক্ষণ না সবচেয়ে ছোট ব্লকগুলোর সাইজ $1$ বা $2$ হয়. এমন সাইজের ব্লকের জন্য উত্তর $O(1)$ এই বের করে ফেলা যাবে।

তো, ফাইনালি আমরা একটি ট্রি পাবো। ট্রি টার প্রতিটি নোড মূল অ্যারেটার কোনো একটা সেগমেন্টকে নির্দেশ করবে। যেসব নোড $k$ সাইজের কোনো একটা সেগমেন্টকে নির্দেশ করবে তার $\sqrt{k}$ টা চাইল্ড থাকবে – প্রতিটি ব্লকের জন্য একটা করে. আবার প্রতিটা নোডে তিনটা অ্যারে থাকবে গুলো ওই সেগমেন্ট এর $\text{prefixOp}$, $\text{suffixOp}$ ও \(b\) কে নির্দেশ করবে। ট্রি টির রুট এ পুরো মূল অ্যারেটা থাকবে. লিফ নোড এর সাইজ হবে $1$ বা $2$।

আর এটা দেখাই যাচ্ছে যে ট্রি এর হাইট $O(\log \log n)$ হবে, কারণ ট্রি এর কোনো একটা নোড যদি $k$ সাইজের কোনো একটা সেগমেন্টকে নির্দেশ করে, তাহলে তার চাইল্ড দের সাইজ হবে$\sqrt{k}$ । $\log(\sqrt{k}) = \frac{\log{k}}{2}$, তাই $\log k$ ট্রি এর প্রতি লেয়ার এ অর্ধেক হচ্ছে। তাই ট্রি এর টোটাল হাইট হবে $O(\log \log n)$। ট্রি টা বানানোর জন্য টাইম এবং মেমোরি লাগবে $O(n \cdot \log \log n)$, কারণ অ্যারের প্রতিটা উপাদান প্রতি লেয়ারে শুধু একবার করেই আসে।

আমরা এই ট্রি ব্যবহার করে $O(\log \log n)$ তে কুয়েরি করতে পারবো. আমরা ট্রি ধরে নিচে নামতে থাকবো যতক্ষণ না এমন সেগমেন্ট আসে যায় সাইজ $1$ বা $2$। অথবা আমরা তখনো থেমে যাবো যদি এমন কোনো সেগমেন্ট পাওয়া যায় যেটার জন্য আমাদের কুয়েরি পুরোপুরি একটা ব্লকে না আঁটে। এক্ষেত্রে আমরা আগের মতোই অ্যারে তিনটা ব্যবহার করে ‌কুয়েরির এ অংশের উত্তর দিতে পারবো.

তো এখন আমরা $O(\log \log n)$ এ কুয়েরি করতে শিখেই গেলাম। কিন্তু, এর চেয়ে ভালো কম্প্লেক্সিটিতে কি কুয়েরি করা যাবে?


আরো অপটিমাইজড কুয়েরি :nerd_face:


একটা সহজ অপটিমাইজেশন হতে পারে বাইনারি সার্চ ব্যবহার করা। আমাদের ট্রি এর কোন নোড টা দরকার সেটা বাইনারি সার্চ করেই বের করে ফেলতে পারি। বাইনারি সার্চ লাগালে আমরা $O(\log \log \log n)$ এ কুয়েরি করতে পারবো. কিন্তু এটাই কি শেষ? এর চেয়েও ভালো কি করা যায় না? xD আমরা একটু বেশিই লোভি, নাকি?

কিন্তু তাও, উত্তরটা হচ্ছে হ্যাঁ। আমরা এর চেয়েও ভালো কম্প্লেক্সিটিতে কুয়েরি করতে পারবো। প্রথমে দুটি স্বীকার্য ধরে নিতে হবে:

  1. প্রতিটা ব্লকের সাইজ \(2\) এর পাওয়ার হবে।
  2. কোনো একটা লেয়ারের সবগুলো ব্লকের সাইজ সমান হবে।

এগুলো সত্য করার জন্য আমরা আমাদের অ্যারেতে কিছু অতিরিক্ত \(0\) যোগ করে দিতে পারি যেন অ্যারেটির সাইজ \(2^x\) হয়।

যদি আমরা এটা করি তাহলে কিছু কিছু ব্লকের সাইজ প্রয়োজনের দ্বিগুন পর্যন্ত হয়ে যেতে পারে, কিন্তু তাও এটার সাইজ $O(\sqrt{k})$ ই থাকবে এবং আমরা লিনিয়ার কম্প্লেক্সিটিতেই বিল্ড করার কাজ সম্পাদন করতে পারবো।

এখম, আমরা বেশ সহজেই চেক করতে পারবো কুয়েরিটা $2^k$ সাইজের ব্লকের ভিতর পরে কিনা। কুয়েরির $l$ এবং $r$ (0-বেসড ইনডেক্স এ) কে বাইনারিতে লিখা যাক. ধরি, $k=4, l=39, r=46$. এক্ষেত্রে $l$ এবং $r$ হবে:

$l = 39_{10} = 100111_2$

$r = 46_{10} = 101110_2$

আমাদের এটা মনে রাখতে হবে যে কোনো একটা লেয়ারের প্রতিটা ব্লক সমান সাইজের। (এক্ষেত্রে এই সাইজটি হচ্ছে $2^k = 2^4 = 16$)। প্রথম ব্লকটি কাভার করে $(0 - 15)$ বা $(000000_2 - 001111_2)$, দ্বিতীয় ব্লকটি কাভার করে $(16 - 31)$ বা $(010000_2 - 011111_2)$। এবং এভাবেই \(16\) টি করে কাভার করতে থাকে। আমরা দেখি যে কোনো একটা ব্লকের প্রথম ইনডেক্স এর সাথে ওই ব্লকের শেষ ইনডেক্স এর বাইনারি ফর্ম এ শুধু শেষ $k$ (আমাদের ক্ষেত্রে, $4$) টা ডিজিট ই আলাদা হতে পারে কিন্তু এর আগের সবগুলো ডিজিট সেম হয়। এটা ব্লকের মধ্যের যেকোনো দুটি ইনডেক্স এর জন্যই সত্য হবে। আমাদের ক্ষেত্রে $l$ ও $r$ এর শেষ \(4\) টির আগের সবগুলো ডিজিট সেম, তাই তারা একই ব্লকের মধ্যে পড়েছে।

তো, আমাদের এটা চেক করতে হবে যেন শেষ থেকে সর্বোচ্চ $k$ টা বিট ই আলাদা হয় (বা $l\ \text{xor}\ r$ এর মান $2^k-1$ এর বেশি না হয়)।

এই অবজারভেশনের মাধ্যমে আমরা খুব সহজেই এমন একটা লেয়ার খুঁজে বের করতে পারবো যেটা কুয়েরিটার উত্তর করার জন্য পারফেক্ট । এটা করার জন্য:

  1. অ্যারের সকল ইনডেক্স $i$ এর জন্য আমরা খুঁজে বের করবো সবচেয়ে বামের কোন বিটটা $1$। এটা তারাতারি করার জন্য আমরা ডিপি করে প্রিক্যালকুলেট করে ফেলতে পারি।

  2. এখন, প্রতি কুয়েরি $q(l, r)$ এর জন্য আমাদের $l\ \text{xor}\ r$ এর সবচেয়ে বামের \(1\) বিট টা খুঁজে বের করতে হবে এবং, এই তথ্য ব্যবহার করে সহজেই আমরা বের করে ফেলতে পারবো কোন লেয়ার ব্যবহার করলে আমরা সহজে কুয়েরিটির উত্তর দিতে পারবো। আমরা এটার জন্যও একটা প্রিক্যালকুলেটেড অ্যারে ব্যবহার করতে পারি।

বিস্তারিত ব্যাখ্যার জন্য একেবারে শেষে কোড দেখলেই হবে।

এই টেকনিকে কোপ দিয়ে আমরা $O(1)$ এ কুয়েরি খেলতে পারবো. ইয়েেেেেেেেেেেেেেেেেেেেেেেেেেেেেেেেেেেস। :)

এর চেয়ে ভালো কি করা যাবে? xD


আপডেট :fearful:


আমরা স্ক্রট ট্রি তে আপডেট ও করতে পারি। পয়েন্ট আপডেট আর রেঞ্জ আপডেট দুটোই করা যায় স্ক্রট ট্রিতে।


পয়েন্ট আপডেট :smiley:


একটা অপারেশন $\text{update}(x, val)$ ধরি যেটা $a_x = val$ করে অর্থাৎ ভ্যালু এসাইন করে। আমাদের এটা দ্রুত করতে হবে।


নুব পদ্ধতি :unamused:


প্রথমে আমরা এটা খেয়াল করি যে একটা উপাদানের পরিবর্তন করতে গেলে ট্রি টার মধ্যে কী কী পরিবর্তন ঘটে। ধরি ট্রি টার একটা নোড যেটা $l$ দৈর্ঘ্যের এবং এটার অ্যারেগুলো হচ্ছে: $\text{prefixOp}$, $\text{suffixOp}$ and \(b\)। এটা সহজেই দেখা যায় যে $\text{prefixOp}$ ও $\text{suffixOp}$ এর $O(\sqrt{l})$ টা উপাদান ই শুধু পরিবর্তিত হয় (শুধু যে ব্লকের উপাদানটি পরিবর্তিত হচ্ছে সেই ব্লকে). $b$ এর $O(l)$ টা উপাদান পরিবর্তিত হয়। তাই, ট্রি এর মোট $O(l)$ টা উপাদান পরিবর্তিত হয়।

আমরা জানি যে ট্রি এর কোনো একটা উপাদান $x$ প্রতি লেয়ারে শুধু একবার করেই আছে। রুট নোড (লেয়ার $0$) এর সাইজ $O(n)$, লেয়ার $1$ এর নোড এর সাইজ $O(\sqrt{n})$, লেয়ার $2$ এর এর নোড এর সাইজ $O(\sqrt{\sqrt{n}})$, ইত্যাদি। তাই প্রতি আপডেটে টাইম লাগবে $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$.

কিন্তু এটা অনেক ধীর গতিশীল। আমরা কি ইহাকে বর্তমানের পদ্ধতির চেয়ে দ্রুত গতিসম্পন্ন করিয়া তুলিতে পারি না? :grin:


স্ক্রট ট্রির ভিত্রে স্ক্রট ট্রি :open_mouth:


এটা দেখ যে আপডেট এর প্রধান সমস্যাটা হচ্ছে রুট নোড এর $b$ অ্যারেটা বারবার বিল্ড করার প্রয়োজন হওয়াটা. এটা অপটিমাইজ করার জন্য আমরা এই অ্যারেটাই বাদ দিয়ে দিতে পারি! $b$ অ্যারে বাদ দিয়ে আমরা রুট নোড এর জন্য আরেকটা স্ক্রট ট্রি রাখতে পারি. এটার নাম দেওয়া যাক $\text{index}$। এটা $b$ অ্যারের মতো একই কাজ করে— অনেকগুলো সেগমেন্ট এর কুয়েরির উত্তর একবারে দিয়ে দেওয়া। এটা খেয়াল করো যে $\text{index}$ টা শুধু রুট নোডের ই আছে, স্ক্রট ট্রি এর বাকি নোডগুলোর এটি নেই। তাদের জন্য তাদের $b$ অ্যারেই আছে।

আমরা একটা স্ক্রট ট্রি কে indexed বলবো,যদি এটার রুট নোডের $\text{index}$ থাকে.যে স্ক্রট ট্রি এর রুট নোড এ $b$ অ্যারে আছে সেটা_unindexed_। এটা খেয়াল করো যে $\text{index}$ নিজেই একটা unindexed স্ক্রট ট্রি।

এখন আমরা নিচের উপায়ে indexed ট্রি এর আপডেট করতে পারবো:

  • ট্রি টির $\text{prefixOp}$ ও $\text{suffixOp}$ $O(\sqrt{n})$ এ আপডেট করা।

  • $\text{index}$ আপডেট করবো। এটার সাইজ $O(\sqrt{n})$ এবং আমাদের শুধু এটার একটা উপাদান ই পরিবর্তন করতে হবে (যে ব্লকটি পরিবর্তিত হবে সেটি)। এই স্টেপ এর টাইম কম্প্লেক্সিটি $O(\sqrt{n})$। এই সেকশান এর শুরুতে বর্ণিত উপায়ে এই ধাপটি করা যাবে (“কম গতিসম্পন্ন” টা)।

  • যে চাইল্ড নোডটা পরিবর্তিত ব্লকটিকে নির্দেশ করে সেটাতে যাই এবং তাকে $O(\sqrt{n})$ এ “কম গতিসম্পন্ন” অ্যালগোরিদমটা দিয়ে আপডেট করি।

এটা খেয়াল করো যে কুয়েরি কম্প্লেক্সিটি এখনো $O(1)$: কেনো কুয়েরিতে আমাদের সর্বোচ্চ একবার $\text{index}$ টা ব্যবহার করা লাগবে, এবং এটা $O(1)$ সময় ই নেয়।

তাই পয়েন্ট আপডেট করার কম্প্লেক্সিটি $O(\sqrt{n})$ :)


ইম্প্লিমেন্টেশন :dizzy_face:


স্ক্রট ট্রি এর নিচের ইম্প্লিমেন্টেশনটা এই কাজগুলো করতে পারে: $O(n \cdot \log \log n)$ এ বিল্ড করা, $O(1)$ এ কুয়েরি উত্তর করা এবং $O(\sqrt{n})$ এ পয়েন্ট আপডেট করা।


SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);

inline int log2Up(int n) {
	int res = 0;
	while ((1 << res) < n) {
		res++;
	}
	return res;
}

class SqrtTree {
private:
	int n, lg, indexSz;
	vector<SqrtTreeItem> v;
	vector<int> clz, layers, onLayer;
	vector< vector<SqrtTreeItem> > pref, suf, between;
	
	inline void buildBlock(int layer, int l, int r) {
		pref[layer][l] = v[l];
		for (int i = l+1; i < r; i++) {
			pref[layer][i] = op(pref[layer][i-1], v[i]);
		}
		suf[layer][r-1] = v[r-1];
		for (int i = r-2; i >= l; i--) {
			suf[layer][i] = op(v[i], suf[layer][i+1]);
		}
	}
	
	inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
		int bSzLog = (layers[layer]+1) >> 1;
		int bCntLog = layers[layer] >> 1;
		int bSz = 1 << bSzLog;
		int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
		for (int i = 0; i < bCnt; i++) {
			SqrtTreeItem ans;
			for (int j = i; j < bCnt; j++) {
				SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
				ans = (i == j) ? add : op(ans, add);
				between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
			}
		}
	}
	
	inline void buildBetweenZero() {
		int bSzLog = (lg+1) >> 1;
		for (int i = 0; i < indexSz; i++) {
			v[n+i] = suf[0][i << bSzLog];
		}
		build(1, n, n + indexSz, (1 << lg) - n);
	}
	
	inline void updateBetweenZero(int bid) {
		int bSzLog = (lg+1) >> 1;
		v[n+bid] = suf[0][bid << bSzLog];
		update(1, n, n + indexSz, (1 << lg) - n, n+bid);
	}
	
	void build(int layer, int lBound, int rBound, int betweenOffs) {
		if (layer >= (int)layers.size()) {
			return;
		}
		int bSz = 1 << ((layers[layer]+1) >> 1);
		for (int l = lBound; l < rBound; l += bSz) {
			int r = min(l + bSz, rBound);
			buildBlock(layer, l, r);
			build(layer+1, l, r, betweenOffs);
		}
		if (layer == 0) {
			buildBetweenZero();
		} else {
			buildBetween(layer, lBound, rBound, betweenOffs);
		}
	}
	
	void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
		if (layer >= (int)layers.size()) {
			return;
		}
		int bSzLog = (layers[layer]+1) >> 1;
		int bSz = 1 << bSzLog;
		int blockIdx = (x - lBound) >> bSzLog;
		int l = lBound + (blockIdx << bSzLog);
		int r = min(l + bSz, rBound);
		buildBlock(layer, l, r);
		if (layer == 0) {
			updateBetweenZero(blockIdx);
		} else {
			buildBetween(layer, lBound, rBound, betweenOffs);
		}
		update(layer+1, l, r, betweenOffs, x);
	}
	
	inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
		if (l == r) {
			return v[l];
		}
		if (l + 1 == r) {
			return op(v[l], v[r]);
		}
		int layer = onLayer[clz[(l - base) ^ (r - base)]];
		int bSzLog = (layers[layer]+1) >> 1;
		int bCntLog = layers[layer] >> 1;
		int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
		int lBlock = ((l - lBound) >> bSzLog) + 1;
		int rBlock = ((r - lBound) >> bSzLog) - 1;
		SqrtTreeItem ans = suf[layer][l];
		if (lBlock <= rBlock) {
			SqrtTreeItem add = (layer == 0) ? (
				query(n + lBlock, n + rBlock, (1 << lg) - n, n)
			) : (
				between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
			);
			ans = op(ans, add);
		}
		ans = op(ans, pref[layer][r]);
		return ans;
	}
public:
	inline SqrtTreeItem query(int l, int r) {
		return query(l, r, 0, 0);
	}
	
	inline void update(int x, const SqrtTreeItem &item) {
		v[x] = item;
		update(0, 0, n, 0, x);
	}
	
	SqrtTree(const vector<SqrtTreeItem>& a)
		: n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
		clz[0] = 0;
		for (int i = 1; i < (int)clz.size(); i++) {
			clz[i] = clz[i >> 1] + 1;
		}
		int tlg = lg;
		while (tlg > 1) {
			onLayer[tlg] = (int)layers.size();
			layers.push_back(tlg);
			tlg = (tlg+1) >> 1;
		}
		for (int i = lg-1; i >= 0; i--) {
			onLayer[i] = max(onLayer[i], onLayer[i+1]);
		}
		int betweenLayers = max(0, (int)layers.size() - 1);
		int bSzLog = (lg+1) >> 1;
		int bSz = 1 << bSzLog;
		indexSz = (n + bSz - 1) >> bSzLog;
		v.resize(n + indexSz);
		pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
		suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
		between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
		build(0, 0, n, 0);
	}
};


প্রবলেম:

CodeChef - SEGPROD

সোর্স: E-Maxx



একই ক্যাটাগরির নিচের পোস্ট(গুলি) পড়ে দেখতে পারো:


  1. Offline Query Solution Trick
  2. Disjoint Set Union (Rank + Path Compression)
  3. Disjoint Set Union (Rank Compression)
  4. Merge Sort Tree (MST)


একই Difficulty এর বাকি পোস্টগুলোর লিস্ট দিয়ে দিচ্ছি, পড়ে দেখতে পারো:


  1. BDOI Practice Contest-2 Analysis
  2. BDOI Practice Contest-1 Analysis