线段树系列之——区间更新

第三篇线段树了——重点不在于解决题目，通过题目理解线段树才是重点

前面写了一篇关于线段树的单点更新，线段树的单点更新就只要找到指定的叶节点并进行更新即可，这篇文章主要根据相关例题讲下关于线段树的区间更新

例题

题目链接

题意

N个气球排成一排，共有N条指令，每条指令表示从a-->b每个气球涂一次颜色，问所有指令执行完之后，各个气球依次被涂过多少次颜色。

导学

首先回顾一下线段树的单点更新

void add(int k,int p,int value){
   if(tree[p].left==k&&tree[p].right==k){   //如果找到了对应位置的叶子节点，就进行增加操作
       tree[p].value+=value;
       return;
   }
   int mid=(tree[p].left+tree[p].right)/2;  //从子节点中寻找
   if(k<=mid) add(k,p*2,value);
   else add(k,p*2+1,value);
   tree[p].value = tree[2*p].value+tree[2*p+1].value;  //子节点更新了，父节点也要更新
}

单点更新就相当于范围是[a,a]，然后因为必定有且仅有一个节点和这个范围相同（叶节点），所以就是不断的向左子树或者右子树中找，找到这个叶节点之后，就进行相应的修改操作。修改完成之后，需要相应修改其父节点的值

那相对应的，区间更新的更新范围是[a,b]，不管这个[a,b]是否和某一节点的范围吻合，至少一定存在这几个节点，范围相加就等于[a,b]。那是不是把这几个节点更新就好了呢？求每个气球被涂过多少次颜色又怎么实现呢？

解析

我们在实现代码之后，发现，区间更新与单点更新的代码很相似

void add(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r){
        tree[p].value++;   //在父节点上更新，子节点不做处理
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;
    if(r<=mid) add(l,r,2*p);  //向左子树更新
    else if(l>mid) add(l,r,2*p+1);  //向右子树更新
    else{  //左右子树同时更新
        add(l,mid,2*p);
        add(mid+1,r,2*p+1);
    }
}

相比较而言，单点更新是更新叶节点，然后返回时顺带更新叶节点对应的父节点。而区间更新只更新到父节点，子节点不做处理，当然如果父节点覆盖不了，就会细化到相应的子节点中。

那么查询呢？

通过上面的更新的步骤我们发现。假设整个线段树的范围是[0,10]，那么根节点的左子树的范围是[0,5]，右子树的范围是[6,10]。假设第一次更新区间是[0,5]，第二次更新的区间是[5,10]。

第一次修改，会将根节点的左子树更新次数+1，第二次修改会将叶节点[5,5]和根节点的右子树更新次数+1（因为没有[5,10]范围的节点，只有[5,5]+[6,10]）

当我们需要知道第5个气球被涂了几次的时候，我们从根节点开始找[5,5]这个叶节点，发现父节点[0,5]被涂了，我们将sum+=value（value是父节点被涂的次数，在上面的假设中，就是1），然后以此类推往下，直到到达叶节点[5,5]为止。

所以总结一下就是，更新只更新父节点（最大覆盖单位），如果父节点不够更新再依次细化。在统计每个点时，从根节点开始遍历计算，遇到父节点有更新的就相应增加（因为父节点更新了，就说明该父节点覆盖的所有子节点都需要更新），然后最后求得的就是该叶节点的总更新次数

AC代码（下面还有拓展~）

#include <iostream>
#include <stdio.h>
#define M 100005
using namespace std;
struct node{
    int left;
    int right;
    int value;
}tree[M*4];   
int sum=0;
void build_tree(int l,int r,int p){
    tree[p].left=l;
    tree[p].right=r;
    tree[p].value=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build_tree(l,mid,2*p);
    build_tree(mid+1,r,2*p+1);
}
void add(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r){
        tree[p].value++;
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;
    if(r<=mid) add(l,r,2*p);
    else if(l>mid) add(l,r,2*p+1);
    else{
        add(l,mid,2*p);
        add(mid+1,r,2*p+1);
    }
}
void search(int k,int p){
    sum+=tree[p].value;
    if(tree[p].left==k&&tree[p].right==k) return;
    int mid=(tree[p].left+tree[p].right)/2;
    if(k<=mid) search(k,2*p);
    else search(k,2*p+1);
}
int main(){
    int n,i,num1,num2;
    while(cin>>n&&n!=0){
        build_tree(1,n,1);
        for(i=0;i<n;i++){
            scanf("%d%d",&num1,&num2);
            add(num1,num2,1);
        }
        for(i=1;i<n;i++){
            sum=0;
            search(i,1);
            cout<<sum<<" ";
        }
        sum=0;
        search(n,1);
        cout<<sum<<endl;
    }
    return 0;
}

拓展

题目链接

题意

这是道英文题，简单的描述一下题意。还是拿糖果举例把，桌上有n堆糖果，初始数量每堆糖果都是1，然后会进行一些类似于X Y Z的操作，每个操作都表示把从X堆到Y堆的糖果数量都变成Z。例如1 5 3就表示把第1、2、3、4、5堆糖果的数量都变成3。最后需要求的是所有糖果堆的总数量

