BST-线段树学习笔记_线段树求解bst

         线段树是一种特殊的二叉树——其储存的结点代表一个线段（区间），常用于解决RMQ问题，其根本原理是二分查找，是一棵平衡二叉树，因此修改和查询最值的复杂度都是O（log2n）的。

        对于每一个线段树的结点，其两个子结点分别是线段区间的前半段的后半段：

线段树的实现结构

        在线段树的初步引入中，我们先从一个结构体开始，它储存了以下信息：

（1）线段的左、右值

（2）线段的长度

struct Node{
    int l, r;
    int len;
}

         这个结构体的内涵和作用非常明朗，但事实上，线段的左右值是可以在访问的同时实时计算出来的，我们只需要这个结点的下标和线段长度两个参数，因此用整形数组来实现线段树会更简洁。

const int maxn = 1000;
int tree[maxn];

        首先，我们默认线段树的根结点是一个从0开始的线段（如0-5），其长度代表了这棵线段树有效叶子结点的数量。

        随后，根据下线段树二分的特性，我们可以根据任意结点的下标算出其父节点，左儿子结点和右儿子结点的下标：注意，为了增加引索的效率，我们采用a[1]作为根结点而非a[0]:

        而对于任意结点的值（区间长度），其中值mid=len*1/2是左儿子的右值，mid+1是右儿子的左值，而左儿子的左值等于结点的左值，右儿子的右值等于结点的右值。   

线段树结点的插入

        线段树的结点插入，实际上插入的是叶子结点（一个数），你会发现除了叶子结点是实际存在的，其余树枝只是对叶子结点的一种描述，只是我们找到叶子结点的工具，这和普通的二叉树有很大的不一样，但插入逻辑和朴素的二叉树插入是一致的（因为朴素二叉树也是添加叶子结点，都是add操作，而Treap需要增加叶子结点后旋转调整到合适的位置，是insert操作）。

void add(int pos, int left, int right, int num){//当前访问的数组下标、左值、右值、要插入的数字
    tree[pos]++;        //路径上的len加1    
    if(num==right && num==left){    //找到对应的叶子位置
        return;
    }
    int mid = (left+right)/2;        //计算区间中点
    int left_son = pos*2;        //计算左儿子下标
    int right_son = pos*2+1;        //计算右儿子下标
    if(num<=mid){
        add(left_son,left,mid,num);    //插入到左子树
    }
    else{
        add(right_son,mid+1,right,num);//插入右子树
    }
}

线段树结点的查询

        在此处我们先给出常见的一种线段树结点的查询，线段树查询实际上是查询叶子结点的位置，因此我们只要计算当前区间的左值、中值和右值，就可以判断num在哪个区间中。

int search(int pos, int left, int right, int num){//当前下标，当前区间，查找的数
    if(num==right && num==left)        //找到了相应的叶子结点
        return tree[pos];
    int mid = (left+right)/2;        //计算区间中点
    int left_son = pos*2;        //计算左儿子下标
    int right_son = pos*2+1;        //计算右儿子下标
    if(num<=mid)
        return search(left_son,left,mid,num);
    else
        return search(right_son,mid+1,right,num);
}

        需要注意的是，查询线段树的结点并不是真的为了得到什么值，而是在查询的过程中对树做出修改并维护；或者自定义搜索的操作，这里只给出核心模板，如果需要删除结点或增加结点数量，都可以在查询的路径上增加或减少len的值。

用满二叉树建线段树

        如果你不想一个结点一个结点地插入来构建树，而是直接知道根区间的值来建一棵树，我们可以利用满二叉树来建线段树。注意，满二叉树只是描述了这颗树的外观，并不是代表所有的结点都必须是有效的，我们用空结点（len=0）来补充空位。

        直接给出模板代码，这是一个很方便的建初始树的方法：

