第三篇线段树了——重点不在于解决题目，通过题目理解线段树才是重点
前面写了一篇关于线段树的单点更新，线段树的单点更新就只要找到指定的叶节点并进行更新即可，这篇文章主要根据相关例题讲下关于线段树的区间更新
例题
题意
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代码就不贴了，整合一下就行，毕竟重点还是理解
区间刷新，单点刷新以及其他的一些操作知识，都只是线段树中的基本操作，比赛时很少会有这么裸的题，后续会增加真题实战，但是会发现把只要线段树基础操作理解了，这些真题也就迎刃而解了