思路

这题与上面讲到的区间刷新不太一样。上面那题是累加，所以第一次增加某一节点后，后续修改之后，就不需要改动。

举个栗子，第一次修改[0,5]，第二次修改[5,10]。

对于上面讲到的区间刷新，第二次修改不需要去动第一次修改的内容，仅仅需要在叶节点上进行附加，附加的结果就是叶节点更新次数+父节点([0,5])更新次数

而对于这题的区间更新，比如第一次将[0-5]修改成2，第二次将[5,10]修改成3。那么第二次的修改直接导致的是第一次的修改部分无效，也就是说，第二次修改之后，[0-4]是被第一次修改的2，但是[5,5]已经是3了，那么怎么把[0-5]这个父节点的标记变成[0-4]就成了一个问题。

解析

还是就代码进行解析

struct node{
    int left,right,flag,value;  //left和right表示的是范围，value表示的是这个范围的数值
}tree[M*4];
void build_tree(int l,int r,int p){
    tree[p].left=l;
    tree[p].right=r;
    tree[p].value=0;
    tree[p].flag=0;  //懒惰标记
    if(l==r){
        tree[p].value=1;
        tree[p].flag=1; //叶节点的懒惰标记都为1
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;
    build_tree(l,mid,p*2);
    build_tree(mid+1,r,p*2+1);
}
……
cin>>n>>m;
build_tree(1,n,1);

不知道细心的你有没有发现，定义线段树的结构体中多了一个flag，被称为——懒惰标记

那这个懒惰标记是干嘛的呢？

首先我们看build_tree这个建树操作。他把所有的父节点的value和懒惰标记flag都置0，而叶节点的初始value就是题中给出的1，懒惰标记flag也是1。其余和前面的建树都一样，为什么要这么建树，懒惰标记是干嘛的呢？

懒惰标记
第一次更新了范围[0,5]为2。懒惰标记就跟程序说，[0,5]这个范围以下的所有子节点的值都是2，如果要统计总数了，到我这里就可以懒惰一下，不用往下再走了，我下面的所有数值之和就是(5-0)×2了。但是程序你只有执行到有懒惰标记的地方才能停下，没有懒惰标记的地方，即使value不为0也不能停！

是不是有点感觉到懒惰标记的用法了，如果有思路，可以先试着独立去完成下这道题~

然后看下一段代码

void update(int l,int r,int p,int value){
    if(tree[p].left==l&&tree[p].right==r){   //如果这个节点的范围等于需要更新的范围
        tree[p].value=value;  //更新值
        tree[p].flag=1;  //懒惰标记置1
        return;
    }
    //如果范围不完全匹配
    if(tree[p].flag==1){  //如果懒惰标记已经置1，就向下延伸，且当前节点懒惰标记清零
        tree[p].flag=0;
        tree[p*2].flag=1;
        tree[p*2+1].flag=1;
        tree[p*2].value=tree[p].value;
        tree[p*2+1].value=tree[p].value;
    }
    int mid=(tree[p].left+tree[p].right)/2;
    if(r<=mid) update(l,r,p*2,value);
    else if(l>mid) update(l,r,p*2+1,value);
    else{
        update(l,mid,p*2,value);
        update(mid+1,r,p*2+1,value);
    }
}

类似的，更新操作也只是多了一段if判断代码。如果范围完全匹配，那没话说，修改value，将懒惰标记flag置1。但是在没有完全匹配时，就需要进行判断了，如果当前懒惰标记为0，那相安无事~一旦发现当前这个不完全匹配的节点懒惰标记已经置1了

就像上面说的，第一次将范围[0,5]修改成2，第二次将范围[5,10]修改成3，那么在第二次修改的时候，由于最终目的地是叶节点[5,5]，所以会经过[0,5]这个已经被懒惰的节点。

每到达一个已经被懒惰的节点，且范围不匹配，那就需要把懒惰标记分给子节点，比如[0,5]的子节点是[0,2]和[3,5]，那么就把[0,5]懒惰标记清空，告诉程序，这个范围更新的数据已经无效了，但是因为传递给了子节点，所以[0,2]范围的值是2还是有效的，但是[3,5]的范围还是要被经过，还是要被修改，依次类推。

到叶节点一定会停下，因为叶节点的懒惰标记始终为1

void search(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r&&tree[p].flag==1){
        sum=sum+(tree[p].right-tree[p].left+1)*tree[p].value;
        return; 
    }
    int mid=(tree[p].left+tree[p].right)/2;
    if(r<=mid) search(l,r,p*2);
    else if(l>mid) search(l,r,p*2+1);
    else{
        search(l,mid,p*2);
        search(mid+1,r,p*2+1);
    }
}

在计算总数的时候，如果遇到父节点的懒惰标记为1，那么直接增加整段父节点的值即可~

AC代码

基本上面的分析代码已经都给出了，AC代码就不贴了，整合一下就行，毕竟重点还是理解

区间刷新，单点刷新以及其他的一些操作知识，都只是线段树中的基本操作，比赛时很少会有这么裸的题，后续会增加真题实战，但是会发现把只要线段树基础操作理解了，这些真题也就迎刃而解了