#include<stdio.h>
using namespace std;
const int maxn = 1000;
int tree[maxn*4];
void push_up(int pos){    //向上更新len值
    tree[pos] = tree[pos*2] + tree[pos*2+1];    
}
void build(int pos, int left, int right){
    if(left == right)    return;
    int mid = (left+right)/2;        //计算区间中点
    int left_son = pos*2;        //计算左儿子下标
    int right_son = pos*2+1;        //计算右儿子下标
    build(pos*2,left,mid);
    build(pos*2+1,mid+1,right);
    push_up(pos);
}
int main(){
    int n;
    cin>>n;
    build(1,n,1);
}

用完全二叉树建线段树

        关于完全二叉树的简单概念可以查看本栏关于二叉树的笔记，或自行百度二叉树学习笔记_ex_voda的博客-CSDN博客

        我们终于有幸在这实现对其的利用。利用完全二叉树实现线段树的好处是：我们可以直接算出父节点和子节点的各项线段参数以及叶子结点（最后一行）的结点位置，从而达到结点的传递，这更快也更方便，对于空结点，令其值等于0就好。 

        读者可以自行根据上图比对结点数值之间的关系。

        那么首先我们需要搞清楚几个问题：

1、如何在完全二叉线段树中找到最后一行第一个叶子结点的下标

        不进行证明，完全二叉线段树最后一行的最左下标last_left是大于等于有效叶子结点数n最小的2的指数，例如n=3，last_left=4；n=5,last_left=8；因此当已知n，求last_left的公式为：

last_left = 1 << (int(log(n)/log(2)) + 1);

        值得一提的是，完全二叉线段树的插入仍然可以是朴素的，只是记得更新n和last_left即可。 

2、如何利用完全二叉树的性质引索结点信息 

        对于完全二叉树而言，每一行的最左结点的下标永远是2的指数（根结点是2^0=1），因此当前行的下标范围是从上一行的最左结点下标/2到上一行的最左结点下标-1为止，或者上一行的最左结点下标*2，到上一行的最左结点下标*3-1为止，用代码表示：

for(i=last_left/2;i<last_left;i++)    //遍历,last_left表示下一行的最左下标
for(i=pre_left*2;i<pre_left*3;i++)    //遍历,pre_left表示上一行的最左下标

        解决了下标问题，随后是结点内容，也就是区间长度的引索。

        逻辑很简单：当前节点的区间长度等于其两个子区间的长度的和（有点类似名次树的size）结合下标引索，很容易做到：

tree[pos] = tree[pos*2] + tree[pos*2+1];

3、建树的基本逻辑 

        任何二叉树的建树都需要已知量的参与，线段树也一样。我们如果已知叶子节点数n，我们可以默认这n个节点是紧密地顺序排列的，并自定义它们的编号映射（例如你需要用线段树储存ABCDE这5个节点，只需要用n=5建树，找到last_left=8，随后从A=8，B=9依次建立映射即可实现实际意义的操作），对于完全二叉线段树的最后一行而言，空结点的区间长度为0。

        在建树的时候，我们从树的最后一行开始往上倒推，首先给最后一行的n个有效叶子结点赋值为1，其余为0，随后根据下标引索和内容引索的规则逐行递推即可。

const int Max = 1000;
int tree[4*Max];    //完全二叉树需要4倍结点空间
void Build_Tree(int n,int last_left){
    int i;
    for(i = last_left;i<last_left+n;i++)
        tree[i] = 1;    //给有效结点赋值
    while(last_left != 1){    //从最后一行倒推到根结点
        for(i = last_left/2;i<last_left;i++)
            tree[i] = tree[i*2] + tree[i*2+1];
        last_left /= 2;
    }
}                                                    

4、完全二叉线段树的查询

int query(int pos, int num, int last_left){
    if(tree[pos] == 1 && pos >= last_left)
        return pos;
    //左子区间叶子结点数量足够，查询左子区间中左起第num个元素
    if(tree[pos<<1]>=num)
        return query(u<<1,num,last_left);
    else
    //左子区间结点数量不够，查询右子区间中左起第num-tree[pos<<1]个元素
        return query((pos<<1)+1,num-tree[u<<1],last_left);
}

