线段树实现源代码.txt

此代码是线段树的实现源代码

#include<stdio.h>
#include<stdlib.h>
int M[6];
typedef struct node{
	int l,r;
	int data[6];
	struct node *Ln,*Rn;
}*Linklist,Lnode;
void creat(Linklist list)
{
	Linklist p,q;
	int h=(list->l+list->r)/2;
	if(list->r-list->l==0)
	{	list->Ln=NULL;list->Rn =NULL;return;  }
	p=(Linklist)malloc(sizeof(Lnode));
	p->l=list->l ; p->r =h;	list->Ln =p;  creat(list->Ln );
	q=(Linklist)malloc(sizeof(Lnode));
	q->l=h+1; q->r=list->r;	list->Rn =q;  creat(list->Rn );
}

void insert(int rand ,int message[6],Linklist list)
{
	int i;
	if(list->l==rand&&list->r==rand)
       for(i=0;i<6;i++)list->data[i]=message[i];
	else if(rand<=(list->l+list->r)/2)	insert(rand,message,list->Ln );
	else	                        	insert(rand,message,list->Rn );
}

int*tongji(Linklist list){
	int i,p[6],q[6],*t;
	if(list->r==list->l) return list->data ;
	t=tongji(list->Ln );	for(i=0;i<6;i++)p[i]=t[i];
	t=tongji(list->Rn );	for(i=0;i<6;i++)q[i]=t[i];
	if(p[2]==q[0])	q[3]+=p[5];                            //整理信息并存储 
	for(i=3;i<6;i++) if(q[i]>p[4]){p[4]=q[i];p[1]=q[i-3];}
	if(p[0]==p[1])   p[3]=p[4];
	p[2]=q[2];p[5]=q[5];
	if(p[2]==p[1])   p[5]=p[4];
	for(i=0;i<6;i++)  list->data[i]=p[i];
	return list->data ;
}
int* check(int a,int b,Linklist list){                     //查找a b段信息 
	int h=(list->l +list->r)/2 ,p[6],q[6],*t,i;
	if(list->l==a&&list->r ==b){for(i=0;i<6;i++)M[i]=list->data[i];return M;}
	if(b<=h&&a>=list->l ) check(a , b, list->Ln );
	else if(a>h&&b<=list->r ) check(a,b,list->Rn );
	else if(a>=list->l&&a<=h&&b<=list->r&&b>h){
		t=check(a,h,list->Ln);	for(i=0;i<6;i++)p[i]=t[i];
		t=check(h+1,b,list->Rn); for(i=0;i<6;i++)q[i]=t[i];
	    if(p[2]==q[0])	q[3]+=p[5];                       //整理信息并存储 
		for(i=3;i<6;i++) if(q[i]>p[4]){p[4]=q[i];p[1]=q[i-3];}
		if(p[0]==p[1])   p[3]=p[4];
		p[2]=q[2];p[5]=q[5];
		if(p[2]==p[1])   p[5]=p[4];		
		for(i=0;i<6;i++)  M[i]=p[i];
		return M ;
	}
	return M ;
}
main()
{
	int i,j,*q,message[6],x=1,n,m,y;
	Linklist head;
	head=(Linklist)malloc(sizeof(Lnode));
	head->l=1;
	while(scanf("%d",&n)&&n!=0)
	{	
		head->r=n;
		creat(head);
		scanf("%d",&m);	
    	for(i=0;i<n;i++)
		{
    		scanf("%d",&x);
    		for(j=0;j<3;j++)	message[j]=x;
	    	for(j=3;j<6;j++)    message[j]=1;
    		insert(i+1,message,head);
		}
		q=tongji(head);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
		q=check(x,y,head);
		printf("%d\n",q[4]);
		}
	}	
	return 0;
}