猫史档案馆

 

 

 

线段树

 

 

线段树是一种可以快速取区间特征值（求和、求最值等）、快速修改单个数 据或区间数据的数据结构。

线段树和树状数组虽然都能实现区间求和，但存储本质不一样，实现的途径

也不一样（线段树是对L到R求和，树状数组是对R和L-1求前缀和后处理得）。

线段树不但能提供区间和的查询，还能提供最值等特征值的查询。线段树不但能修改单点数据，还能整个区间批量修改数据。

线段树比树状数组功能强大很多，但消耗更多的空间（2倍）和时间复杂度常数，代码量也更大。

 

 

 

何时使用

 

和树状数组类似，出现对数列进行区间操作（求和、求最值等特征值，修改 数据）时可以考虑线段树。具体来说：

树状数组不够用的时候：求最值等非区间和特征值、批量区间修改 等操作；

非常熟悉线段树的代码。

但时间和空间复杂度要足够的情况下。

 

 

 

OI中的线段树

 

 

OI中的线段树具有以下特点：

 

­1. 线段树是一个树形结构，每个节点主要存放的是某个区间上的特征值，每个节点的左喵存 放的是左半区间的特征值，每个节点的右喵存放的是右半区间的特征值，递归向下定义。

­2. 为了方便可采用数组存储，即t[i]节点的左右喵分别是t[i*2]、t[i*2 + 1]，i=[1…n]。因此，线段树数组需要开4倍元素个数（非满二叉树性质，用链表可以优化到只使用2倍）容量存放所有节点数据。

­3. 每个节点最少需要记录当前节点的区间范围、待求特征值两个量。建议使用struct定义类型。

­4. 所有叶子节点上理论上存放的是每个元素单个数据本身。

 

 

 

 

代码实现

 

 

根据数据建树：

 

­线段树是一个树形结构，每个节点主 要存放的是某个区间上的特征值，每 个节点的左喵存放的是左半区间的 特征值，每个节点的右喵存放的是 右半区间的特征值，递归向下定义。

­依照定义建树。

­比如，根据数组a[]中的数据建立一棵同时记录区间和和区间最大值的线段树tree：

void build(int id , int l , int r){  tree[id].left=l; tree[id].right=r;
    if(l==r){
        tree[id].sum=a[l];
        tree[id].max=a[l];
    }
    else{
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;  
        tree[id].max=max(tree[id*2].max,tree[id*2+1].max;
    }
}

 

 

 

查询区间特征值：

 

­根据查询区间逐层递归向下查找。

­如果查询区间包含了整个当前节点区间，则直接返回当前区间值。

­如果查询区间只存在当前节点的左（右）区间，则返回在对应区间的查询结果。

­如果查询区间同时存在当前节点的左右区间，则在左右区间分别询问，并将返回结果组合后返回。

int query(int id , int l , int r){
    if (tree[id].left==l&&tree[id].right==r)
        return tree[id].sum; //询问总和，可改为最值
    }
    else{
        int mid=(tree[id].left+tree[id].right)/2;
        if (r<=mid) return query(id*2,l,r);
    else
        if(l>mid)
            return query(id*2+1,l,r)
        else
            return query(id*2,l,mid)+query(id*2+1,mid+1,r);
    }
}

 

 

 

 

修改单个数据的值：

 

­类似查询操作，递归查找，直到找到修改数据下标对应的叶子节点，修改数据后返回，回溯过程中要更新值。

­如果修改数据下标等于当前节点区间，则直接修改本节点的值后返回。

­如果查询区间只存在当前节点的左（右）区间，则在对应区间的递归向下修改。要注意，在子节点修改完成后，需要更新当前节点的特征值。

void update(int id , int pos , int val){
    if (tree[id].left==tree[id].right){
        tree[id].sum=tree[id].max=val;
    }
    else{
        int mid=(tree[id].left+tree[id].right)/2;
        if(pos<=mid)
            update(id*2,pos,val);
        else
            update(id*2+1,pos,val);
        tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;  
        tree[id].max=max(tree[id*2].max,tree[id*2+1].max)
    }
}

 

 

 

 

区间修改操作

 

 

更新点

­一个点影响到的结点数？

­如何更新这些点？——递归！

­  如果像树状数组建树那样，用枚举单个修改的方法来“批量”修改数据，或者修改区间时走到 底，把涉及的叶子节点数据全部修改，时间复杂度最差为O(Q * NlogN)。

 

查询区间

­一个区间的值和哪些点有关？

­为了严格O(logN)我们需要做的？——完全包含就不往下行！

 

效仿区间查询操作，当前区间被修改区间包住，就不再往下更新。

在更新和查询区间[l,r]的时候，为了保证复杂度是严格的O(logN)必须在达到 被[l,r]覆盖的区间的结点时就立即返回。而为了保证这样做的正确性，需要在 这两个过程中做一些相关的“懒”操作，要记录孩子是否 需要被修改但是还 尚未被修改，还要在必要且不浪费时间的时候完成对孩子修改。

——适合区间，更有效的线段树写法（优化修改，调整查询）

 

如果当前节点表示的区间被修改区间包含，显然它的孩子也肯定需要被修改。 但我们只修改当前节点的数值，并记录喵需要被修改，而不递归向下修改。

为每个节点添加一个lazytag标签，记录当前区间的孩子是否需要被修改，并 记录改动值的大小，以便后续同步。

 

在什么时候同步到喵？

­“万不得已”的时候

——必须要使用到喵的时候就要同步。但此时刚好会访问喵，所以不会浪费时间。

