线段树的简单实现.doc

线段树的简单实现：i nclude i nclude #define MaxSize 1000typedef char ElemType; typedef struct node int i,j; int cover; struct node *lchild,*rchild; ITree;/建立线段树 ITree *CreateTree(int a,int b) ITree *r; if(bi=a;r-j=b;r-cover=0; if(b-a1) r-lchild=CreateTree(a,(a+b)/2); r-rchild=CreateTree(a+b)/2,b); else r-lchild=r-rchild=NULL; return r;/线段树的插入 void InsTree(ITree *r,int a,int b) int mid; if(ai&r-jcover+; else mid=(r-i+r-j)/2; if(blchild,a,b); else if(midrchild,a,b); else InsTree(r-lchild,a,mid); InsTree(r-rchild,mid,b); /线段树的删除void DelTree(ITree *r,int a,int b) int mid; if(ai&r-jcover-; else mid=(r-i+r-j)/2; if(blchild,a,b); else if(midrchild,a,b); else DelTree(r-lchild,a,mid); DelTree(r-rchild,mid,b); /计算线段树的测度int Count(ITree *r) if(r-cover0) return r-j-r-i; else if(r-j-r-i=1) return 0; else return Count(r-lchild)+Count(r-rchild); /主函数int main() ITree *r; int a,b,a1,b1,a2,b2,a3,b3,n,i; printf(请输入线段树的区间端点：); while(scanf(%d%d,&a,&b)!=EOF) r=CreateTree(a,b); printf(请输入插入3条线段的区间端点：); scanf(%d%d%d%d%d%d,&a1,&b1,&a2,&b2,&a3,&b3); InsTree(r,a1,b1);InsTree(r,a2,b2);InsTree(r,a3,b3); printf(插入3条线段后线段树的测度为%dn,Count(r); printf(请输入删除2条线段的区间端点：); scanf(%d%d%d%d,&a1,&b1,&a2,&b2); DelTree(r,a1,b1);DelTree(r,a2,b2); printf(删除2条线段后线段树的测度为%dn,Count(r); printf(n请输入线段树的区间端点：); return 0; pku 2528(离散化+线段树)2010-03-16 16:42#include#includeusing namespace std;struct nodeint left,right;int count;tree160020;int poster100032;int flag20003;int hash10000003;/hash函数。int sum;int cmp(const void *a,const void *b) return *(int *)a-*(int *)b;void Build(int k,int i,int j)/利用完全二叉树建树。 treek.left=i;treek.right=j;treek.count=0;if(i!=j) int mid=(i+j)/2; Build(2*k,i,mid); Build(2*k+1,mid+1,j);return ;void Insert(int i,int color,int from,int to)if(treei.left=from&treei.right=to) treei.count=color; return ;if(treei.count=color)return ;if(treei.count!=-1&treei.count!=color)/这个if语句很重要，就是他，搞了很长时间。 tree2*i.count=treei.count; tree2*i+1.count=treei.count; treei.count=-1;int mid=(treei.left+treei.right)1;if(tomid) Insert(1+2*i,color,from,to);else Insert(i*2,color,from,mid); Insert(i*2+1,color,mid+1,to);return ;void query(int i)if(treei.count=0) if(flagtreei.count=0)sum+; flagtreei.count+; return ; query(i*2);query(i*2+1);return ; int main()int i,j,k;int t,n;scanf(%d,&t);while(t-) memset(flag,0,sizeof(flag); scanf(%d,&n); j=0;k=1; for(i=1;i=n;i+) scanf(%d%d,&posteri0,&posteri1); flagj+=posteri0; flagj+=posteri1; qsort(flag,j,sizeof(flag0),cmp);/离散化处理。 hashflag0=1; for(i=1;ij;i+) if(flagi!=flagi-1)k+; hashflagi=k; Build(1,1,k);/建立空的线段树 memset(flag,0,sizeof(flag); for(i=1;i=n;i+) Insert(1,i,hashposteri0,hashposteri1);/插入 sum=0; query(1);/计算可以看到总的海报数量 printf(%dn,sum);return 0; pku 2777(线段树)2010-03-16 18:49#includeusing namespace std;const int hmax=100005;int flag100;int sum=0;struct nodeint left,right;int color;board4*hmax;void Build(int k,int from,int to) boardk.left=from;boardk.right=to;boardk.color=1;if(from!=to) int mid=(from+to)1; Build(2*k,from,mid); Build(2*k+1,mid+1,to);return ;void update(int i,int from,int to,int color)if(boardi.left=from&boardi.right=to) boardi.color=color; return ;if(boardi.color=color)return ;if(boardi.color!=color&boardi.color) board2*i.color=boardi.color; board2*i+1.color=boardi.color; boardi.color=0;int mid=(boardi.left+boardi.right)1;if(tomid) update(i*2+1,from,to,color);else update(i*2,from,mid,color); update(i*2+1,mid+1,to,color);return ;void query(int i,int from,int to)if(boardi.color) if(!flagboardi.color)sum+; flagboardi.color+; return ; int mid=(boardi.left+boardi.right)1;if(tomid) query(i*2+1,from,to);else query(i*2,from,mid); query(i*2+1,mid+1,to);return ;int main() int i,a,b,c,k;int L,T,O;char s13;while(scanf(%d%d%d,&L,&T,&O)!=EOF) Build(1,1,L); for(i=0;ib)k=a;a=b;b=k; update(1,a,b,c); else scanf(%d%d,&a,&b); if(ab)k=a;a=b;b=k; sum=0; memset(flag,0,sizeof(flag); query(1,a,b); printf(%dn,sum); return 0; pku 2777(线段树)2010-03-16 18:49#includeusing namespace std;const int hmax=100005;int flag100;int sum=0;struct nodeint left,right;int color;board4*hmax;void Build(int k,int from,int to) boardk.left=from;boardk.right=to;boardk.color=1;if(from!=to) int mid=(from+to)1; Build(2*k,from,mid); Build(2*k+1,mid+1,to);return ;void update(int i,int from,int to,int color)if(boardi.left=from&boardi.right=to) boardi.color=color; return ;if(boardi.color=color)return ;if(boardi.color!=color&boardi.color) board2*i.color=boardi.color; board2*i+1.color=boardi.color; boardi.color=0;int mid=(boardi.left+boardi.right)1;if(tomid) update(i*2+1,from,to,color);else update(i*2,from,mid,color); update(i*2+1,mid+1,to,color);return ;void query(int i,int from,int to)if(boardi.color) if(!flagboardi.color)sum+; flagboardi.color+; return ; int mid=(boardi.left+boardi.right)1;if(tomid) query(i*2+1,from,to);else query(i*2,from,mid); query(i*2+1,mid+1,to);return ;int main() int i,a,b,c,k;int L,T,O;char s13;while(scanf(%d%d%d,&L,&T,&O)!=EOF) Build(1,1,L); for(i=0;ib)k=a;a=b;b=k; update(1,a,b,c); else scanf(%d%d,&a,&b); if(ab)k=a;a=b;b=k; sum=0; memset(flag,0,sizeof(flag); query(1,a,b); printf(%dn,sum); return 0; pku 1177(线段树)2010-03-30 11:48强烈推荐先看看国家集训队的论文-陈宏的论文#include#includeusing namespace std;const int hmax=40006;struct seg_tree int left,right; int count; int cl,cr; int segment; int seg;node2*hmax;struct rectint start,end;int x;int tag;linehmax;int hashhmax,lisanhmax;int Yhmax,n;int cmp(rect a,rect b) return (a.x1) int mid=(1+nodei.left+nodei.right)1; Build(2*i,from,mid); Build(2*i+1,mid,to);return;void update(int i,int from,int to)if(nodei.count0) nodei.segment=lisannodei.right-lisannodei.left; nodei.seg=1; nodei.cl=nodei.cr=1;else if(nodei.right-nodei.left1) nodei.segment=(node2*i.segment+node2*i+1.segment); nodei.cl=node2*i.cl; nodei.cr=node2*i+1.cr; nodei.seg=node2*i.seg+node2*i+1.seg; if(node2*i.cr&node2*i+1.cl)nodei.seg-;else nodei.segment=0; nodei.cl=nodei.cr=0; nodei.seg=0;void Insert(int i,int from,int to,int tag)if(from=nodei.right) nodei.count+=tag;else int mid=(1+nodei.left+nodei.right)1; if(frommid)Insert(2*i+1,from,to,tag);update(i,from,to);int main() int i,j,k;int x1,x2,y1,y2; while(EOF!=scanf(%d,&n) for(i=j=0;jn;j+) scanf(%d%d%d%d,&x1,&y1,&x2,&y2); linei.start=linei+1.start=y1; linei.end=linei+1.end=y2; linei.x=x1;linei+1.x=x2; linei.tag=1;linei+1.tag=-1; Yi=y1;Yi+1=y2; i+=2; sort(Y,Y+2*n); sort(line,line+2*n,cmp);/* for(i=0;i2*n;i+) coutYiendl; coutendl; for(i=0;i2*n;i+) coutlinei.x linei.start linei.end linei.tagendl; coutendl;*/ lisan1=Y0; hashY0+10000=1; k=1; for(i=1;i2*n;i+) if(Yi=Yi-1)continue; k+; lisank=Yi; hashYi+10000=k; Build(1,1,k); int from,to; int pre=0, len=0; int sum=0; line2*n.x=line2*n-1.x; for(i=0;i=pre) sum+=len-pre; else sum+=pre-len; pre=len; printf(%dn,sum);return 0;/*-6-400481010141516202225-15 0 10 1-5 8 25 10 -6 4 12 15 22 15 0 10 -110 15 22 -115 -4 14 116