线段树

线段树

一 什么是线段树
线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]

二 线段树的性质
1 线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b]。长度为1的线段称为元线段。非元线段都有两个子结点，左结点代表的线段为[a,(a + b) / 2]，右结点代表的线段为[((a + b) / 2）+1,b]。
2 线段树是平衡二叉树，最大深度为logN(N为线段树所标示的区间的长度)。我们知道一颗线段树的叶子节点的长度为1，那么假设高度为h，
则2^(h-1) = N , 有h = logN+1，当N无穷大的时候趋于logN。
3 假设一个区间长度为N即[1 , N]，根据线段树的根节点表示[1 , N]，然后将区间分成两半那么线段树最多的节点数是2N-1个。保守起见，开辟的空间为4*N。
4 线段树主要用于处理一段连续区间的插入，查找，统计，查询等操作，操作的时间复杂度为O(logN)。建立一颗线段树的时间复杂度为O(N)。

5 注意位运算的时候“+”比“>>”和“<<“高，所以应该要括号。

6 线段树是可以用来求解所有RMQ问题，所有树状数组可以解决的问题线段树都可以做。

三 线段树的模板

1 单点更新（hdu1166为例），单点更新都是更新叶子节点上面然后顺带更新根到叶子节点路径上的点。

struct Node{
 int left;
 int right;
 int sum;
};
Node node[4*MAXN];/*最多需要分配的空间*/
int number[MAXN];

//向上更新
void push_up(int pos){
 node[pos].sum = node[pos<<1].sum + node[(pos<<1)+1].sum;/*向上更新当前点的信息*/
}

/*建立空的二叉树，初始化每个营地人数为0*/
void buildTree(int left , int right , int pos){
 node[pos].left = left;
 node[pos].right = right;
 if(left == right){
 node[pos].sum = number[left];
 return;
 }
 /*递归建立子树*/
 int mid = (left+right)>>1;
 buildTree(left , mid , pos<<1);
 buildTree(mid+1 , right , (pos<<1)+1);
 push_up(pos);
}

/*单点更新*/
void update(int index , int num , int pos){
 if(node[pos].left == node[pos].right){
 node[pos].sum += num;
 return;
 }
 int mid = (node[pos].left+node[pos].right)>>1;
 if(index <= mid)
 update(index , num , pos<<1);
 else 
 update(index , num , (pos<<1)+1);
 push_up(pos);/*路径上的点都要向上更新*/
}

/*区间查询分成三种可能的区间
1 都在左儿子这个区间
2 都在右儿子这个区间
3 跨越左右儿子
*/
int query(int Left , int Right , int pos){
 if(node[pos].left == Left && node[pos].right == Right) 
 return node[pos].sum;
 int mid = (node[pos].left+node[pos].right)>>1;
 if(Right <= mid)
 return query(Left , Right , pos<<1);
 else if(Left > mid)
 return query(Left , Right , (pos<<1)+1);
 else
 return query(Left , mid , pos<<1)+query(mid+1 , Right , (pos<<1)+1);
}

2 成段更新

1 成段更新和单点更新是不同的，单点更新是要更新到叶子节点，但是对于成段更新是更新到某个区间即可，找个区间是当前需要的更新的区间的最大的子区间
2 成段更新需要维护一个“延时标记”，初始化看情况。我们先把标记放在一个大的区间，下次遇到的时候再进行向下的更新(标记传递)

代码：

//我们以区间更改和区间求和为样例
struct Node{
    int left;
    int right;
    int mark;//延时标记
    int sum;//和或者是其它的信息
};
Node node[4*MAXN];

//向上更新
void push_up(int pos){
    node[pos].sum = node[pos<<1].sum + node[(pos<<1)+1].sum;
}

//向下更新
void push_down(int pos){
    if(node[pos].mark){//如果可以继续往下更新
       node[pos<<1].mark += node[pos].mark;
       node[(pos<<1)+1].mark += node[pos].mark;
       node[pos<<1].sum += node[pos].mark*(node[pos<<1].right-node[pos<<1].left+1);
       node[(pos<<1)+1].sum += node[pos].mark*(node[(pos<<1)+1].right-node[(pos<<1)+1].left+1);
       node[pos].mark = 0;//当前点的延时标记更改为0
    }
}

//建立线段树
void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    node[pos].mark = 0;
    if(left == right){
        node[pos].sum = num[left];
        node[pos].mark = num[left];
        return;
    }
    int mid = (left+right)>>1;
    buildTree(left , mid , pos<<1);
    buildTree(mid+1 , right , (pos<<1)+1);
    push_up(pos);//向上更新
}

//成段更新
void update(int left , int right , int value , int pos){
    if(left <= node[pos].left && right >= node[pos].right){
      node[pos].mark += value;
      node[pos].sum += value*(node[pos].right-node[pos].left+1);
      return ;
    }
    push_down(pos);//向下更新
    int mid = (node[pos].left+node[pos].right)>>1;
    if(right <= mid)
        update(left , right , value , pos<<1);
    else if(left > mid)
        update(left , right , value , (pos<<1)+1);
    else{
        update(left , mid , value , pos<<1);
        update(mid+1 , right , value , (pos<<1)+1);
    }
    push_up(pos);//向上更新
}

int query(int left , int right , int pos){
    if(node[pos].left == left && node[pos].right == right)
        return node[pos].sum;
    int mid = (node[pos].left+node[pos].right)>>1;
    push_down(pos);//这里还要进行向下更新，防止没有更新彻底
    if(right <= mid)
        return query(left , right , pos<<1);
    else if(left > mid)
        return query(left , right , (pos<<1)+1);
    else
        return query(left , mid , pos<<1) + query(mid+1 , right , (pos<<1)+1);
}

3 线段树的离散化

离散化：就是把一些离散化的点映射成一些连续的点，比如1 ， 1000，300000 ， 40000000可以离散化成1，2，3，4这四种点

那么区间也就可以离散成集中的点，比如有这四个区间[1,3] , [1000 , 3000] , [50000 , 600000] , [56798900 , 4546565654]l，那么我们只要对所有的值进行排序

1，3，1000，3000，50000，600000 ， 5678900，4546565654 那么就可以离散成1 ，2 ，3，4，5，6，7，8.那么区间就可以变成[1,2]，[3,4]，[5,6]，[7,8].那么这样就把相对离散的区间转化成集中的区间了，那么再利用线段树即可。