Updating through Lazy:
নিচের ছবিটা দেখি,
এখন,এখানে 0-1 রেঞ্জের প্রতি ইনডেক্সের মান x বাড়াতে চাই,তাহলে প্রতি ইনডেক্সের লীফে গিয়ে বাড়িয়ে আসতে হবে।কি দরকার এত কষ্ট করে প্রতি লীফে লীফে গিয়ে মান আপডেট করার?আমরা যদি 0-1 রেঞ্জ যে নোডের অন্তর্ভূক্ত সেই নোডে(এখানে ২ নম্বর) x রেখে বলে দেয় যে, এর চাইল্ড গুলোর সাথে x যোগ হবে তাহলেই তো হয়ে যায়।এটাই হল লেজি টেকনিক।
আমরা lazy[] নামে একটা অ্যারে নিব।ইনিশিয়ালি সবগুলো নোডের lazy[] এর মান হবে 0।এরপর চেক করব আমরা বর্তমানে যে রেঞ্জে আছি সেটা যে রেঞ্জ আপডেট করতে চায় পুরোপুরি তার অন্তর্ভূক্ত কি না।যদি পুরোপুরি অন্তর্ভূক্ত হয় তাহলে তখনকার বর্তমান নোডের সাথে ভ্যালু যোগ করে দিতে হবে।আর সেই নোডের চাইল্ড থাকলে তাদের lazy[] মান আপডেট করতে হবে।আর আংশিকভাবে অন্তর্ভূক্ত হলে স্প্লিট করতে থাকতে হবে। আর একটা জিনিস চেক করতে হবে যে বর্তমান নোডের lazy[] মান 0 কি না? যদি শূন্য হয় তারমানে ঐ নোড টা আপডেটেড আছে।আর যদি 0 না হয় তার মানে নোড টা আপডেটেড না,তাই তার মান আপডেটেড করে তার Lazy[] এর মান 0 করে দিতে হবে।আর তার চাইল্ড থাকলে তাদের lazy[] মান আপডেট করে দিতে হবে।আপডেট করার স্যাম্পল কোড টা দেখি,
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void update_tree(int node,int a,int b,int i,int j,int value){ | |
| if(lazy[node]!=0){ //This node needs to be updated | |
| tree[node]+=lazy[node]; //update it | |
| if(a!=b){ | |
| lazy[node*2]+=lazy[node]; //mark child as lazy | |
| lazy[1+(node*2)]+=lazy[node]; //mark child as lazy | |
| } | |
| lazy[node]=0; //Reset it | |
| } | |
| if(a>b || a>j || b<i) return; //current segment is not within range | |
| if(a>=i and b<=j){ | |
| tree[node]+=value; | |
| if(a!=b) { // Not leaf node | |
| lazy[node*2] += value; | |
| lazy[node*2+1] += value; | |
| } | |
| return; | |
| } | |
| update_tree(node*2, a, (a+b)/2,i,j,value); // Updating left child | |
| update_tree(1+node*2,1+(a+b)/2,b,i,j,value); // Updating right child | |
| tree[node]=min(tree[node*2],tree[node*2+1]); // Updating root with max value | |
| } |
এতক্ষন যা বলছি,কোডটাও ঠিক ঐ রকমই।এখন আমরা হাতে-কলমে দেখে নিব কিভাবে অপারেশন গুলো হচ্ছে এবং কোডের সাথে মিলিয়ে দেখব।নিচের ছবিটা দেখি,
উপরের ছবিতে আমরা একটা কনসেপচুয়াল মিনিমাম সেগমেন্ট ট্রি এবং lazy[] নামে একটা অ্যারে দেখতে পাচ্ছি,যেটাতে বিভিন্ন নোডের lazy মান সেভ করে রাখব।এখন আমরা যদি 0-3 রেঞ্জের সব ইনডেক্সের মান 2 করে বাড়িয়ে দিতে চায় তাহলে কি ঘটবে?আমরা যদি update_tree(1,0,3,0,3,2) ফাংশন টা কল করি, তাহলে প্রথমে আমরা শুরু করব রুট নোড দিয়ে।আমরা দেখতে পাচ্ছি আমদের বর্তমান নোড 1 এর লেজি(lazy[1]=0) মান 0।তারমানে নোড টা আপডেটেড,তাই কোডের প্রথম if কন্ডিশন এক্সিকিউট হবে না।দ্বিতীয় if কন্ডিশনও এক্সিকিউট হবে না কারণ আমাদের বর্তমান রেঞ্জ(0-3) আপডেট রেঞ্জের(0-3) পুরোপুরি বাইরে নয়।তৃতীয় if কন্ডিশন টা এক্সিকিউট হবে কারণ আমাদের বর্তমান রেঞ্জ(0-3) পুরোপুরি আপডেট রেঞ্জের(0-3) অন্তর্ভূক্ত।তাই আর রুট নোডের(1 নম্বর) মান আপডেট(-1+2(value)=2=tree[1]) করে দিচ্ছি এবং তার চাইল্ড গুলোর(2 and 3 node) লেজি মান আপডেট(lazy[2]=2,lazy[3]=2) করে দিচ্ছি এবং আর কিছু না করে ফাংশন রিটার্ন করে দিচ্ছি।নিচের ছবি দেখলেই বুঝা যাবে,
1 নম্বর নোডেই যেহেতু পুরো আপডেট রেঞ্জ কাভার করে ফেলসে তাই 1 নম্বর নোডের মান আপডেট করে দিলাম।আর 1 নম্বর নোডের চাইল্ড 2 ও 3 এর লেজি মান আপডেট করে দিলাম।
এখন যদি update_tree(1,0,3,2,2,4) এই ফাংশন টা কল করি অর্থাৎ 2-2 রেঞ্জের ইনডেক্স গুলোর মান 4 করে বাড়াতে চাই ,তাহলে কি ঘটবে?প্রথমে দেখতে পাচ্ছি 1 নম্বর নোডের লেজি(lazy[1]=0) মান 0 তাই প্রথম if কন্ডিশন এক্সিকিউট হবে না।দ্বিতীয় if কন্ডিশনও এক্সিকিউট হবে না কারণ আমাদের বর্তমান রেঞ্জ(0-3) আপডেট রেঞ্জের(2-2) পুরোপুরি বাইরে নয়। এখন আছি 0-3 রেঞ্জে কিন্তু আমাদের কুয়েরি রেঞ্জ 2-2 অর্থাৎ বর্তমান রেঞ্জ(0-3) আংশিক ভাবে আপডেট রেঞ্জের(2-2) অন্তর্ভূক্ত।তাই আমদের বর্তমান রেঞ্জ কে স্প্লিট করে দুই ভাগে ভাগ করব(0-1 হল নোড 1 এ এবং 2-3 হল নোড 2 এ)।এখন যদি নোড 2 এ আসি,তাহলে দেখা যাচ্ছে নোড 2 এর লেজি(lazy[2]=2) মান 0 না,মানে প্রথম if কন্ডিশন এক্সিকিউট হবে।নোড 2 এর নতুন মান হবে 2+2(lazy[2])=4,সাথে সাথে এর লেজি মান(lazy[2]=0) রিসেট(0) করে দিব এবং 2 নম্বর নোডের চাইল্ড 4 এবং 5 এর লেজি মান আপডেট(lazy[4]=2,lazy[5]=2) করে দিচ্ছি।নিচের ছবিটা দেখলেই বুঝা যাবে,
এখন বর্তমান রেঞ্জ(0-1) যেহেতু কুয়েরি রেঞ্জের বাইরে,তাই দ্বিতীয় if কন্ডিশন এক্সিকিউট হবে এবং আর কিছু না করেই ফাংশন রিটার্ন করবে।এখন আমরা ডান দিকে যাব।সেখানে আমরা 3 নম্বর নোড চেক করব প্রথমে।যেহেতু এর লেজি(lazy[3]=2) মান 0 না,তাই এর নতুন আপডেটেড মান হবে -1+2(lazy[3])=1=tree[3]=1 এবং এর লেজি(lazy[3]=0) মান রিসেট করে দিব।এবং 3 নম্বর নোডের চাইল্ড 6 ও 7 নম্বর নোডের লেজি মান আপডেট(lazy[6]=2,lazy[7]=2) করে দিব।ছবিতে দেখি,
এখন আমাদের বর্তমান রেঞ্জ(2-3) যেহেতু আপডেট রেঞ্জের(2-2) সাথে আংশিক ভাবে ওভারল্যাপড তাই বর্তমান রেঞ্জ করে স্প্লিট করে দুই ভাগে(2-2 এবং 3-3) ভাগ করব।প্রথমে 6 নম্বর নোড(রেঞ্জ 2-2) চেক করি।6 নম্বর নোডের লেজি(lazy[6]=2) মান 0 না,তাই প্রথম if কন্ডিশন টা এক্সিকিউট হবে এবং এর আপডেটেড মান হয়ে -1+2(lazy[6])=1=tree[6] হবে।দ্বিতীয় if কন্ডিশনও এক্সিকিউট হবে না কারণ আমাদের আপডেট রেঞ্জ(2-2) বর্তমান রেঞ্জের(2-2) পুরোপুরি বাইরে নয়।আবার যেহেতু ৬ নম্বর নোডের রেঞ্জ(2-2) পুরোপুরি কুয়েরি রেঞ্জের(2-2) অন্তর্ভূক্ত তাই তৃতীয় if কন্ডিশন টা এক্সিকিউট হবে।এর সাথে ভ্যালু যোগ হবে।অতএব এর ট্রির মান হবে tree[6]=1+4=5।যেহেতু ৬ নম্বর নোডের কোন চাইল্ড নাই,তাই তৃতীয় if এর ভিতরের if কন্ডিশন টা এক্সিকিউট হবে না। ছবি তে দেখি,
এখন 7 নম্বর নোড চেক করি।7 নম্বর নোডের লেজি(lazy[7]=2) মান 0 না।তাই প্রথম if কন্ডিশন টা এক্সিকিউট হবে এবং এর আপডেটেড মান হবে tree[7]=4+2(lazy[7])=6।সাথে সাথে এর লেজি মান রিসেট(lazy[7]=0) করে দিব।এবং যেহেতু এর কো চাইল্ড নাই তাই আপডেট করা লাগবে না।আবার যেহেতু বর্তমান রেঞ্জ(3-3) পুরোপুরি আপডেট রেঞ্জের(2-2) বাইরে তাই দ্বিতীয় if এক্সিকিউট হবে এবং আর কিছু না করে ফাংশন রিটার্ন করে দিবে। ছবিতে দেখি,
উপরের ছবিতে দেখা যাচ্ছে,2 নম্বর মিনিমাম রিটার্ন করছে 4 এবং 3 নম্বর নোড রিটার্ন করছে 5।সুতরাং 1 নম্বর নোড তথা 1-3 রেঞ্জে মিনিমাম হবে 4।
1 নম্বর নোডেই যেহেতু পুরো আপডেট রেঞ্জ কাভার করে ফেলসে তাই 1 নম্বর নোডের মান আপডেট করে দিলাম।আর 1 নম্বর নোডের চাইল্ড 2 ও 3 এর লেজি মান আপডেট করে দিলাম।
এখন যদি update_tree(1,0,3,2,2,4) এই ফাংশন টা কল করি অর্থাৎ 2-2 রেঞ্জের ইনডেক্স গুলোর মান 4 করে বাড়াতে চাই ,তাহলে কি ঘটবে?প্রথমে দেখতে পাচ্ছি 1 নম্বর নোডের লেজি(lazy[1]=0) মান 0 তাই প্রথম if কন্ডিশন এক্সিকিউট হবে না।দ্বিতীয় if কন্ডিশনও এক্সিকিউট হবে না কারণ আমাদের বর্তমান রেঞ্জ(0-3) আপডেট রেঞ্জের(2-2) পুরোপুরি বাইরে নয়। এখন আছি 0-3 রেঞ্জে কিন্তু আমাদের কুয়েরি রেঞ্জ 2-2 অর্থাৎ বর্তমান রেঞ্জ(0-3) আংশিক ভাবে আপডেট রেঞ্জের(2-2) অন্তর্ভূক্ত।তাই আমদের বর্তমান রেঞ্জ কে স্প্লিট করে দুই ভাগে ভাগ করব(0-1 হল নোড 1 এ এবং 2-3 হল নোড 2 এ)।এখন যদি নোড 2 এ আসি,তাহলে দেখা যাচ্ছে নোড 2 এর লেজি(lazy[2]=2) মান 0 না,মানে প্রথম if কন্ডিশন এক্সিকিউট হবে।নোড 2 এর নতুন মান হবে 2+2(lazy[2])=4,সাথে সাথে এর লেজি মান(lazy[2]=0) রিসেট(0) করে দিব এবং 2 নম্বর নোডের চাইল্ড 4 এবং 5 এর লেজি মান আপডেট(lazy[4]=2,lazy[5]=2) করে দিচ্ছি।নিচের ছবিটা দেখলেই বুঝা যাবে,
এখন বর্তমান রেঞ্জ(0-1) যেহেতু কুয়েরি রেঞ্জের বাইরে,তাই দ্বিতীয় if কন্ডিশন এক্সিকিউট হবে এবং আর কিছু না করেই ফাংশন রিটার্ন করবে।এখন আমরা ডান দিকে যাব।সেখানে আমরা 3 নম্বর নোড চেক করব প্রথমে।যেহেতু এর লেজি(lazy[3]=2) মান 0 না,তাই এর নতুন আপডেটেড মান হবে -1+2(lazy[3])=1=tree[3]=1 এবং এর লেজি(lazy[3]=0) মান রিসেট করে দিব।এবং 3 নম্বর নোডের চাইল্ড 6 ও 7 নম্বর নোডের লেজি মান আপডেট(lazy[6]=2,lazy[7]=2) করে দিব।ছবিতে দেখি,
এখন আমাদের বর্তমান রেঞ্জ(2-3) যেহেতু আপডেট রেঞ্জের(2-2) সাথে আংশিক ভাবে ওভারল্যাপড তাই বর্তমান রেঞ্জ করে স্প্লিট করে দুই ভাগে(2-2 এবং 3-3) ভাগ করব।প্রথমে 6 নম্বর নোড(রেঞ্জ 2-2) চেক করি।6 নম্বর নোডের লেজি(lazy[6]=2) মান 0 না,তাই প্রথম if কন্ডিশন টা এক্সিকিউট হবে এবং এর আপডেটেড মান হয়ে -1+2(lazy[6])=1=tree[6] হবে।দ্বিতীয় if কন্ডিশনও এক্সিকিউট হবে না কারণ আমাদের আপডেট রেঞ্জ(2-2) বর্তমান রেঞ্জের(2-2) পুরোপুরি বাইরে নয়।আবার যেহেতু ৬ নম্বর নোডের রেঞ্জ(2-2) পুরোপুরি কুয়েরি রেঞ্জের(2-2) অন্তর্ভূক্ত তাই তৃতীয় if কন্ডিশন টা এক্সিকিউট হবে।এর সাথে ভ্যালু যোগ হবে।অতএব এর ট্রির মান হবে tree[6]=1+4=5।যেহেতু ৬ নম্বর নোডের কোন চাইল্ড নাই,তাই তৃতীয় if এর ভিতরের if কন্ডিশন টা এক্সিকিউট হবে না। ছবি তে দেখি,
এখন 7 নম্বর নোড চেক করি।7 নম্বর নোডের লেজি(lazy[7]=2) মান 0 না।তাই প্রথম if কন্ডিশন টা এক্সিকিউট হবে এবং এর আপডেটেড মান হবে tree[7]=4+2(lazy[7])=6।সাথে সাথে এর লেজি মান রিসেট(lazy[7]=0) করে দিব।এবং যেহেতু এর কো চাইল্ড নাই তাই আপডেট করা লাগবে না।আবার যেহেতু বর্তমান রেঞ্জ(3-3) পুরোপুরি আপডেট রেঞ্জের(2-2) বাইরে তাই দ্বিতীয় if এক্সিকিউট হবে এবং আর কিছু না করে ফাংশন রিটার্ন করে দিবে। ছবিতে দেখি,
উপরের ছবিতে দেখা যাচ্ছে,2 নম্বর মিনিমাম রিটার্ন করছে 4 এবং 3 নম্বর নোড রিটার্ন করছে 5।সুতরাং 1 নম্বর নোড তথা 1-3 রেঞ্জে মিনিমাম হবে 4।
Query Through Lazy:
কুয়েরি আর আপডেট ফাংশনের মধ্যে তেমন কোন পার্থক্য নাই।তাই, আপডেট টা বুঝলে কুয়েরি ফাংশন না বুঝার কোন কারণ নেই।কুয়েরি ফাংশন সহ সম্পূর্ণ কোড টা দেখে নেই,
সম্পূর্ন কোডঃ
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define mx 100005 | |
| #define inf 0x3f3f3f3f | |
| int arr[mx]; | |
| int tree[3*mx],lazy[3*mx]; | |
| void build_tree(int node,int a,int b){ //node=current node, a-b=current range | |
| if(a>b) return; //out of range | |
| if(a==b){ //Leaf node | |
| tree[node]=arr[a]; //initialize value | |
| return; | |
| } | |
| int mid=(a+b)/2; | |
| int left=node*2; | |
| int right=(node*2)+1; | |
| build_tree(left,a,mid); //Init left child | |
| build_tree(right,mid+1,b); //Init right child | |
| tree[node]=min(tree[left],tree[right]); //Init root value | |
| } | |
| void update_tree(int node,int a,int b,int i,int j,int value){ | |
| if(lazy[node]!=0){ //This node needs to be updated | |
| tree[node]+=lazy[node]; //update it | |
| if(a!=b){ | |
| lazy[node*2]+=lazy[node]; //mark child as lazy | |
| lazy[1+(node*2)]+=lazy[node]; //mark child as lazy | |
| } | |
| lazy[node]=0; //Reset it | |
| } | |
| if(a>b || a>j || b<i) return; //current segment is not within range | |
| if(a>=i and b<=j){ | |
| tree[node]+=value; | |
| if(a!=b) { // Not leaf node | |
| lazy[node*2] += value; | |
| lazy[node*2+1] += value; | |
| } | |
| return; | |
| } | |
| update_tree(node*2, a, (a+b)/2,i,j,value); // Updating left child | |
| update_tree(1+node*2,1+(a+b)/2,b,i,j,value); // Updating right child | |
| tree[node]=min(tree[node*2],tree[node*2+1]); // Updating root with max value | |
| } | |
| int query_tree(int node,int a,int b,int i,int j){ | |
| if(a>b || a>j || b<i) return -inf; // Out of range | |
| if(lazy[node]!=0){ // This node needs to be updated | |
| tree[node]+=lazy[node]; // Update it | |
| if(a!=b) { //not leaf node.mark it's child as lazy | |
| lazy[node*2] += lazy[node]; // Mark child as lazy | |
| lazy[node*2+1] += lazy[node]; // Mark child as lazy | |
| } | |
| lazy[node] = 0; // Reset it | |
| } | |
| if(a>=i && b<=j) // Current segment is totally within range [i, j] | |
| return tree[node]; | |
| int q1=query_tree(node*2,a,(a+b)/2,i,j); // Query left child | |
| int q2=query_tree(1+node*2,1+(a+b)/2,b,i,j); // Query right child | |
| int res=min(q1,q2); // Return final result | |
| return res; | |
| } | |
| int main() | |
| { | |
| int n; | |
| scanf("%d",&n); | |
| for(int i=0;i<n;i++) scanf("%d",&arr[i]); | |
| build_tree(1,0,n-1); | |
| memset(lazy,0,sizeof(lazy)); | |
| update_tree(1,0,n-1,0,3,5); //increment range [0,3] by 5 | |
| update_tree(1,0,n-1,7,10,12); // Incremenet range [7, 10] by 12 | |
| update_tree(1,0,n-1, 10,n-1,100); // Increment range [10, N-1] by 100 | |
| int ans=query_tree(1,0,n-1,0,n-1); //Get min value in range [0,n-1] | |
| cout<<ans<<endl; | |
| return 0; | |
| } |
Tree[node]+=(b-a+1)*value;
ReplyDeleteTree[node]+=(b-a+1)*lazy[node];
Ey 2 ta jinish correction kore diyen.Lekha ta valo chilo apner + guchano.
Nah ,Code thik e achey ..uporer 2 ta condition sum jokhon korte hobey tokhon lagey.
Delete