算法总结--线段树

叠甲：鄙人水平有限，本文为作者的学习总结，仅供参考。

1.线段树介绍

其每个树的节点表示一个区间，其孩子节点表示该区间二分下来的两个节点，其值可以表示这个区间数据的某种运算，如最值、求和等，以下以数组 [1,2,3,4] 为栗子说明,如下所示，根节点表示区间 [1,4] 的和，其它以此类推。

node：当前区间数的和[区间的左边界,区间的右边界]
           10[1,4]             
           /     \           
       3[1,2]    7[3,4]          
       /    \    /    \       
    1[1]  2[2]  3[3] 4[4]

有如上所示的二叉树以后我们获取区间和的时间复杂度就从 O(n 到了 O(logn,但数据量十分庞大时这是十分重要的。当然，在节点维护时需要使用一种特殊的方法进行 —— Lazy-tag 技术，这让修改的和时间复杂为降为了O(logn。

2.二叉树

如下编号为 K 的节点对应的左孩子为 K+K,右孩子为 K+K+1
在程序为了提高运行效率常常写成 K<<1 与 K<<1|1

node：节点编号
       K             
    /     \           
  K<<1   K<<1|1

3.Lazy-tag 技术

对于线段树来说，Lazy-tag 技术是十分的重要的，这是将时间复杂减小来的原因。
其实现的方法具体来说就是使用一些数来对节点进行标记，从而使只有对应区间的根节点会被进行更改，不其内部的值不做更改，具体代码实现见下文。

4.举个栗子——线段树模板题

题目描述

求出某区间每一个数的和。

这种要多次对不同的区间进行操作，线段树是很好的选择，其代码实现可以分为以下几个步骤

4.1.建树

// 创建一个开始编号为 index
// 区间为 [l,r] 的一个线段树
void build_tree(int index,int l,int r    
{
    // 如果为叶节点，即区间中自有一个数
    if(r == l
    {
        tree[index] = nums[l];
        return;
    }
    // 递归遍历所有的节点
    int m = (r+l >> 1; // 二分区间
    build_tree(index<<1,l,m;// 左孩子
    build_tree(index<<1|1,m+1,r;// 右孩子
    // 赋值，父节点值为其俩孩子的和
    tree[index] = treep[index<<1] + treep[index<<1|1];
}

4.2.维护线段树

在维护数据时，我使用 Lazy-tag 的方法进行处理，具体步骤如下：

【2】根据该节点是否被标记来确定是否要进行 lazy-tag的下传，通常使用push_down函数来实现
【3】判断是否进行左右节点的递归
【4】更新父节点的数据

// 父节点的 lazy-tag 向其孩子进行传递
void push_down(int index,int l,int r
{
    int m = (l+r>>1;
    // 左孩子
    tree[index<<1] += tag[index]*(m-l+1;
    tag[index<<1] += tag[index];
    // 右孩子
    tree[index<<1|] += tag[index]*(r-m;
    tag[index<<1|] += tag[index];  
    // 去除父节点的标志
    tag[index] = 0；
}
// 对编号为 index，区间 [l,r] 的中 [x,y] 进行修改
void update(int index,int l,int r,int x,int y
{
    // [1] 判断区间 [l,r

编程笔记 » 算法总结--线段树