前言（胡言乱语）

“杭电杯”被狠狠薄纱???，发现队友都是大佬，只有我是蒟蒻！！！具体表现为~~(包括但不限于)~~只有我还不会线段树?，狠狠泪目！这就学?(･_･;

线段树的概念

线段树（Segment Tree）是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

线段树的应用

线段树适合解决的问题的特征是：大区间的解可以从小区间的解合并而来（区间加法!），即对于一个[L,R] = [L,M] + [M + 1,R].线段树对于区间的修改、维护和查询的时间复杂度优化为log级别。如果是要修改一个元素（单点修改），直接修改叶子节点上元素的值，然后从从下往上更新线段树；如果修改的是一个区间的元素（区间修改），需要用到Lazy-Tag技术。

线段树的构造

节点的构造

我们一般采用静态数组实现满二叉树，父节点和子节点之间的访问非常简单，缺点是最后一行有大量节点被浪费。

//定义二叉树数据结构struct {    int L;//左儿子    int R;//右儿子    int data;//记录线段i的最值或区间和}tree[N * 4]; //直接用数组表示二叉树int tree[N * 4];//记录线段i的最值或区间和

这两种都满足index_l = index_p << 1，index_r = index_p << 1 | 1

注意：二叉树的空间需要开N * 4，即元素数量的4倍

建树

建树的过程就是利用递归的思想，从上往下建树，从下往上传递区间值

int ls(int p){    return p << 1;} int rs(int p){    return p << 1 | 1;} void push_up(int p){    tree[p] = tree[ls(p)] + tree[rs(p)];} void build(int p,int pl,int pr){    if(pl == pr){        tree[p] = a[pl];//给叶节点赋值        return ;    }    int mid = (pl + pr) >> 1;//折半    build(ls(p),pl,mid);//构造左子树    build(rs(p),mid + 1,pl);//构造右子树    push_up(p);//更新节点信息}

区间查询

查询区间最值

以上面这个图为例，我们现在查询区间[3，7]之间的最值，从根节点开始，查询左右子树，存在一下3种情况
1、如果要查询的区间完全覆盖查询区间，就可以直接取值
2、如果要查询的区间与查询区间有交集，继续向下查询
3、如果要查询的区间与查询区间没有交集，那这个节点以及所有子节点的值对结果没有贡献

查询区间和

以上面这个图为例，我们现在查询区间[3，7]之间的和，从根节点开始，查询左右子树，存在一下3种情况
1、如果要查询的区间完全覆盖查询区间，就可以直接取值
2、如果要查询的区间与查询区间有交集，继续向下查询
3、如果要查询的区间与查询区间没有交集，那这个节点以及所有子节点的值对结果没有贡献

不难发现，无论要查询的是什么基本的思路都是：根据区间直接的覆盖情况来决定取值还是继续递归。

区间查询代码

int query(int l,int r,int p,int pl,int pr){//区间查询    if(l <= pl && pr <= r){//完全覆盖        return tree[p];//根据需要返回相应的值    }    int mid = (pl + pr) >> 1;    if(l <= mid){//左子树上有交集        res += query(l,r,pl, ls(p),mid);    }    if(r > mid){//右子树上有交集        res += query(l,r,pr,mid + 1,rs(p));    }    return res;}

区间操作与Lazy-Tag

Lazy-Tag

利用线段树的特征：线段树的节点tree[i]记录了区间i的值。可以再定义一个tag[i]用它统一记录区间i的修改，而不是一个一个地修改区间内的每个元素。~~看起来就慢的嘞~~
懒标记的精髓是：打标记和下传操作。若修改的是一个线段区间，就只对这个区间进行整体上的修改，打上tag标记，而它的子树先不进行修改，等需要使用到它的子树的时候，再对它的子树进行修改，把标记下传。

区间修改

图片[1]-学不会的线段树-五八三
以上图为例，我们现在要把区间[4,7]内的每个元素加2，按以下步骤进行操作：
1、左子树递归到节点11（标红的点），[4,4]被完全覆盖，打上标记tag[11] = 2，更新节点的值，不再继续深入
2、左子树递归返回，更新父节点的值

3、右子树递归到节点6，[5,6]被完全覆盖，打上标记tag[6] = 2，更新节点的值，不再继续深入
4、右子树递归返回，更新父节点的值

5、右子树递归到节点14，[7,7]被完全覆盖，打上标记tag[14] = 2，更新节点的值，不再继续深入
6、右子树递归返回，更新父节点的值

Q：好像tag并没有什么用啊
A：因为我们这里只对某个区间进行了一次操作，如果对多个区间进行多次操作的话，tag的作用就能很好的体现出来了

区间修改代码

void addTag(int t,int p,int pl,int pr){    tag[p] += t;//给节点p打标记    tree[p] += t * (pr - pl + 1);//更新节点信息} void push_down(int p, int pl, int pr){    if(tag[p]){//如果有标记，把标记下传        int mid = (pl + pr) >> 1;        addTag(tag[p],ls(p),pl,mid);        addTag(tag[p],rs(p),mid + 1,pr);        tag[p] = 0;//自己的标记被传走    }} void update(int l,int r,int p,int pl,int pr,int t){    if(l <= pl && pr <= r){//完全覆盖        addTag(t,p,pl,pr);//给节点p打标记        return ;    }    push_down(p,pl,pr);    int mid = (pl + pr) >> 1;    update(l,r,ls(p),pl,mid,t);    update(l,r,rs(p),mid + 1,pr,t);    push_up(p);//更新节点信息}