数据结构——线段树c++

线段树概讲

为什么是概讲呢，因为线段树包含的东西太多了，现在我也只搞明白了，线段树的建立 、线段树的查询、线段树的单节点更新，至于颇有难度的 区间更新就简单的写下来以供各位大佬看后一笑。因为线段树的知识本人并未经过系统学习，通过看各位大神的博客方才有了自己一些不成熟的理解。我将会在文章末尾附上学生学习时的链接，供各位老师更进一步。

线段树的建立

首先要知道什么是线段树：
线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。
如果觉得概念晦涩难懂的话，咱就上图在图中我们可以看到线段0-5在分成一个一个的左孩子 右孩子后出现了六个单一的节点，如图所示在第四行里就有0 1 3 4 四个单一的节点。从现在起我们叫这种单一的节点为叶子节点 除此之外其余的不为单一的点我们叫它非叶子节点。
你可能会很疑惑，为什么要用线段树来将一个如此简单的问题复杂化呢，别急我们举一个例子来说明这种算法的好处。

问题描述如下:从数组arr[0…n-1]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。

对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。

另一种解法：使用一个二维数组来保存提前计算好的区间[i,j]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。

我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

叶子节点是原始组数arr中的元素
非叶子节点代表它的所有子孙叶子节点所在区间的最小值

例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr[0…5]内的最小值是1）：
由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点，因此存储线段是需要的空间复杂度是O(n)。尤其是在节点需要更新时，时间复杂度将会大大提高。
在下面这个杭电的题中我们可以看到，我们可能需要对每一个叶子节点的值进行更新，并且对一定区间上的叶子节点进行求和。当这个数据很少的时候相信我们不需要借助计算机就能很好的完成，但当数据量很大的时候这无疑就是一个苦差事了。

hdu1166敌兵布阵

Problem Description

C国的死对头A国这段时间正在进行军事演习，所以C国情报头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
*情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

此题只是一个帮助大家打开思路的一道题，如果想要具体解出还需借助我们下面要讲的查询以及更新算法。
好了，铺垫了这么多相信各位老师都想打人了，咱现在言归正传，听听学生如何讲这个线段树的建立。

对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树，我们也可以用数组来存储。
struct SegTreeNode

{

int val;

}；我们用一个结构体来存储每一个节点中的数字，为何要用结构体呢，在接下来的区间更新中我们将用到一个延迟标记，这时结构体将比数组更为方便。
此代码是用来求最小值的代码，因为此代码理解起来十分简单，所以我们都用求最小值的问题来讲解下文的各种线段树算法 如果对代码感觉不懂可以参照图片进一步理解定义包含n个节点的线段树 SegTreeNode segTree[n]，segTree[0]表示根节点。那么对于节点segTree[i]，它的左孩子是segTree[2* i + 1], 右孩子是segTree[2 * i + 2]。
我们可以从根节点开始，平分区间，递归的创建线段树，线段树的创建函数如下：

const int MAXNUM = 1000;
struct SegTreeNode
{
    int val;
}segTree[MAXNUM];//定义线段树

/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
    if(istart == iend)//叶子节点
        segTree[root].val = arr[istart];
    else
    {
        int mid = (istart + iend) / 2;
        build(root*2+1, arr, istart, mid);//递归构造左子树
        build(root*2+2, arr, mid+1, iend);//递归构造右子树
        //根据左右子树根节点的值，更新当前根节点的值
        segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    }
}

线段树的查询

已经构建好了线段树，那么怎样在它上面找某个区间的最小值呢？查询的思想是选出一些区间，使他们相连后恰好涵盖整个查询区间，因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下，具体见代码解释：

对照图方便理解

/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
    //查询区间和当前节点区间没有交集
    if(qstart > nend || qend < nstart)
        return INFINITE;
    //当前节点区间包含在查询区间内
    if(qstart <= nstart && qend >= nend)
        return segTree[root].val;
    //分别从左右子树查询，返回两者查询结果的较小值
    int mid = (nstart + nend) / 2;
    return min(query(root*2+1, nstart, mid, qstart, qend),
               query(root*2+2, mid + 1, nend, qstart, qend));

}

