সেগমেন্ট ট্রি (Sum,max,update,query)

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

 Code:

#include<bits/stdc++.h>
using namespace std;
int tree[1000];
int arr[100];
int seg(int parent_node, int first_index_no, int last_index_no)
{
    if(first_index_no>last_index_no) return 0;

    if(first_index_no==last_index_no){//two index are equal that
        tree[parent_node]=arr[last_index_no];
        cout<<"left child = "<<arr[last_index_no]<<endl;
        return 0;
    }
    int mid = (first_index_no+last_index_no)/2;
    int left_node = parent_node*2;
    int right_node = parent_node*2+1;
    seg(left_node, first_index_no, mid);
    seg(right_node, mid+1, last_index_no );
    tree[parent_node]=(tree[left_node]+tree[right_node]);
    cout<<"Current sum = "<<tree[parent_node]<<"   node no = "<<parent_node<<endl;

    return tree[parent_node];

}
int main()
{
    int a,b,c;

    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        arr[i]=rand()%10;
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    int x = seg(1,0,n-1);
    cout<<"The sum of segment tree is = "<<x<<endl;
    return 0;
}

input:

5
1 7 4 0 9

 

Output:

left child = 1
left child = 7
Current sum = 8   node no = 4
left child = 4
Current sum = 12   node no = 2
left child = 0
left child = 9
Current sum = 9   node no = 3
Current sum = 21   node no = 1
The sum of segment tree is = 21

For max...

Code:

Just include max function..
#include<bits/stdc++.h>
using namespace std;
int tree[1000];
int arr[100];
int seg(int parent_node, int first_index_no, int last_index_no)
{
    if(first_index_no>last_index_no) return 0;

    if(first_index_no==last_index_no){//two index are equal that
        tree[parent_node]=arr[last_index_no];
        cout<<"left child = "<<arr[last_index_no]<<endl;
        return 0;
    }
    int mid = (first_index_no+last_index_no)/2;
    int left_node = parent_node*2;
    int right_node = parent_node*2+1;
    seg(left_node, first_index_no, mid);
    seg(right_node, mid+1, last_index_no );

    tree[parent_node]=max(tree[left_node],tree[right_node]); //just including max function

    cout<<"Current max = "<<tree[parent_node]<<"   node no = "<<parent_node<<endl;

    return tree[parent_node];

}
int main()
{
    int a,b,c;

    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        arr[i]=rand()%10;
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    int x = seg(1,0,n-1);
    cout<<"The sum of segment tree is = "<<x<<endl;
    return 0;
}

Code for build tree, query and update:

#include<bits/stdc++.h>
using namespace std;
int tree[100000];
int arr[10000];
int seg(int parent_node, int first_index_no, int last_index_no)
{
    if(first_index_no>last_index_no) return 0;

    if(first_index_no==last_index_no){//two index are equal that
        tree[parent_node]=arr[last_index_no];
        cout<<"left child = "<<arr[last_index_no]<<endl;
        return 0;
    }
    int mid = (first_index_no+last_index_no)/2;
    int left_node = parent_node*2;
    int right_node = parent_node*2+1;
    seg(left_node, first_index_no, mid);
    seg(right_node, mid+1, last_index_no );
    tree[parent_node]=(tree[left_node]+tree[right_node]);
    cout<<"Current max = "<<tree[parent_node]<<"   node no = "<<parent_node<<endl;

    return tree[parent_node];
}



int quesum(int parent_node, int first_index_no, int last_index_no, int first_que_index, int last_que_index)
{
    if(first_index_no>last_que_index||last_index_no<first_que_index){
            cout<<"Out side query...for "<<first_index_no  <<" to "<<last_index_no<<endl;
            return 0;
    }
    if(first_index_no>=first_que_index&&last_index_no<=last_que_index){
        cout<<"In side query...for "<<first_index_no  <<" to "<<last_index_no<<endl;
        cout<<"The value is = "<<tree[parent_node]<<endl;
        return tree[parent_node];
    }
    int mid = (first_index_no+last_index_no)/2;
    int left_node = parent_node*2;
    int right_node = parent_node*2+1;

    return quesum(left_node, first_index_no, mid,first_que_index,last_que_index) + quesum(right_node, mid+1, last_index_no, first_que_index,last_que_index);


}



int update(int parent_node, int first_index_no, int last_index_no, int update_index, int update_value)
{
    if(first_index_no>update_index||last_index_no<update_index) return 0;

    if(first_index_no==last_index_no&&first_index_no==update_index){//two index are equal that
        tree[parent_node]=update_value;
        arr[update_index]=update_value;
        cout<<"left child = "<<arr[last_index_no]<<endl;
        return 0;
    }
    int mid = (first_index_no+last_index_no)/2;
    int left_node = parent_node*2;
    int right_node = parent_node*2+1;
    update(left_node, first_index_no, mid,update_index,update_value);
    update(right_node, mid+1, last_index_no,update_index,update_value);
    tree[parent_node]=(tree[left_node]+tree[right_node]);
    return tree[parent_node];
}



int main()
{
    int a,b,c;

    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        arr[i]=rand()%10;
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    int x = seg(1,0,n-1);
    cout<<"The sum of segment tree is = "<<x<<endl;
    cout<<endl<<endl;

    int p,q;
    cin>>p>>q;

    int xx = quesum(1,0,n-1,p,q);
    cout<<"The sum of "<<p<<" index to "<<q<<" is = "<<xx<<endl;

    int r,t;
    cin>>r>>t;
    int z = update(1,0,n-1,r,t);
    cout<<"The sum of updated segment tree is = "<<z<<endl;


    cout<<"This part is completed......."<<endl<<endl<<endl;
    x = seg(1,0,n-1);
    cout<<"The sum of segment tree is = "<<x<<endl;
    cout<<endl<<endl;

    return 0;
}