線段樹的簡單實現

《線段樹的簡單實現》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

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("請輸入線段樹的區(qū)間端點：");while(s

5、canf("%d%d",&a,&b)!=EOF){r=CreateTree(a,b);printf("請輸入插入3條線段的區(qū)間端點：");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條線段的區(qū)間端點：");scanf("%d%d%d%d",&a1,&b1,&a2,&b2

6、);DelTree(r,a1,b1);DelTree(r,a2,b2);printf("刪除2條線段后線段樹的測度為%d",Count(r));printf("請輸入線段樹的區(qū)間端點：");}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