举例说明（对照上面的二叉树）：

1、当我们要查询区间[0,2]的最小值时，从根节点开始，要分别查询左右子树，查询左子树时节点区间[0,2]包含在查询区间[0,2]内，返回当前节点的值1，查询右子树时，节点区间[3,5]和查询区间[0,2]没有交集，返回正无穷INFINITE，查询结果取两子树查询结果的较小值1，因此结果是1.

2、查询区间[0,3]时，从根节点开始，查询左子树的节点区间[0,2]包含在区间[0,3]内，返回当前节点的值1；查询右子树时，继续递归查询右子树的左右子树，查询到非叶节点4时，又要继续递归查询：叶子节点4的节点区间[3,3]包含在查询区间[0,3]内，返回4，叶子节点9的节点区间[4,4]和[0,3]没有交集，返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4，叶子节点3的节点区间[5,5]和[0,3]没有交集，返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。

线段树的单节点更新

单节点更新是指只更新线段树的某个叶子节点的值，但是更新叶子节点会对其父节点的值产生影响，因此更新子节点后，要回溯更新其父节点的值。

/*
功能：更新线段树中某个叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
index: 待更新节点在原始数组arr中的下标
addVal: 更新的值（原来的值加上addVal）
*/
void updateOne(int root, int nstart, int nend, int index, int addVal)
{
    if(nstart == nend)
    {
        if(index == nstart)//找到了相应的节点，更新之
            segTree[root].val += addVal;
        return;
    }
    int mid = (nstart + nend) / 2;
    if(index <= mid)//在左子树中更新
        updateOne(root*2+1, nstart, mid, index, addVal);
    else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新
    //根据左右子树的值回溯更新当前节点的值
    segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}

比如我们要更新叶子节点4（addVal = 6）,更新后值变为10，那么其父节点的值从4变为9，非叶结点3的值更新后不变，根节点更新后也不变。

线段树的区间更新

区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其相应的非叶父节点，那么回溯需要更新的非叶子节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不是O(lgn)，例如当我们要更新区间[0,3]内的叶子节点时，需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念，这也是线段树的精华所在。

延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。

因此需要在线段树结构中加入延迟标记域，本文例子中我们加入标记与addMark，表示节点的子孙节点在原来的值的基础上加上addMark的值，同时还需要修改创建函数build 和 查询函数 query，其中区间更新的函数为update，代码如下：

const int INFINITE = INT_MAX;
const int MAXNUM = 1000;
struct SegTreeNode
{
    int val;
    int addMark;//延迟标记
}segTree[MAXNUM];//定义线段树

/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
    segTree[root].addMark = 0;//----设置标延迟记域
    if(istart == iend)//叶子节点
        segTree[root].val = arr[istart];
    else
    {
        int mid = (istart + iend) / 2;
        build(root*2+1, arr, istart, mid);//递归构造左子树
        build(root*2+2, arr, mid+1, iend);//递归构造右子树
        //根据左右子树根节点的值，更新当前根节点的值
        segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
    }
}

/*
功能：当前节点的标志域向孩子节点传递
root: 当前线段树的根节点下标
*/
void pushDown(int root)
{
    if(segTree[root].addMark != 0)
    {
        //设置左右孩子节点的标志域，因为孩子节点可能被多次延迟标记又没有向下传递
        //所以是 “+=”
        segTree[root*2+1].addMark += segTree[root].addMark;
        segTree[root*2+2].addMark += segTree[root].addMark;
        //根据标志域设置孩子节点的值。因为我们是求区间最小值，因此当区间内每个元
        //素加上一个值时，区间的最小值也加上这个值
        segTree[root*2+1].val += segTree[root].addMark;
        segTree[root*2+2].val += segTree[root].addMark;
        //传递后，当前节点标记域清空
        segTree[root].addMark = 0;
    }
}

