线段树的简单实现

《线段树的简单实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线段树的简单实现：＃include＃include#defineMaxSize1000typedefcharElemType;typedefstructnode{inti,j;intcover;structnode*lchild,*rchild;}ITree;//建立线段树ITree*CreateTree(inta,intb){ITree*r;if(bi=a;r->j=b;r->cove

2、r=0;if(b-a>1){r->lchild=CreateTree(a,(a+b)/2);r->rchild=CreateTree((a+b)/2,b);}elser->lchild=r->rchild=NULL;returnr;}//线段树的插入voidInsTree(ITree*r,inta,intb){intmid;if(a<=r->i&&r->j<=b)r->cover++;else{mid=(r->i+r->j)/2;if(b<=mid)InsTree(r->lchild,a,b);elseif(mid<=

3、a)InsTree(r->rchild,a,b);else{InsTree(r->lchild,a,mid);InsTree(r->rchild,mid,b);}}}//线段树的删除voidDelTree(ITree*r,inta,intb){intmid;if(a<=r->i&&r->j<=b)r->cover--;else{mid=(r->i+r->j)/2;if(b<=mid)DelTree(r->lchild,a,b);elseif(mid<=a)DelTree(r->rchild,a,b);else{DelT

4、ree(r->lchild,a,mid);DelTree(r->rchild,mid,b);}}}//计算线段树的测度intCount(ITree*r){if(r->cover>0)returnr->j-r->i;elseif(r->j-r->i==1)return0;elsereturnCount(r->lchild)+Count(r->rchild);}//主函数intmain(){ITree*r;inta,b,a1,b1,a2,b2,a3,b3,n,i;printf("请输入线段树的区间端点：");while(s

5、canf("%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条线段后线段树的测度为%d",Count(r));printf("请输入删除2条线段的区间端点：");scanf("%d%d%d%d",&a1,&b1,&a2,&b2

6、);DelTree(r,a1,b1);DelTree(r,a2,b2);printf("删除2条线段后线段树的测度为%d",Count(r));printf("请输入线段树的区间端点：");}return0;}pku2528(离散化+线段树)2010-03-1616:42#include#includeusingnamespacestd;structnode{intleft,right;intcount;}tree[160020];intposter[10003][2]

7、;intflag[20003];inthash[10000003];//hash函数。intsum;intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}voidBuild(intk,inti,intj)//利用完全二叉树建树。{tree[k].left=i;tree[k].right=j;tree[k].count=0;if(i!=j){intmid=(i+j)/2;Build(2*k,i,mid);Build(2*k+1,mid+1,j);}return;

8、}voidInsert(inti,intcolor,intfrom,intto){if(tree[i].left==from&&tree[i].right==to){tree[i].count=color;return;}if(tree[i].count==color)return;if(tree[i].count!=-1&&tr