文章目录
一、线段树
二、线段树的基本内容
三、线段树的基本操作


一、线段树
1、线段树的树形结构：

线段树是一种二叉搜索树，什么叫做二叉搜索树，首先满足二叉树，每个结点度小于等于二，即每个结点最多有两颗子树，何为搜索，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。

2、线段树的应用：

线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。更可以扩充到二维线段树（矩阵树）和三维线段树（空间树）。对于一维线段树来说，每次更新以及查询的时间复杂度为O(logN)。

3、线段树和其他RMQ算法的区别：

常用的解决RMQ问题有ST算法，二者预处理时间都是O(NlogN)，而且ST算法的单次查询操作是O(1)，看起来比线段树好多了，但二者的区别在于线段树支持在线更新值，而ST算法不支持在线操作。

线段树不但可以用来处理RMQ问题和求和问题，而且其实线段树的功能远远不止如此，要熟练的理解线段这个概念才能更加深层次的理解线段树。
二、线段树的基本内容
每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。
代码：
const int maxn = 100005;
int a[maxn],t[maxn<<2];       

void Pushup(int k){       
    t[k] = max(t[k<<1],t[k<<1|1]);
}

void build(int k,int l,int r){   
    if(l == r)    
        t[k] = a[l];
    else{
        int m = l + ((r-l)>>1);
        build(k<<1,l,m);    
        build(k<<1|1,m+1,r);    
        Pushup(k);    
    }
}

三、线段树的基本操作
1.点更新：
代码：
//递归方式更新 updata(p,v,1,n,1);
void updata(int p,int v,int l,int r,int k){    
    if(l == r)   
        a[k] += v,t[k] += v;    
    else{
        int m = l + ((r-l)>>1);   
        if(p <= m)  
            updata(p,v,l,m,k<<1);
        else    
            updata(p,v,m+1,r,k<<1|1);
        Pushup(k);    
    }
}

2.区间查询：
//递归方式区间查询 query(L,R,1,n,1);
int query(int L,int R,int l,int r,int k){    
    if(L <= l && r <= R)   
        return t[k];
    else{
        int res = -INF;    
        int mid = l + ((r-l)>>1);    
        if(L <= m)    
            res = max(res, query(L,R,l,m,k<<1));
        if(R > m)   
            res = max(res, query(L,R,m+1,r,k<<1|1));

        return res;    
    }
}

3.区间更新：

树状数组中的区间更新我们用了差分的思想，而线段树的区间更新相对于树状数组就稍微复杂一点，这里我们引进了一个新东西，Lazy_tag，字面意思就是懒惰标记的意思，实际上它的功能也就是偷懒= =，因为对于一个区间[L,R]来说，我们可能每次都更新区间中的没个值，那样的话更新的复杂度将会是O(NlogN)，这太高了，所以引进了Lazy_tag，这个标记一般用于处理线段树的区间更新。

线段树在进行区间更新的时候，为了提高更新的效率，所以每次更新只更新到更新区间完全覆盖线段树结点区间为止，这样就会导致被更新结点的子孙结点的区间得不到需要更新的信息，所以在被更新结点上打上一个标记，称为lazy-tag，等到下次访问这个结点的子结点时再将这个标记传递给子结点，所以也可以叫延迟标记。

也就是说递归更新的过程，更新到结点区间为需要更新的区间的真子集不再往下更新，下次若是遇到需要用这下面的结点的信息，再去更新这些结点，所以这样的话使得区间更新的操作和区间查询类似，复杂度为O(logN)。
void Pushdown(int k){   
    if(lazy[k]){    
        lazy[k<<1] += lazy[k];   
        lazy[k<<1|1] += lazy[k];    
        t[k<<1] += lazy[k];        
        t[k<<1|1] += lazy[k];    
        lazy[k] = 0;    
    }
}

//递归更新区间 updata(L,R,v,1,n,1);
void updata(int L,int R,int v,int l,int r,int k){    
    if(L <= l && r <= R){    
        lazy[k] += v;    
        t[k] += v;    
    }
    else{
        Pushdown(k);    
        int m = l + ((r-l)>>1);
        if(L <= m)    
            update(L,R,v,l,m,k<<1);
        if(m < R)    
            update(L,R,v,m+1,r,k<<1|1);
        Pushup(k);    
    }
}

注意看Pushdown这个函数，也就是当需要查询某个结点的子树时，需要用到这个函数，函数功能就是更新子树的lazy值，可以理解为平时先把事情放着，等到哪天要检查的时候，就临时再去做，而且做也不是一次性做完，检查哪一部分它就只做这一部分。是不是感受到了什么是Lazy_tag，实至名归= =。
值得注意的是，使用了Lazy_tag后，我们再进行区间查询也需要改变。区间查询的代码则变为：
//递归方式区间查询 query(L,R,1,n,1);
int query(int L,int R,int l,int r,int k){    
    if(L <= l && r <= R)    
        return t[k];
    else{
        Pushdown(k);    
        int res = -INF;    
        int mid = l + ((r-l)>>1);    
        if(L <= m)    
            res = max(res, query(L,R,l,m,k<<1));
        if(R > m)   
            res = max(res, query(L,R,m+1,r,k<<1|1));

        return res;    
    }
}

其实变动也不大，就是多了一个临时更新子树的值的过程。