数据结构之——线段树(1)

    线段树是ACM中比较常见的数据结构，它的每一点都代表了一条线段[a,b]，长度为1的为元线段，所有叶子结点的长度均为1。长度范围为[1,L]的一颗线段树的深度为log(L-1)+1。

    线段树基本的应用时查询某段的和，最大最小值，成段更新，保证每次操作的复杂度为log(n)。

    关于线段树的文章有很多，大家可以参考http://www.notonlysuccess.com/?p=59。

    在这里，我用hdu和poj上面的一些关于线段树的简单应用做为例题讲解。

hdu1166（单点更新，区间求和）：

    敌军海岸线上排列有n个营地，每个营地有若干个士兵，每个营地的士兵都是在随时变动（增加或减少），要随时求出任意两个营地之间的士兵人数之和。

    首先构造线段树的结构：

struct Seg_Tree
{
	int left;//左孩子
	int right;//右孩子
	int value; //该段士兵的总人数
	int calmid()
	{
		return (left+right)>>1;
	}
}tt[MAX*4];//MAX是营地个数，一般线段树的结点为它的4倍

     然后就是创建线段树：

int build(int left,int right,int idx)//idx从1开始
{
	tt[idx].left = left;
	tt[idx].right = right;
	if(left == right)
		return tt[idx].value = num[left];
	int mid = (left + right)>>1;
	return tt[idx].value = build(left,mid,LL(idx)) + build(mid+1,right,RR(idx));
}

     对于某个营地增加或减少士兵，有更新操作：

void update(int id,int x,int idx)
{
	tt[idx].value += x;
	if(tt[idx].left == tt[idx].right)
		return;
	int mid = tt[idx].calmid();
	if(id <= mid)
		update(id,x,LL(idx));
	else
		update(id,x,RR(idx));
}

    查询某段营地士兵数量总和：

int query(int left,int right,int idx)
{
	if(left == tt[idx].left && right == tt[idx].right)
		return tt[idx].value;
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(mid < left)
		return query(left,right,RR(idx));
	else
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
}

  

hdu1754（单点更新，区间最值）：

    老师喜欢问学生a到学生b中最好的成绩是多少，其间，还会更改某些学生的成绩。

    创建线段树：

int bulid(int left, int right, int idx)
{
	tt[idx].left = left;
	tt[idx].right = right;
	if(left == right)
		return tt[idx].value = num[left];
	int mid = tt[idx].calmid();
	return tt[idx].value = max(bulid(left,mid,LL(idx)), bulid(mid+1,right,RR(idx)));
}

     对于某个学生成绩的更改，有更新操作： 

void update(int id, int value, int idx)		//更新点，同时更新区间最值:先更新左右子树的最值，然后更新父节点
{
	if(tt[idx].left == tt[idx].right)
	{
		tt[idx].value = value;
		return;
	}
	int mid = tt[idx].calmid();
	if(id <= mid)
		update(id,value,LL(idx));
	else
		update(id,value,RR(idx));
	tt[idx].value = max(tt[LL(idx)].value, tt[RR(idx)].value);
}

    查询某段学生成绩中的最大值：

int query(int left, int right, int idx)
{
	if(left == tt[idx].left && right == tt[idx].right)
		return tt[idx].value;
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(left > mid)
		return query(left,right,RR(idx));
	else
		return max(query(left,mid,LL(idx)), query(mid+1,right,RR(idx)));
}

 以上两道例题是对于单点更新，对于成段更新，有hdu1698：

    dota里面有一种钩子，它由n段组成，刚开始全部是铜的，每段重量为1。现在要把其中a-b这段换成金的或者银的(重量分别为3,2)，查询这个钩子的总重量。

    创建线段树：

void build(int left, int right, int idx)
{
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].value = 1;//初始每段重量为1,-1表示这段钩子中是混合的（金银铜的混合）
	if(left == right)
		return;
	int mid = (left + right)>>1;
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}

    更新a-b段的钩子：

void update(int left, int right, int value, int idx)		//更新区间
{
	if(left <= tt[idx].left && right >= tt[idx].right)
	{
		tt[idx].value = value;
		return;
	}
	if(tt[idx].value != -1)
	{
		tt[LL(idx)].value = tt[RR(idx)].value = tt[idx].value;
		tt[idx].value = -1;			//表示这个点代表的线段是混合的
	}
	int mid = tt[idx].calmid();
	if(left <= mid)
		update(left,right,value,LL(idx));
	if(mid < right)
		update(left,right,value,RR(idx));
}

    查询某段钩子的重量：

int query(int left, int right, int idx)
{
	if(left == tt[idx].left && right == tt[idx].right)
	{
		if(tt[idx].value != -1)
			return (right-left+1)*tt[idx].value;
		else
		{
			int mid = tt[idx].calmid();
			return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
		}
	}
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(left > mid)
		return query(left,right,RR(idx));
	else
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
}

 

学习线段树，要熟悉线段树的构造，查找，更新操作。