线段树.cc

线段树的基本实现～动态实现。功能并不强大

#include<stdio.h>
struct ss
{
 __int64 sum;
 int x,y,cover;
 struct ss *l,*r;
};
ss *tree;
__int64 n,q;
char c;
    
    void make(ss *p,int x,int y)
 {   
  ss *pp;
  p->x=x;p->y=y;
  if (y-x>1)
  {  
   pp=new ss;
   pp->l=0;pp->r=0;pp->sum=0;pp->cover=0;
   p->l=pp;
   make(pp,x,(x+y)/2);
   pp=new ss;
   pp->l=0;pp->r=0;pp->sum=0;pp->cover=0;
   p->r=pp;
   make(pp,(x+y)/2,y);
   p->sum=p->l->sum+p->r->sum;
  }
  else scanf("%I64d",&p->sum);
 }
 void insert(ss *p,int x,int y,int z)
 {
  __int64 temp;
  int m=(p->y+p->x)/2;
  if (p->x==x&&p->y==y)
  {
   p->sum+=(y-x)*z;
   p->cover=1;return ;
  }

  if (p->cover==1&&p->r!=0)
  {
   p->cover=0;
   temp=(p->sum - p->l->sum - p->r->sum)/(p->y - p->x);
   p->r->sum+=temp*(p->r->y - p->r->x);p->r->cover=1;
   p->l->sum+=temp*(p->l->y - p->l->x);p->l->cover=1;
  }
     
  if (y<=m) insert(p->l,x,y,z);
  if (x>=m) insert(p->r,x,y,z);
  if (x<m&&y>m) 
  {
   insert(p->l,x,m,z);
   insert(p->r,m,y,z);
  }
  p->sum=p->l->sum+p->r->sum;
 }
 __int64 output(ss *p,int x ,int y)
 {
     int m=(p->x+p->y)/2;
	 __int64 temp;
	 if (p->x==x&&p->y==y) return (p->sum);
	 if (p->cover==1&&p->r!=0)
	 {
		    p->cover=0;
            temp=(p->sum - p->l->sum - p->r->sum)/(p->y - p->x);
            p->r->sum+=temp*(p->r->y - p->r->x);p->r->cover=1;
            p->l->sum+=temp*(p->l->y - p->l->x);p->l->cover=1;
	 }
	 if (y<=m) return (output(p->l,x,y));
	 if (x>=m) return (output(p->r,x,y));
	 if (x<m&&y>m) return (output(p->l,x,m)+output(p->r,m,y));
 }
int main()
{   
 int i,x,y,z;
 scanf("%I64d%I64d ",&n,&q);
 tree=new ss;
 tree->l=0;tree->r=0;tree->sum=0;tree->cover=0;
 make(tree,1,n+1);
 scanf("%c",&c);
 for (i=1;i<=q;i++)
 {
  scanf("%c",&c);
  if (c=='Q')
  {
   scanf("%d%d",&x,&y);
   printf("%I64d\n",output(tree,x,y+1));
  }
  if (c=='C')
  {
   scanf("%d%d%d",&x,&y,&z);
   insert(tree,x,y+1,z);
  }
  scanf("%c",&c);
 }
 return 0;
}