数据结构之——线段树(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));elseupdate(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));elsereturn 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));elseupdate(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));elsereturn 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));elsereturn query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));}

?

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