সেগমেন্ট ট্রি হল একটি ট্রি ডাটা স্ট্রাকচার,যেটা কতগুলো interval/segment কে স্টোর করে রাখে এবং সেখান থেকে একটা নির্দিষ্ট রেঞ্জের মধ্যকার সল্যুশন কুয়েরি করে বের করা যায়।এটা একটা Height Balanced Binary Tree এবং গঠনগতভাবে স্থিতিশীল।এই গাঠনিক স্থিতিশীলতার কারণে এটা Balanced Binary Tree এর চেয়ে কম ইফিশিয়েন্ট,কিন্তু এর রিকার্সিভ অপারেশনের কারণে এটা চিন্তা করা এবং কোড করা অপেক্ষাকৃত সহজ।
সেগমেন্ট ট্রি বুঝতে হলে রিকার্সন সম্পর্কে ভাল ধারণা থাকতে হবে।আর মার্জ সর্ট জানলে সেগমেন্ট ট্রি খুবই সহজ লাগবে।কারণ সেগমেন্ট ট্রি মার্জ সর্টের মতই Divide And Conquer পদ্ধতিতে কাজ করে।
একটা সেগমেন্ট ট্রির সাধারণত তিনটা অপারেশন থাকেঃ
1. Building Tree: To initialize the tree segment/interval
2. Updating Tree: To update the value of given range
3. Query Tree: To retrieve the value of segment/interval
Building Tree:
সেগমেন্ট ট্রি তে আমরা যে সল্যুশন চাই,সেগুলো ট্রির লীফে থাকে।আর সেগুলোর মার্জ করা সল্যুশন ট্রির ইন্টারনাল নোডে থাকে।নিচের ছবিটা দেখি,
ছবিঃসংগৃহীত
এটি একটি বাইনারি ট্রি।যেখানে x যদি রুট হয় তাহলে 2*x এবং 2*x+1 হবে তার চাইল্ড।এর k তম লেভেলের ডিসেন্ডেন্ট গুলো 2^k এর (2^(k+1))-1 এর মধ্যে।বাকিটা কোড দেখে বুঝার চেষ্টা করি,
এখানে আমরা ১ কে রুট নোড ধরে শুরু করেছি।ধবি,আমাদের রেঞ্জ a থেকে b।যেহুতু আমাদের ডেটা গুলো লীফে স্টোর করব,তাই যতক্ষন না a=b হবে অর্থ্যাৎ লীফ নোডে না পৌছব তখন ঐ রেঞ্জ টাকে রিকার্সিভ্লি স্প্লিট করতে থাকব।আর লীফে পৌছে গেলেই সেখানে ডেটা tree[] তে স্টোর করে ফাংশন রিটার্ন করে দিব।এবং উপরে উঠার সময় তাদের মার্জ করা করা সল্যুশনও tree[] তে রেখে দিব।
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]; //why? ;) | |
| 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]=max(tree[left],tree[right]); //Init root value | |
| } | |
| int main() | |
| { | |
| int n; | |
| scanf("%d",&n); | |
| for(int i=0;i<n;i++) scanf("%d",&arr[i]); | |
| build_tree(1,0,n-1); | |
| return 0; | |
| } |
Updating Tree:
আমাদের কুয়েরির মেইন ডেটা গুলো যেহুতু লীফে থাকে,আপডেটও করতে হবে লীফে।আগের মতই রেঞ্জ স্প্লিট করতে করতে যখন আমরা লীফে পৌছে যাব তখন তার সেটার মান আপডেট করে দিব।আর উপরে উঠার সময় ইন্টারনাল নোডের সল্যুশন গুলো মার্জ হয়ে আপডেট হয়ে যাবে।আপডেটের স্যাম্পল কোড টা দেখি,
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){ //[a,b]=current range [i,j]=to be updated | |
| if(a>b or a>j or b<i) //current segment is not within range [i,j] | |
| return; | |
| if(a==b){ //Leaf node | |
| tree[node]+=value; | |
| return; | |
| } | |
| int mid=(a+b)/2; | |
| int left=node*2; | |
| int right=(node*2)+1; | |
| update_tree(left,a,mid,i,j,value); //updating left child | |
| update_tree(right,mid+1,b,i,j,value); //updating right child | |
| tree[node]=max(tree[left],tree[right]); //updating root with max value | |
| } | |
Query Tree:
কুয়েরি করার সময় আমরা চেক করব বর্তমানে আমরা যে রেঞ্জে আছি সেটা রিলেভেন্ট কি না? অর্থাৎ এখন যে রেঞ্জে আছি তার পুরোটা কুয়েরি রেঞ্জের অন্তর্ভূক্ত হলে সেই নোডের সল্যুশন রিটার্ন করব।আর যদি আংশিকভাবে কুয়েরি রেঞ্জের অনর্ভূক্ত হয় তাহলে রিলেভেন্ট রেঞ্জ পাবার জন্য বর্তমান রেঞ্জকে স্প্লিট করতে থাকব।আর যদি বর্তমান রেঞ্জ পুরোপুরি কুয়েরি রেঞ্জের বাইরে হয় তাহলে এমন একটা ভ্যালু রিটার্ন করব যেন সেটা মেইন সল্যুশনে কোন ইফেক্ট না ফেলে। যেমন যোগফল বের করার সময় 0 রিটার্ন করতে পারি,ম্যাক্সিমাম ভ্যালু বের করার -infinity সময় বা মিনিমাম ভ্যালু বের করার সময় infinity রিটার্ন করতে পারি।কুয়েরি ফাংশনের কোডটা দেখি,
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
| int query_tree(int node,int a,int b,int i,int j){ | |
| if(a>b or a>j or b<i) return -inf; //out of range | |
| if(a>=i and b<=j) //current segment is totally in range [i,j] | |
| return tree[node]; | |
| int left=node*2; | |
| int right=node*2+1; | |
| int mid =(a+b)/2; | |
| int q1=query_tree(left,a,mid,i,j); | |
| int q2=query_tree(right,mid+1,b,i,j); | |
| int res=max(q1,q2); | |
| return res; | |
| } |
সম্পূর্ন কোডঃ
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]; //why? ;) | |
| void build_tree(int node,int a,int b){ //node=current node, b-e=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]=max(tree[left],tree[right]); //Init root value | |
| } | |
| void update_tree(int node,int a,int b,int i,int j,int value){ //[a,b]=current range [i,j]=to be updated | |
| if(a>b or a>j or b<i) //current segment is not within range [i,j] | |
| return; | |
| if(a==b){ //Leaf node | |
| tree[node]+=value; | |
| return; | |
| } | |
| int mid=(a+b)/2; | |
| int left=node*2; | |
| int right=(node*2)+1; | |
| update_tree(left,a,mid,i,j,value); //updating left child | |
| update_tree(right,mid+1,b,i,j,value); //updating right child | |
| tree[node]=max(tree[left],tree[right]); //updating root with max value | |
| } | |
| int query_tree(int node,int a,int b,int i,int j){ | |
| if(a>b or a>j or b<i) return -inf; //out of range | |
| if(a>=i and b<=j) //current segment is totally in range [i,j] | |
| return tree[node]; | |
| int left=node*2; | |
| int right=node*2+1; | |
| int mid =(a+b)/2; | |
| int q1=query_tree(left,a,mid,i,j); | |
| int q2=query_tree(right,mid+1,b,i,j); | |
| int res=max(q1,q2); | |
| 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); | |
| update_tree(1,0,n-1,0,6,5); //increment range [0,6] 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 max value in range [0,n-1] | |
| cout<<ans<<endl; | |
| return 0; | |
| } |
Complexity:
সেগমেন্ট ট্রি অ্যারে কে বারবার দুই ভাগে ভাগ করে,তাই ট্রি এর ডেপথ হবে log(n)।অতএব,প্রতিটা আপডেট এবং কুয়েরির কমপ্লেক্সিটি O(log n)।সেগমেন্ট ট্রি বিল্ড করার ক্ষেত্রে যেহুতু n টি আপডেট হয়েছে,তাই সেক্ষেত্রে কমপ্লেক্সিটি O(n log n)।
সেগমেন্ট ট্রি শিখা হয়ে গেলে লেজি প্রপাগেশন শিখে নিতে হবে।এটা সেগমেন্ট ট্রির দারুণ একটা অপটিমাইজেশন।
সেগমেন্ট ট্রি শিখা হয়ে গেলে লেজি প্রপাগেশন শিখে নিতে হবে।এটা সেগমেন্ট ট্রির দারুণ একটা অপটিমাইজেশন।
Related Problems & Solution:
Solution: https://ideone.com/3b9GOx
2. LightOj 1112 - Curious Robin Hood
Solution:https://ideone.com/HPAoJR
2. LightOj 1112 - Curious Robin Hood
Solution:https://ideone.com/HPAoJR
No comments:
Post a Comment