স্কোয়ার্ট ট্রি#
একটি অ্যারে $a$ দেওয়া আছে যাতে $n$ উপাদান আছে এবং একটি অপারেশন $\circ$ যা সাহচর্য ধর্ম পূরণ করে: $(x \circ y) \circ z = x \circ (y \circ z)$ যেকোনো $x$, $y$, $z$-এর জন্য সত্য।
তাই, $\gcd$, $\min$, $\max$, $+$, $\text{and}$, $\text{or}$, $\text{xor}$, ইত্যাদি অপারেশন এই শর্ত পূরণ করে।
এছাড়াও আমাদের কিছু কোয়েরি $q(l, r)$ আছে। প্রতিটি কোয়েরির জন্য, আমাদের $a_l \circ a_{l+1} \circ \dots \circ a_r$ গণনা করতে হবে।
স্কোয়ার্ট ট্রি $O(n \cdot \log \log n)$ প্রিপ্রসেসিং সময় এবং $O(n \cdot \log \log n)$ মেমরি ব্যবহার করে $O(1)$ সময়ে এই কোয়েরি প্রক্রিয়া করতে পারে।
বর্ণনা#
স্কোয়ার্ট ডিকম্পোজিশন তৈরি#
একটি স্কোয়ার্ট ডিকম্পোজিশন তৈরি করি। আমরা অ্যারেকে $\sqrt{n}$ ব্লকে ভাগ করি, প্রতিটি ব্লকের আকার $\sqrt{n}$। প্রতিটি ব্লকের জন্য, আমরা গণনা করি:
- যেসব কোয়েরি ব্লকের মধ্যে থাকে এবং ব্লকের শুরুতে শুরু হয় তাদের উত্তর ($\text{prefixOp}$)
- যেসব কোয়েরি ব্লকের মধ্যে থাকে এবং ব্লকের শেষে শেষ হয় তাদের উত্তর ($\text{suffixOp}$)
এবং আমরা একটি অতিরিক্ত অ্যারে গণনা করব:
- $\text{between}_{i, j}$ ($i \le j$-এর জন্য) - যে কোয়েরি $i$ ব্লকের শুরুতে শুরু হয় এবং $j$ ব্লকের শেষে শেষ হয় তার উত্তর। লক্ষ্য করুন আমাদের $\sqrt{n}$ ব্লক আছে, তাই এই অ্যারের আকার হবে $O(\sqrt{n}^2) = O(n)$।
উদাহরণ দেখি।
ধরি $\circ$ হলো $+$ (আমরা একটি সেগমেন্টে যোগফল গণনা করি) এবং আমাদের নিম্নলিখিত অ্যারে $a$ আছে:
{1, 2, 3, 4, 5, 6, 7, 8, 9}
এটি তিনটি ব্লকে ভাগ হবে: {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}।
$\text{between}$ অ্যারে হলো:
{
{6, 21, 45},
{0, 15, 39},
{0, 0, 24}
}(আমরা ধরে নিই $i > j$ যেখানে অবৈধ উপাদানগুলো শূন্য দিয়ে পূরণ করা)
স্পষ্টতই এই অ্যারেগুলো $O(n)$ সময় ও মেমরিতে সহজেই গণনা করা যায়।
আমরা ইতিমধ্যে এই অ্যারে ব্যবহার করে কিছু কোয়েরি উত্তর দিতে পারি। যদি কোয়েরি একটি ব্লকে না থাকে, আমরা এটিকে তিনটি অংশে ভাগ করতে পারি: একটি ব্লকের সাফিক্স, তারপর পরপর কিছু ব্লকের সেগমেন্ট এবং তারপর একটি ব্লকের প্রিফিক্স। আমরা $\text{suffixOp}$ থেকে একটি মান, তারপর $\text{between}$ থেকে একটি মান, তারপর $\text{prefixOp}$ থেকে একটি মানে আমাদের অপারেশন নিয়ে কোয়েরি উত্তর দিতে পারি।
কিন্তু যদি আমাদের কোয়েরি সম্পূর্ণভাবে একটি ব্লকে থাকে, তাহলে এই তিনটি অ্যারে দিয়ে প্রক্রিয়া করা যায় না। তাই, আমাদের কিছু করতে হবে।
একটি ট্রি তৈরি#
আমরা শুধু সম্পূর্ণভাবে একটি ব্লকে থাকা কোয়েরি উত্তর দিতে পারি না। কিন্তু যদি আমরা প্রতিটি ব্লকের জন্য উপরে বর্ণিত একই স্ট্রাকচার তৈরি করি? হ্যাঁ, আমরা করতে পারি। এবং আমরা রিকার্সিভভাবে এটি করি, যতক্ষণ না ব্লকের আকার $1$ বা $2$ হয়। এই ব্লকগুলোর উত্তর $O(1)$-এ সহজেই গণনা করা যায়।
তাই, আমরা একটি ট্রি পাই। ট্রি-র প্রতিটি নোড অ্যারের কোনো সেগমেন্ট উপস্থাপন করে। $k$ দৈর্ঘ্যের অ্যারে সেগমেন্ট উপস্থাপনকারী নোডের $\sqrt{k}$ চাইল্ড আছে — প্রতিটি ব্লকের জন্য একটি। প্রতিটি নোডে উপরে বর্ণিত তিনটি অ্যারেও আছে যা এর সেগমেন্টের জন্য। ট্রি-র রুট পুরো অ্যারে উপস্থাপন করে। $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(1)$ সময়ে উত্তর গণনা করা যায়) অথবা প্রথম সেগমেন্ট পাই যেখানে আমাদের কোয়েরি সম্পূর্ণভাবে একটি ব্লকে থাকে না। প্রথম সেকশনে দেখুন কীভাবে এই ক্ষেত্রে কোয়েরি উত্তর দিতে হয়।
ঠিক আছে, এখন আমরা প্রতি কোয়েরিতে $O(\log \log n)$ করতে পারি। এটি কি আরও দ্রুত করা যায়?
কোয়েরি কমপ্লেক্সিটি অপটিমাইজ করা#
সবচেয়ে স্পষ্ট অপটিমাইজেশন হলো প্রয়োজনীয় ট্রি নোড বাইনারি সার্চ করা। বাইনারি সার্চ ব্যবহার করে, আমরা প্রতি কোয়েরিতে $O(\log \log \log n)$ কমপ্লেক্সিটিতে পৌঁছাতে পারি। আরও দ্রুত করা কি সম্ভব?
উত্তর হ্যাঁ। নিম্নলিখিত দুটি বিষয় ধরে নিই:
- প্রতিটি ব্লকের আকার দুই-এর ঘাত।
- প্রতিটি স্তরে সব ব্লক সমান।
এটি অর্জন করতে, আমরা অ্যারেতে কিছু শূন্য উপাদান যোগ করতে পারি যেন এর আকার দুই-এর ঘাত হয়।
যখন আমরা এটি ব্যবহার করি, কিছু ব্লকের আকার দুই-এর ঘাত হতে দ্বিগুণ বড় হতে পারে, কিন্তু এটি এখনও $O(\sqrt{k})$ আকারের এবং আমরা একটি সেগমেন্টে অ্যারে তৈরির লিনিয়ার কমপ্লেক্সিটি বজায় রাখি।
এখন, আমরা সহজেই পরীক্ষা করতে পারি কোয়েরি সম্পূর্ণভাবে $2^k$ আকারের একটি ব্লকে থাকে কিনা। কোয়েরির রেঞ্জ $l$ এবং $r$ (০-ইনডেক্সিং) বাইনারিতে লিখি। যেমন, ধরি $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)$) ইত্যাদি উপাদান ঢাকে। আমরা দেখি একটি ব্লক দ্বারা ঢাকা অবস্থানের ইনডেক্স শুধু $k$টি (আমাদের ক্ষেত্রে, $4$) শেষ বিটে ভিন্ন হতে পারে। আমাদের ক্ষেত্রে $l$ এবং $r$-এর চারটি সর্বনিম্ন বিট ছাড়া সব সমান, তাই তারা একটি ব্লকে আছে।
তাই, আমাদের পরীক্ষা করতে হবে $k$টির বেশি ক্ষুদ্রতম বিট ভিন্ন কিনা (অথবা $l\ \text{xor}\ r$ $2^k-1$ অতিক্রম করে কিনা)।
এই পর্যবেক্ষণ ব্যবহার করে, আমরা কোয়েরি দ্রুত উত্তর দিতে উপযুক্ত একটি স্তর খুঁজে পেতে পারি। কীভাবে:
প্রতিটি $i$-এর জন্য যা অ্যারের আকার অতিক্রম করে না, $1$-এর সমান সর্বোচ্চ বিট খুঁজি। দ্রুত করতে, আমরা ডিপি এবং একটি আগে থেকে গণনা করা অ্যারে ব্যবহার করি।
এখন, প্রতিটি $q(l, r)$-এর জন্য $l\ \text{xor}\ r$-এর সর্বোচ্চ বিট খুঁজি এবং, এই তথ্য ব্যবহার করে, যে স্তরে কোয়েরি সহজে প্রক্রিয়া করা যায় সেটি বেছে নেওয়া সহজ। এখানেও আমরা একটি আগে থেকে গণনা করা অ্যারে ব্যবহার করতে পারি।
আরও বিস্তারিতের জন্য, নিচের কোড দেখুন।
তাই, এটি ব্যবহার করে, আমরা প্রতিটি $O(1)$-এ কোয়েরি উত্তর দিতে পারি। :)
উপাদান আপডেট করা#
আমরা স্কোয়ার্ট ট্রি-তে উপাদান আপডেটও করতে পারি। একক উপাদান আপডেট এবং সেগমেন্টে আপডেট উভয়ই সমর্থিত।
একটি একক উপাদান আপডেট করা#
একটি কোয়েরি $\text{update}(x, val)$ বিবেচনা করি যা $a_x = val$ অ্যাসাইনমেন্ট করে। আমাদের এই কোয়েরি যথেষ্ট দ্রুত সম্পাদন করতে হবে।
সরল পদ্ধতি#
প্রথমে, দেখি একটি একক উপাদান পরিবর্তন হলে ট্রি-তে কী বদলায়। $l$ দৈর্ঘ্যের একটি ট্রি নোড এবং এর অ্যারে: $\text{prefixOp}$, $\text{suffixOp}$ ও $\text{between}$ বিবেচনা করি। দেখা সহজ যে $\text{prefixOp}$ এবং $\text{suffixOp}$-এর শুধু $O(\sqrt{l})$ উপাদান পরিবর্তন হয় (শুধু পরিবর্তিত উপাদানের ব্লকের ভেতরে)। $\text{between}$-এ $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)$।
কিন্তু এটি খুব ধীর। আরও দ্রুত করা কি সম্ভব?
স্কোয়ার্ট-ট্রি-র ভেতরে একটি স্কোয়ার্ট-ট্রি#
লক্ষ্য করুন আপডেটের বটলনেক হলো রুট নোডের $\text{between}$ পুনর্নির্মাণ। ট্রি অপটিমাইজ করতে, এই অ্যারে বাদ দিই! $\text{between}$ অ্যারের পরিবর্তে, আমরা রুট নোডের জন্য আরেকটি স্কোয়ার্ট-ট্রি সংরক্ষণ করি। একে $\text{index}$ বলি। এটি $\text{between}$-এর মতোই ভূমিকা পালন করে — ব্লকের সেগমেন্টে কোয়েরি উত্তর দেয়। লক্ষ্য করুন বাকি ট্রি নোডে $\text{index}$ নেই, তারা তাদের $\text{between}$ অ্যারে রাখে।
একটি স্কোয়ার্ট-ট্রি ইনডেক্সড, যদি এর রুট নোডে $\text{index}$ থাকে। রুট নোডে $\text{between}$ অ্যারে সহ একটি স্কোয়ার্ট-ট্রি আনইনডেক্সড। লক্ষ্য করুন $\text{index}$ নিজে আনইনডেক্সড।
তাই, একটি ইনডেক্সড ট্রি আপডেট করার অ্যালগরিদম নিম্নরূপ:
$\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})$। :)
সেগমেন্ট আপডেট করা#
স্কোয়ার্ট-ট্রি সেগমেন্টে উপাদান অ্যাসাইন করার মতো কাজও করতে পারে। $\text{massUpdate}(x, l, r)$ মানে সব $l \le i \le r$-এর জন্য $a_i = x$।
এটি করার দুটি পদ্ধতি আছে: একটি $O(\sqrt{n}\cdot \log \log n)$-এ $\text{massUpdate}$ করে, প্রতি কোয়েরি $O(1)$ রেখে। দ্বিতীয়টি $O(\sqrt{n})$-এ $\text{massUpdate}$ করে, কিন্তু কোয়েরি কমপ্লেক্সিটি $O(\log \log n)$ হয়।
আমরা সেগমেন্ট ট্রি-র মতোই লেজি প্রোপাগেশন করব: কিছু নোডকে লেজি হিসেবে চিহ্নিত করি, মানে প্রয়োজনে পুশ করব। কিন্তু সেগমেন্ট ট্রি থেকে একটি পার্থক্য: নোড পুশ করা ব্যয়বহুল, তাই কোয়েরিতে এটি করা যায় না। স্তর $0$-তে নোড পুশ করতে $O(\sqrt{n})$ সময় লাগে। তাই, কোয়েরির ভেতরে নোড পুশ করি না, শুধু দেখি বর্তমান নোড বা এর প্যারেন্ট লেজি কিনা, এবং কোয়েরি করার সময় সেটি বিবেচনা করি।
প্রথম পদ্ধতি#
প্রথম পদ্ধতিতে, আমরা বলি শুধু স্তর $1$-এর ($O(\sqrt{n}$) দৈর্ঘ্যের) নোডগুলো লেজি হতে পারে। এমন নোড পুশ করলে, এটি নিজে সহ সম্পূর্ণ সাবট্রি $O(\sqrt{n}\cdot \log \log n)$-এ আপডেট করে। $\text{massUpdate}$ প্রক্রিয়া নিম্নরূপ:
স্তর $1$-এর নোড এবং তাদের সংশ্লিষ্ট ব্লক বিবেচনা করুন।
কিছু ব্লক সম্পূর্ণভাবে $\text{massUpdate}$ দ্বারা ঢাকা। তাদের $O(\sqrt{n})$-এ লেজি চিহ্নিত করুন।
কিছু ব্লক আংশিকভাবে ঢাকা। লক্ষ্য করুন এই ধরনের সর্বোচ্চ দুটি ব্লক আছে। তাদের $O(\sqrt{n}\cdot \log \log n)$-এ পুনর্নির্মাণ করুন। যদি তারা লেজি থাকে, সেটি বিবেচনা করুন।
আংশিকভাবে ঢাকা ব্লকের জন্য $\text{prefixOp}$ এবং $\text{suffixOp}$ $O(\sqrt{n})$-এ আপডেট করুন (কারণ এই ধরনের শুধু দুটি ব্লক আছে)।
$\text{index}$ $O(\sqrt{n}\cdot \log \log n)$-এ পুনর্নির্মাণ করুন।
তাই আমরা দ্রুত $\text{massUpdate}$ করতে পারি। কিন্তু লেজি প্রোপাগেশন কোয়েরিতে কী প্রভাব ফেলে? নিম্নলিখিত পরিবর্তন হবে:
যদি আমাদের কোয়েরি সম্পূর্ণভাবে একটি লেজি ব্লকে থাকে, লেজি বিবেচনায় নিয়ে গণনা করুন। $O(1)$।
যদি আমাদের কোয়েরি একাধিক ব্লক নিয়ে গঠিত হয়, যার কিছু লেজি, আমাদের শুধু বামতম এবং ডানতম ব্লকে লেজি যত্ন নিতে হবে। বাকি ব্লকগুলো $\text{index}$ ব্যবহার করে গণনা করা হয়, যা ইতিমধ্যে লেজি ব্লকের উত্তর জানে (কারণ প্রতিটি পরিবর্তনের পর এটি পুনর্নির্মিত)। $O(1)$।
কোয়েরি কমপ্লেক্সিটি $O(1)$ থেকে যায়।
দ্বিতীয় পদ্ধতি#
এই পদ্ধতিতে, প্রতিটি নোড লেজি হতে পারে (রুট ছাড়া)। এমনকি $\text{index}$-এর নোডও লেজি হতে পারে। তাই, কোয়েরি প্রক্রিয়া করার সময়, সব প্যারেন্ট নোডে লেজি ট্যাগ দেখতে হবে, অর্থাৎ কোয়েরি কমপ্লেক্সিটি হবে $O(\log \log n)$।
কিন্তু $\text{massUpdate}$ দ্রুত হয়। এটি নিম্নলিখিতভাবে দেখায়:
কিছু ব্লক সম্পূর্ণভাবে $\text{massUpdate}$ দ্বারা ঢাকা। তাই, তাদের লেজি ট্যাগ যোগ হয়। এটি $O(\sqrt{n})$।
আংশিকভাবে ঢাকা ব্লকের জন্য $\text{prefixOp}$ এবং $\text{suffixOp}$ $O(\sqrt{n})$-এ আপডেট করুন (কারণ এই ধরনের শুধু দুটি ব্লক আছে)।
ইনডেক্স আপডেট করতে ভুলবেন না। এটি $O(\sqrt{n})$ (আমরা একই $\text{massUpdate}$ অ্যালগরিদম ব্যবহার করি)।
আনইনডেক্সড সাবট্রি-র জন্য $\text{between}$ অ্যারে আপডেট করুন।
আংশিকভাবে ঢাকা ব্লক উপস্থাপনকারী নোডে যান এবং রিকার্সিভভাবে $\text{massUpdate}$ কল করুন।
লক্ষ্য করুন রিকার্সিভ কলে আমরা প্রিফিক্স বা সাফিক্স $\text{massUpdate}$ করি। কিন্তু প্রিফিক্স এবং সাফিক্স আপডেটের জন্য সর্বোচ্চ একটি আংশিকভাবে ঢাকা চাইল্ড থাকতে পারে। তাই, আমরা স্তর $1$-এ একটি নোড, স্তর $2$-এ দুটি নোড এবং যেকোনো গভীর স্তরে দুটি নোড ভিজিট করি। তাই, টাইম কমপ্লেক্সিটি $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$। এখানে পদ্ধতিটি সেগমেন্ট ট্রি ম্যাস আপডেটের অনুরূপ।
ইমপ্লিমেন্টেশন#
নিম্নলিখিত স্কোয়ার্ট ট্রি-র ইমপ্লিমেন্টেশন এই অপারেশনগুলো সম্পাদন করতে পারে: $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);
}
};