什么是线段树?

线段树是一种二叉树,用于区间搜索等.

常用来处理这样一类问题:在某区间中插入一些线,删除一些线,最后问某点被覆盖多少次. 因此,线段树一般需要支持以下操作: 给某区间增加一个delta值,查询某点的覆盖次数,查询某区间被覆盖次数之和....等

线段树的构建?

线段树是一种二叉搜索树,它的每个结点表示一个区间,根结点表示最大的区间,左儿子表示根节点表示区间的左半区间,右儿子表示右半区间.

所以线段树的结点常常包括:两个值left right,分别记录区间左右边界; sum记录区间覆盖次数之和....根据不一样的题目,可能有不一样的改动. 一般的结点就像这样:

class node{    int left, right;    int sum;};

线段树,需要被构建.当left == right,区间表示一个点,sum就是点的值.否则,sum为左儿子与右儿子sum的和.

void build(int l, int r, node &father){    father.left = l;    father.right = r;    if(l == r)    {        father.sum = n[r];        return;    }    int mid = (l + r) >> 1;    build(l, mid, node leftson);    build(mid + 1, r, node rightson);    father.sum = leftson.sum + rightson.sum;    return;}

线段树的一般实现:

需要支持ask(l, r, i)操作, 询问结点区间i在区间[l,r]中的部分的Sum. 如果区间i与该区间没重叠部分,Sum就是0; 如果区间i被完全覆盖,Sum就是i的sum; 否则区间i与该区间相交,则sum为i左右儿子在区间[l, r]的Sum之和,需要递归的进行计算.

int ans;void ask(int l, int r, node father){    if father not in [l, r]        then return    if father in [l, r]        then ans <- ans + father.sum             return    ask(l, r, leftson)    ask(l, r, rightson)    father.sum <- leftson.sum + rightson.sum    return}

还需要支持update(l, r, i, delta),区间i在区间[l, r]中的部分的每个点覆盖次数加delta.这里与上面ask类似.

线段树的延迟标记

我们不需要每次进行update就对所有的结点进行处理,而是可以将delta保存起来,这样多个delta可以一起计算.

可以想象一下update(l,r,i,1),update(l,r,i,2),update(l,r,i,4);我们不需要每次都计算所有结点,将delta的总和1+2+4记录在结点i中,并更新[l,r]的sum并不更新子节点的sum,需要时(*)计算一次update(l,r,i,7)即可. 需要在node中增加一个toadd来记录node所表示的区间没有增加的delta的总和. *什么是"需要时"? 如果对区间[l,r]进行ask,显然没有问题,因为我们每次都更新了[l,r]sum值.但是如果ask[l,r]区间的一部分,则有问题,因为还没有加上toadd,此时需要将[l,r]区间进行加toadd的操作,同样这里只需要做到需要查询的区间已经更新就够了!

例题: