Segment Tree with lazzy
#include<iostream>
using namespace std;
int tree[300005];
class Node{
public:
int data;
int lazzy;
Node* parent,*left,*right;
int leftLimit,rightLimit;
};
void
buildSeg(Node* root,int st,int en){
cout<<"("<<st<<",
"<<en<<")"<<endl;
root->leftLimit=st;
root->rightLimit=en;
if(st==en){
root->data=0;
root->lazzy=0;
//cout<<"Data seted to
:"<<root->data<<endl;
//return root->data;
return;
}
int mid=(st+en)/2;
Node* leftC,*rightC;
leftC=new Node;
rightC=new Node;
leftC->parent=root;
rightC->parent=root;
leftC->left=nullptr;
leftC->right=nullptr;
rightC->left=nullptr;
rightC->right=nullptr;
root->left=leftC;
root->right=rightC;
//int l,r;
buildSeg(leftC,st,mid);
buildSeg(rightC,mid+1,en);
//cout<<"Backed data is
("<<st<<", "<<en<<")
:"<<l<<" "<<r<<endl;
root->data = 0;
root->lazzy=0;
//return root->data;
}
void
updateParent(Node* root){
if(root==nullptr){
return;
}
int l=0,r=0;
if(root->left!=nullptr){
l=root->left->data;
}
if(root->right!=nullptr){
r=root->right->data;
}
root->data=l+r;
updateParent(root->parent);
}
void
pushLazzy(Node* root,int lazzy){
if(root->left!=nullptr){
if(root->left->lazzy>0){
pushLazzy(root->left,root->left->lazzy);
}
int
l=root->left->leftLimit,r=root->left->rightLimit;
int sm=(r*(r+1)/2)-(l*(l-1)/2);
root->left->data+=(lazzy*sm);
root->left->lazzy=lazzy;
}
if(root->right!=nullptr){
if(root->right->lazzy>0){
pushLazzy(root->right,root->right->lazzy);
}
int
l=root->right->leftLimit,r=root->right->rightLimit;
int sm=(r*(r+1)/2)-(l*(l-1)/2);
root->right->data+=(lazzy*sm);
root->right->lazzy=lazzy;
}
root->lazzy=0;
}
void update(Node*
root,int l,int r){
if(l>r){
return;
}
if(root->leftLimit==l&&root->rightLimit==r){
cout<<"LImit matched :
("<<l<<",
"<<r<<")"<<endl;
int sm=(r*(r+1)/2)-(l*(l-1)/2);
root->data+=sm;
root->lazzy++;
updateParent(root->parent);
return;
}
if(root->lazzy>0){
cout<<"There lazzy :
"<<root->lazzy<<endl;
pushLazzy(root,root->lazzy);
}cout<<"("<<root->leftLimit<<",
"<<root->rightLimit<<") ";
if(root->left!=nullptr&&l<=root->left->rightLimit){
cout<<"calling limit :
"<<"("<<l<<",
"<<min(root->left->rightLimit,r)<<")"<<endl;
update(root->left,l,min(root->left->rightLimit,r));
}if(root->right!=nullptr&&r>=root->right->leftLimit){
cout<<"calling limit :
"<<"("<<max(root->right->leftLimit,l)<<",
"<<r<<")"<<endl;
update(root->right,max(root->right->leftLimit,l),r);
}
}
void print(Node*
root){
if(root==nullptr){
return;
}
print(root->left);
cout<<root->data<<'
'<<root->lazzy<<"
("<<root->leftLimit<<",
"<<root->rightLimit<<")"<<endl;
print(root->right);
}
int main(){
Node* root=new Node;
root->parent=nullptr;
root->left=nullptr;
root->right=nullptr;
buildSeg(root,1,15);
print(root);
int l,r;
do{
cin>>l>>r;
update(root,l,r);
print(root);
}while(l!=-1);
}
মন্তব্যসমূহ
একটি মন্তব্য পোস্ট করুন