/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
    //查询区间和当前节点区间没有交集
    if(qstart > nend || qend < nstart)
        return INFINITE;
    //当前节点区间包含在查询区间内
    if(qstart <= nstart && qend >= nend)
        return segTree[root].val;
    //分别从左右子树查询，返回两者查询结果的较小值
    pushDown(root); //----延迟标志域向下传递
    int mid = (nstart + nend) / 2;
    return min(query(root*2+1, nstart, mid, qstart, qend),
               query(root*2+2, mid + 1, nend, qstart, qend));

}

/*
功能：更新线段树中某个区间内叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[ustart, uend]: 待更新的区间
addVal: 更新的值（原来的值加上addVal）
*/
void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
{
    //更新区间和当前节点区间没有交集
    if(ustart > nend || uend < nstart)
        return ;
    //当前节点区间包含在更新区间内
    if(ustart <= nstart && uend >= nend)
    {
        segTree[root].addMark += addVal;
        segTree[root].val += addVal;
        return ;
    }
    pushDown(root); //延迟标记向下传递
    //更新左右孩子节点
    int mid = (nstart + nend) / 2;
    update(root*2+1, nstart, mid, ustart, uend, addVal);
    update(root*2+2, mid+1, nend, ustart, uend, addVal);
    //根据左右子树的值回溯更新当前节点的值
    segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}

区间更新举例说明：当我们要对区间[0,2]的叶子节点增加2，利用区间查询的方法从根节点开始找到了非叶子节点[0-2]，把它的值设置为1+2 = 3，并且把它的延迟标记设置为2，更新完毕；当我们要查询区间[0,1]内的最小值时，查找到区间[0,2]时，发现它的标记不为0，并且还要向下搜索，因此要把标记向下传递，把节点[0-1]的值设置为2+2 = 4，标记设置为2，节点[2-2]的值设置为1+2 = 3，标记设置为2（其实叶子节点的标志是不起作用的，这里是为了操作的一致性），然后返回查询结果：[0-1]节点的值4；当我们再次更新区间[0,1]（增加3）时，查询到节点[0-1],发现它的标记值为2，因此把它的标记值设置为2+3 = 5，节点的值设置为4+3 = 7；

其实当区间更新的区间左右值相等时（[i,i]），就相当于单节点更新，单节点更新只是区间更新的特例。

实践检验真理（来个水题）

还是杭电的1166 敌兵布阵 链接在此

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int tree[50005*3];
void creat(int root,int l,int r)
{
    if(l==r)
    {
        scanf("%d",&tree[root]);
        return;///别忘了return。
    }
    int mid;
    mid = (l+r)/2;
    creat(root*2,l,mid);
    creat(root*2+1,mid+1,r);
    tree[root] = tree[root*2]+tree[root*2+1];
}
void updata(int root,int l,int r,int index,int x)
{
    if(l==r)
    {
        tree[root] += x;
        return;
    }
    int mid = (l+r)/2;
    if(index<=mid)
    updata(root*2,l,mid,index,x);
    else updata(root*2+1,mid+1,r,index,x);
    tree[root] = tree[root*2]+tree[root*2+1];
}
int show(int root,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)///包含在内。
    {
        return tree[root];
    }
    int mid = (l+r)/2;
    int res = 0;
    if(mid>=L)///看看所找的区域在左边还是右边。
        res += show(root*2,l,mid,L,R);
    if(mid<R)
        res += show(root*2+1,mid+1,r,L,R);
    return res;
}
int main()
{
    int T;
    int n;
    int a,b;
    char str[6];
    scanf("%d",&T);
    int t = 0;
    while(T--)
    {
        scanf("%d",&n);///输入n。
        creat(1,1,n);
        printf("Case %d:\n",++t);
        while(~scanf("%s",str))
        {
            if(strcmp(str,"End")==0)
                break;
            if(strcmp(str,"Add")==0)
            {
                scanf("%d%d",&a,&b);
                updata(1,1,n,a,b);
            }
            else if(strcmp(str,"Sub")==0)
            {
                scanf("%d%d",&a,&b);
                updata(1,1,n,a,-b);
            }
            else
            {
                scanf("%d%d",&a,&b);
                int r = show(1,1,n,a,b);
                printf("%d\n",r);
            }
        }
    }
    return 0;
}

诸多借鉴，持续更新····