­具体的，更新时，若当前区间不被包含在更新区间里，则要往喵区间里更新，要访问喵；  查询时，若当前区间不被包含在查询区间里，则要去喵区间里查询，要访问喵。

 

 

 

Code：

//把id节点的变动情况下传给喵 
void pushdown(int id){
    if(tree[id].tag == true){
        tree[id*2].tag = tree[id*2 + 1].tag = true; //下传标记到左右喵
        tree[id*2].delta += tree[id].delta;//下传变动记录到左喵，以便左喵继续下传
        tree[id*2].max += tree[id].delta;//更改左喵数值
        tree[id*2].sum += (tree[id*2].r – tree[id*2].l + 1) * tree[id].delta;
        tree[id*2+1].delta += tree[id].delta;//下传变动记录到右喵，以便右喵继续下传
        tree[id*2+1].max += tree[id].delta;//更改右喵数值
        tree[id*2+1].sum += (tree[id*2 + 1].r –tree[id*2 + 1].l + 1)*tree[id].delta;
        tree[id].tag = false;//喵已被修改，清空标记
        tree[id].delta = 0;
    }
}

void query(int id , int l , int r){
    if (tree[id].left==l&&tree[id].right==r)
        return tree[id].sum;
    }
    else{
        pushdown(id);	//不得不访问喵了，就要下传
        int mid=(tree[id].left+tree[id].right)/2;
        if (r<=mid)
            return query(id*2,l,r);
        else
            if (l>mid)
                return query(id*2+1,l,r)
            else
                return query(id*2,l,mid) +  query(id*2+1,mid+1,r);
    }
}

void modify(int id , int l , int r , int x){
    if (tree[id].left>=l && tree[id].right<=r)
        tree[id].max+=x;  tree[id].sum+=x*(tree[id].r-tree[id].l+1);//标记喵需要修改但尚未修改
        tree[id].tag = true; tree[id].delta = x;
    }
    else{
        pushdown(id); //不得不访问喵了，就要下传
        int mid=(tree[id].left+tree[id].right)/2;
        if (r<=mid)
            modify(id*2,l,r);
        else
            if (l>mid)
                modify(id*2+1,l,r)
            else{
                modify(id*2,l,mid);
                modify(id*2+1,mid+1,r);
            }
        tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
        tree[id].max=max(tree[id*2].max,tree[id*2+1].max);
    }
}

 

 

 

 

 

例题讲解

 

 

 

例题A BALANCED LINE UP

 

 

۞ Description：

N头牛总是按同一序列排队。有一天，主人决定让一些牛们玩 一场飞盘比赛。他准备找一群在对列中为置连续的牛来进行比赛，但为了避免 水平悬殊，牛的身高不应该相差太大。 主人准备了Q个可能的牛的选择和所有 牛的身高，请告诉他每一组里面最高和最低的牛的身高差别。

 

۞ Input：

牛数目N及N头奶牛的身高，询问数Q及询问的左右端点编号。

۞ Output：

询问区间内最高的奶牛和最矮的奶牛的身高差。

 

۞ Limitation：

N<=50 000，Q<=50 000，1<=身高<=1 000 000

 

 

۞ Solution：

­不就是询问区间特征值么？

­线段树解决。

­特征值为最大值、最小值。修改在查询、建树等过程中的特征值计算方式。

­

­* ：线段树不但能接受区间和最为特征值，还能接受最值，或者其他更为复杂的计算结果作为 特征值。并且可以同时记录多个特征值。

 

 

 

 

例题B BALLOC

 

 

۞ Description：

农场由N个畜栏组成，编号为1..N，畜栏i可以最多容纳Ci只奶 牛。奶牛i希望得到连续的一段畜栏，表示为一段区间 (Ai,Bi) 。这样的话奶牛 可以在这段牛棚里面转悠。(当然，这段畜栏必须要有足够的空间)给出M个请 求，请求出不超过畜栏承载量的情况下，最多可以满足的请求数。

 

۞ Input：

畜栏数量N，牛数目M，及这M头牛所想要的畜栏范围、Ci。

۞ Output：

能满足的最多数目。

 

۞ Limitation：

N<=100000，M<=100000， 1 <= Ci <= 100000。

 

 

۞ Solution：

 

­区间？线段树！

­等等…好像哪里不对…最大能容忍量？这要怎么用线段树…

­最大能容忍量->贪心，使用贪心策略尽量多的分配畜栏，贪心的过程当中用线段树检查是否 可以分配成功。

­分配上的贪心策略：对请求，按照r关键字递增排序，然后r相同就按照区间长度递增排序。

­总的来讲就是优先截止早的区间，相同的话就优先区间长度小的区间。

­然后一个一个请求往里塞，就是线段树操作了。能塞的塞进去，不能的就continue

­每个位置有个权值代表剩余多少个空位。对于一个区间覆盖时就看区间最小值是否大于0。

­* ：线段树虽然代码量大，但也仍有可能仅作为一个辅助工具辅助其余算法提供检验等功能。

 

 

 

 

课后练习

 

 

 

BLACK AND WHITE

 

 

۞ Description：

有n个数和m此操作，操作分两种：

1x y 表示把区间[x, y]里面的1改为0，0改为1；

2x y 表示查询区间[x, y]最多的连续的1的个数。

 

۞ Input：

数字个数n及这n个数字（0或1），操作个数m及m条操作具体信息。

۞ Output：

针对每个询问（操作1）返回询问区间里最多的连续的1的个数。

 

۞ Limitation：

n<=100 000，m<=50 000。