lineartree.cpp

一个效率可以的线段树代码 可以直接用来求解矩形面积并 另外可以修改实现更多功能.

class node
{
	public:
		long long st,ed;
		long long v,sum;
		node *left,*right;
		node(){left=right=NULL;v=sum=0;}
		~node(){if(left!=NULL)delete left;if(right!=NULL)delete right;}
};
class lineartree
{
	private:
		node *root;
		void update(node *r)
		{
			if(r->v>0)
			{
				r->sum=r->ed-r->st;
				return;
			}
			long long vl=(r->left==NULL)?0:r->left->sum;
			long long vr=(r->right==NULL)?0:r->right->sum;
			r->sum=vl+vr;
		}
		void ins(node *r,long long st,long long ed,long long value)
		{
			long long mid=(r->st+r->ed)/2;
			if(r==NULL)return;
			if(st==r->st&&ed==r->ed)
			{
				r->v+=value;
				if(r->v<0)
				{
					if(r->left==NULL)
					{
						r->left=new node;
						r->left->st=r->st;
						r->left->ed=mid;
					}
					if(r->right==NULL)
					{
						r->right=new node;
						r->right->st=mid;
						r->right->ed=r->ed;
					}
					ins(r->left,r->st,mid,r->v);
					ins(r->right,mid,r->ed,r->v);
					r->v=0;
				}
				update(r);
				return;
			}
			if(r->v!=0)
			{
				if(r->left==NULL)
				{
					r->left=new node;
					r->left->st=r->st;
					r->left->ed=mid;
				}
				if(r->right==NULL)
				{
					r->right=new node;
					r->right->st=mid;
					r->right->ed=r->ed;
				}
				ins(r->left,r->st,mid,r->v);
				ins(r->right,mid,r->ed,r->v);
				r->v=0;
				update(r);
			}
			if(ed<=mid)
			{
				if(r->left==NULL)
				{
					r->left=new node;
					r->left->st=r->st;
					r->left->ed=mid;
				}
				ins(r->left,st,ed,value);
				update(r);
				return;
			}
			if(st>=mid)
			{
				if(r->right==NULL)
				{
					r->right=new node;
					r->right->st=mid;
					r->right->ed=r->ed;
				}
				ins(r->right,st,ed,value);
				update(r);
				return;
			}
			if(r->left==NULL)
			{
				r->left=new node;
				r->left->st=r->st;
				r->left->ed=mid;
			}
			if(r->right==NULL)
			{
				r->right=new node;
				r->right->st=mid;
				r->right->ed=r->ed;
			}
			ins(r->left,st,mid,value);
			ins(r->right,mid,ed,value);
			update(r);
		}
		long long findsum(node *r,long long st,long long ed)
		{
			if(r==NULL)return 0;
			if(r->st==st&&r->ed==ed)return r->sum;
			long long mid=(r->st+r->ed)/2;
			if(r->v!=0)
			{
				if(r->left==NULL)
				{
					r->left=new node;
					r->left->st=r->st;
					r->left->ed=mid;
				}
				if(r->right==NULL)
				{
					r->right=new node;
					r->right->st=mid;
					r->right->ed=r->ed;
				}
				ins(r->left,r->st,mid,r->v);
				ins(r->right,mid,r->ed,r->v);
				r->v=0;
				update(r);
			}
			if(ed<=mid)return findsum(r->left,st,ed);
			if(st>=mid)return findsum(r->right,st,ed);
			return findsum(r->left,st,mid)+findsum(r->right,mid,ed);
		}
	public:
		lineartree(long long st=-100000000000ll,long long ed=100000000000ll){root=new node;root->st=st;root->ed=ed;}
		void ins(long long st,long long ed,long long value){ins(root,st,ed,value);}
		long long findsum(long long st,long long ed){return findsum(root,st,ed);}
		~lineartree(){delete root;}
};