HDU-1698(線段樹入門)

請您先别看着個代碼,這個代碼是我自己在通過自己對線段樹的了解,自己寫的...

那不是一般的爛...是經過我無數的改正才改過來的 希望大家不要借鑒哦,,一會等我看看,别人的代碼,然後再整理整理,出個漂亮的代碼.嘿嘿

這個是逾時的....

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int N;
struct Node{
	int left;
	int right;
	int val;
}tnode[1000005];

void Buildtree(int l,int r,int n,int t)
{
	int mid=(r+l)/2;
	if(l!=0&&r!=0)
	{
		if(l!=r)
		{
			tnode[n].left=l;
			tnode[n].right=r;
			tnode[n].val=t;
			Buildtree(l,mid,2*n,mid-l+1);
			Buildtree(mid+1,r,2*n+1,r-mid);
		}
		else
		{
			tnode[n].left=l;
			tnode[n].right=r;
			tnode[n].val=1;
		}
	}
}

void update(int n)
{
	if(n==0)
		return;
	if(n%2==0)
	{
		tnode[n/2].val=tnode[n].val+tnode[n+1].val;
		update(n/2);
	//	printf("update(l=%d___r=%d)==%d\n",tnode[n/2].left,tnode[n/2].right,tnode[n/2].val);
		
	}
	else
	{
		tnode[(n-1)/2].val=tnode[n].val+tnode[n-1].val;
		update((n-1)/2);
	}

}

int getsum()
{
	return tnode[1].val;
}

void motify(int l,int r,int val,int n)
{
	int mid=(tnode[n].left+tnode[n].right)/2;
	if(tnode[n].left==l&&tnode[n].right==r&&l==r)
	{
		tnode[n].val=val;
		update(n);
	}
	else
	{

		if(r<=mid)
		{
			motify(l,r,val,2*n);
		}	
		else if(l>=mid+1)	
		{
			motify(l,r,val,2*n+1);
		}
		else if(l<=mid&&r>=mid+1)
		{
			motify(l,mid,val,2*n);
			motify(mid+1,r,val,2*n+1);
		}
	}
}


int main()
{
	int T;
	int M;
	while(scanf("%d",&T)!=EOF)
	{
		for(int k=1;k<=T;k++)
		{
			scanf("%d",&N);
			Buildtree(1,N,1,10);
		//	for(int i=1;i<=30;i++)
		//	{
		//		printf("i=%d__l=%d____r=%d____val=%d__\n",i,tnode[i].left,tnode[i].right,tnode[i].val);
		//	}
		//	printf("\n");
		//	system("pause");
			scanf("%d",&M);
			int a,b,val;
			for(int i=1;i<=M;i++)
			{
				scanf("%d%d%d",&a,&b,&val);
				motify(a,b,val,1);
		//		for(int i=1;i<=30;i++)
		//		{
		//			printf("i=%d__l=%d____r=%d____val=%d__\n",i,tnode[i].left,tnode[i].right,tnode[i].val);
		//		}
		//		printf("\n");
			}
			printf("Case %d: The total value of the hook is ",k);
			int ans=getsum();
			printf("%d.\n",ans);
		}
	}
	return 0;
}


           

下面不上比較好看的代碼..嘿嘿,,

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>


int N;
struct Node{
	int left;
	int right;
	int val;
}tree[300005];

int Buildtree(int i,int a,int b)
{
	tree[i].left=a;
	tree[i].right=b;
	if(a==b)
	{
		return tree[i].val=1;
	}
	int mid=(a+b)/2;
	return tree[i].val=Buildtree(2*i,a,mid)+Buildtree(2*i+1,mid+1,b);
}

int update(int i,int a,int b,int val)
{
	if(tree[i].left==tree[i].right)
	{
		return tree[i].val=val;
	}
	int mid=(tree[i].left+tree[i].right)/2;
	if(a>mid)
	{
		return tree[i].val=update(2*i+1,a,b,val)+tree[2*i].val;
	}
	else if(b<=mid)
	{
		return tree[i].val=update(2*i,a,b,val)+tree[2*i+1].val;
	}
	else
	{
		return tree[i].val=update(2*i,a,mid,val)+update(2*i+1,mid+1,b,val);
	}
}


int main()
{
	int T;
	int M;
	scanf("%d",&T);
	for(int k=1;k<=T;k++)
	{
		scanf("%d",&N);
		Buildtree(1,1,N);
	//	printf("%d____\n",tree[1].val);
		scanf("%d",&M);
		for(int i=1;i<=M;i++)
		{
			int a,b,val;
			scanf("%d%d%d",&a,&b,&val);
			update(1,a,b,val);
			//printf("%d******\n",tree[1].val);
		}
		printf("Case %d: The total value of the hook is %d.\n",k,tree[1].val);
	}
	return 0;
}