离散化

        所谓的离散化实际上就是对线段树的结点区间进行去重，避免被覆盖的无效结点占据内存空间。一般来说，需要离散化的情况都是已知一些杂乱的区间来建树，在建树之前，我们对这些杂乱区间进行离散化，随后重新建立映射，完成高效建树。

        离散化的步骤如下：

（1）提取这些区间的所有端点。

（2）排序并删除相同的端点。

（3）将剩下的端点重新映射到新的有序线段上。

区间修改——lazy

        对线段树的区间进行修改，如果采用朴素的点修改法会浪费大量的时间。lazy法的思想逻辑是：对需要修改的最上层区间进行修改，并标记，而封装此区间下的子树结点不做变化，只要当某操作需要深入到此区间的子树时，才进行更深入的修改。

        举个例子：小区、单元楼和住户分别是3个深度的树结点，现在让给A小区发m袋大米，让A小区均分给单元楼，单元楼再均分给住户。朴素法是找到相应的住户，发米，回溯到单元楼，统计米数，再回溯到小区；而懒值法只在小区层面进行修改，相当于先不把米给住户，这样当你询问A小区有多少米的时候，答案是一样的。而如果你想要询问某某住户有多少米，这时候操作深入了lazy标记的层（小区），再把米发给住户保证答检查正确。

        了解了算法思想，现在开始试图实现它。首先我们默认你已经用上面的各种方法建好一棵满二叉树或者完全二叉树了，现在重点是用lazy法修改它的区间值。

        区间修改的主要操作是改和查，此处改我们以求和为例。实现思路如下： （1）需要重申的是，树的建立是基于key的，而区间修改的操作是基于value的，我们不希望对value的修改会改变树的形状，因此很基础地，用一个单独的数组（或者结构体）来映射key-value，在这里我们以求和区间修改为例，因此采用sum[]。对于映射数组时常需要一个更新函数，且在树中往往是从下往上更新的，给出push_up()（应具体操作需求而异）：

void push_up(int pos){
    sum[pos] = sum[pos<<1] + sum[pos<<1|1];
}

（2）当我们进行区间修改操作时，是从树的根开始往下遍历的，在到达目标层之前的路径上有两种情况：1、当前层没有被lazy标记，什么都不用做；2、当前层已经被lazy标记过了，但是由于还没有到目标层，因此这个lazy标记作废，带着旧lazy标记的数据继续往下直到目标层。你会发现lazy标记并不不是一个bool值代表此处是否有“待分配的操作值”，事实上我们可以直接让lazy标记记录具体的操作值，以便以后的操作，由于以加和为例，采用add[]数组。给出向下更新函数push_down()：

void push_down(int pos, int mid){
    if(add[pos]){
        add[pos<<1] += add[pos];
        add[pos<<1|1] += add[pos];
        sum[pos<<1] += (mid - (mid>>1)) * add[pos];
        sum[pos<<1|1] += (mid>>1) * add[pos];
        add[pos]= 0;        //消除本层标记
    }
}

（3）接下来，我们以“让a-b区间里每一个数都+c”这个操作为例，构造区间更新/区间修改函数update()，这个函数是应操作而异的：

void update(int a,int b, long long c, int left, int right, int pos){
    if(a<=left && b>=right){    //此区间是[a,b]的子区间
        sum[pos] += (right - left +1) + c;
        add[pos] += c;
        return;
    }
    push_down(pos,right-left+1);    //向下更新
    int mid = (left + right) / 2;
    if(a<=mid)    update(a,b,c,left,mid,pos<<1);
    else          update(a,b,c,mid+1,right,pos<<1|1);
    push_up(pos);        //回溯，向上更新
}

        在区间更新的过程中可以发现，实际上就是用push_down向树的深处深入，找到符合要求的区间，修改，回溯的同时用push_up自下而上更新，从而在进、出的路径上维护树的lazy（add）状态和lazy标记。

---

参考题目

简单题：hdu 1166/1394/1698/1754/2795

               poj 1195/2182/2299/2828/2352/2750/2886/2777/3264/3468

中等题：hud 1540/1823/4027/5869

               poj 2155/2528/2823/3225

综合题：hdu 1255/1542/3642/3974/4578/4614/4718/5756/4441