线段树模板

//logn时间查找任意一段数的新信息

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int l,r;
int good;
struct node *Ln,*Rn;
}*Linklist,Lnode;
int nice;
int max(int a,int b){ if(a>b)return a; else return b;}
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,Linklist list)
{
if(list->l==rand&&list->r==rand)
    {list->good=message; return;}
else if(rand<=(list->l+list->r)/2) insert(rand,message,list->Ln );
else                         insert(rand,message,list->Rn );
}
int tongji(Linklist list)
{
if(list->l==list->r )return list->good ;
else list->good =max(tongji(list->Ln),tongji(list->Rn));
return list->good ;
}
int find(int a,int b,Linklist list)
{
int h=(list->l +list->r)/2;
if(list->l==a&&list->r ==b) {nice=list->good;return list->good;}
if(b<=h&&a>=list->l ) find(a , b, list->Ln );
else if(a>h&&b<=list->r ) find(a,b,list->Rn );
else if(a>=list->l&&a<=h&&b<=list->r&&b>h)
     return nice=max(find(a,h,list->Ln ),find(h+1,b,list->Rn ));
return nice;
}
main()
{
int i,a,n,x,y;
Linklist head;
head=(Linklist)malloc(sizeof(node));
head->l=1;
scanf("%d",&n);
head->r=n; creat(head);

for(i=0;i<n;i++)
{
   scanf("%d",&a);
   insert(i+1,a,head);
}
tongji(head);
while(scanf("%d%d",&x,&y))
{
   a=find(x,y,head);
   printf("%d\n",a);
}
return 0;
}

本文转自博客园知识天地的博客，原文链接：线段树模板，如需转载请自行联系原博主。