线段树基本概念

1：概述

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

性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍。

 

2：基本操作（demo用的是查询区间最小值）

 

线段树的主要操作有：

 

(1)：线段树的构造 void build(int node, int begin, int end);

 

主要思想是递归构造，如果当前节点记录的区间只有一个值，则直接赋值，否则递归构造左右子树，最后回溯的时候给当前节点赋值

#include 
     
        using namespace std;    const int maxind = 256;  int segTree[maxind * 4 + 10];  int array[maxind];   /* 构造函数，得到线段树 */  void build(int node, int begin, int end)    {        if (begin == end)            segTree[node] = array[begin]; /* 只有一个元素,节点记录该单元素 */      else        {             /* 递归构造左右子树 */           build(2*node, begin, (begin+end)/2);            build(2*node+1, (begin+end)/2+1, end);                      /* 回溯时得到当前node节点的线段信息 */            if (segTree[2 * node] <= segTree[2 * node + 1])                segTree[node] = segTree[2 * node];            else                segTree[node] = segTree[2 * node + 1];        }    }    int main()  {      array[0] = 1, array[1] = 2,array[2] = 2, array[3] = 4, array[4] = 1, array[5] = 3;      build(1, 0, 5);      for(int i = 1; i<=20; ++i)       cout<< "seg"<< i << "=" <
      
       <
      
     

 

 

为什么需要线段树？

题目一： 10000个正整数，编号1到10000，用A[1],A[2],A[10000]表示。 修改：无 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.

方法一：对于统计L,R ，需要求下标从L到R的所有数的和，从L到R的所有下标记做[L..R],问题就是对A[L..R]进行求和。

这样求和，对于每个询问，需要将(R-L+1)个数相加。

 

方法二：更快的方法是求前缀和,令 S[0]=0, S[k]=A[1..k] ，那么，A[L..R]的和就等于S[R]-S[L-1]，

这样，对于每个询问，就只需要做一次减法，大大提高效率。

 

 

题目二： 10000个正整数，编号从1到10000，用A[1],A[2],A[10000]表示。 修改：1.将第L个数增加C （1 <= L <= 10000） 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.

再使用方法二的话，假如A[L]+=C之后，S[L],S[L+1],,S[R]都需要增加C,全部都要修改，见下表。

 

	方法一	方法二
A[L]+=C	修改1个元素	修改R-L+1个元素
求和A[L..R]	计算R-L+1个元素之和	计算两个元素之差

从上表可以看出，方法一修改快，求和慢。 方法二求和快，修改慢。

那有没有一种结构，修改和求和都比较快呢？答案当然是线段树。

 

线段树的点修改

 

上面的问题二就是典型的线段树点修改。

线段树先将区间[1..10000]分成不超过4*10000个子区间，对于每个子区间，记录一段连续数字的和。

之后，任意给定区间[L,R]，线段树在上述子区间中选择约2*log2(R-L+1)个拼成区间[L,R]。

如果A[L]+=C ，线段树的子区间中，约有log2(10000)个包含了L，所以需要修改log2(10000)个。

 

于是，使用线段树的话，

A[L]+=C 需要修改log2(10000) 个元素

求和A[L...R]需要修改2*log2(R-L+1) <= 2 * log2(10000) 个元素。

log2(10000) < 14 所以相对来说线段树的修改和求和都比较快。

 

 

问题一：开始的子区间是怎么分的？

首先是讲原始子区间的分解，假定给定区间[L,R]，只要L < R ，线段树就会把它继续分裂成两个区间。

首先计算 M = (L+R)/2，左子区间为[L,M]，右子区间为[M+1,R]，然后如果子区间不满足条件就递归分解。

以区间[1..13]的分解为例，分解结果见下图：

 

问题二：给定区间【L,R】，如何分解成上述给定的区间？

对于给定区间[2,12]要如何分解成上述区间呢？

 

分解方法一：自下而上合并——利于理解

先考虑树的最下层，将所有在区间[2,12]内的点选中，然后，若相邻的点的直接父节点是同一个，那么就用这个父节点代替这两个节点（父节点在上一层）。这样操作之后，本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树，那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树，那么这个节点会被剩下。中间的所有节点都被父节点取代。对最下层处理完之后，考虑它的上一层，继续进行同样的处理。

 

下图为n=13的线段树，区间[2,12]，按照上面的叙述进行操作的过程图：

由图可以看出：在n=13的线段树中，[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。

 

 

分解方法二：自上而下分解——利于计算

首先对于区间[1,13]，计算(1+13)/2 = 7，于是将区间[2,12]“切割”成了[2,7]和[8,12]。

其中[2,7]处于节点[1,7]的位置，[2,7] < [1,7] 所以继续分解，计算(1+7)/2 = 4, 于是将[2,7] 切割成[2,4]和[5,7]。

[5,7]处于节点[5,7]的位置，所以不用继续分解，[2,4]处于区间[1,4]的位置，所以继续分解成[2]和[3,4]。

最后【2】 < 【1,2】，所以计算(1+2)/2=1 ，将【2】用1切割，左侧为空，右侧为【2】

当然程序是递归计算的，不是一层一层计算的，上图只表示计算方法，不代表计算顺序。

 

 

如何进行区间统计？

假设这13个数为1,2,3,4,1,2,3,4,1,2,3,4,1. 在区间之后标上该区间的数字之和：

如果要计算[2,12]的和，按照之前的算法：

[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12]

  29  = 2 + 7 + 6 + 7 + 7

计算5个数的和就可以算出[2,12]的值。

 

如何进行点修改？

假设把A[6]+=7 ,看看哪些区间需要修改？[6],[5,6],[5,7],[1,7],[1,13]这些区间全部都需要+7.其余所有区间都不用动。

于是，这颗线段树中，点修改最多修改5个线段树元素（每层一个）。

下图中，修改后的元素用蓝色表示。

存储结构是怎样的？

 

线段树是一种二叉树，当然可以像一般的树那样写成结构体，指针什么的。

但是它的优点是，它也可以用数组来实现树形结构，可以大大简化代码。

数组形式适合在编程竞赛中使用，在已经知道线段树的最大规模的情况下，直接开足够空间的数组，然后在上面建立线段树。

简单的记法： 足够的空间 = 数组大小n的四倍。

 

实际上足够的空间 =  （n向上扩充到最近的2的某个次方）的两倍。

举例子：假设数组长度为5，就需要5先扩充成8，8*2=16.线段树需要16个元素。如果数组元素为8，那么也需要16个元素。 所以线段树需要的空间是n的两倍到四倍之间的某个数，一般就开4*n的空间就好，如果空间不够，可以自己算好最大值来省点空间。

怎么用数组来表示一颗二叉树呢？

 

假设某个节点的编号为v,那么它的左子节点编号为2*v，右子节点编号为2*v+1。

然后规定根节点为1.这样一颗二叉树就构造完成了。通常2*v在代码中写成 v<<1 。 2*v+1写成 v<<1|1 。

 

 

代码中如何实现？

(0)定义：

#define maxn 100007  //元素总个数  int Sum[maxn<<2];//Sum求和，开四倍空间int A[maxn],n;//存原数组下标[1，n]

 

(1)建树：

//PushUp函数更新节点信息，这里是求和void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  //Build函数建立线段树void Build(int l,int r,int rt){ //[l,r]表示当前节点区间，rt表示当前节点的实际存储位置     if(l==r) {//若到达叶节点         Sum[rt]=A[l];//存储A数组的值        return;      }      int m=(l+r)>>1;     //左右递归    Build(l,m,rt<<1);      Build(m+1,r,rt<<1|1);      //更新信息    PushUp(rt);  }

(2)点修改：

假设A[L]+=C:

void Update(int L,int C,int l,int r,int rt){//[l,r]表示当前区间，rt是当前节点编号//l,r表示当前节点区间，rt表示当前节点编号      if(l==r){//到达叶节点，修改叶节点的值        Sum[rt]+=C;          return;      }      int m=(l+r)>>1;     //根据条件判断往左子树调用还是往右    if(L <= m) Update(L,C,l,m,rt<<1);      else       Update(L,C,m+1,r,rt<<1|1);      PushUp(rt);//子节点的信息更新了，所以本节点也要更新信息}

点修改其实可以写的更简单，只需要把一路经过的Sum都+=C就行了，不过上面的代码更加规范，在题目更加复杂的时候，按照格式写更不容易错。

 

(3)区间查询（本题为求和）：

询问A[L..R]的和

注意到，整个函数的递归过程中，L,R是不变的。

首先如果当前区间[l,r]在[L,R]内部，就直接累加答案

如果左子区间与[L,R]有重叠，就递归左子树，右子树同理。

int Query(int L,int R,int l,int r,int rt){//[L,R]表示操作区间，[l,r]表示当前区间，rt:当前节点编号    if(L <= l && r <= R){         //在区间内直接返回        return Sum[rt];      }      int m=(l+r)>>1;      //左子区间:[l,m] 右子区间：[m+1,r]  求和区间:[L,R]   //累加答案    int ANS=0;      if(L <= m) ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠，递归    if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1); //右子区间与[L,R]有重叠，递归    return ANS;  }

 

 转自：http://blog.csdn.net/zearot/article/details/52280189

 

 相关博客推荐：http://blog.csdn.net/liujian20150808/article/details/51137749

                          http://www.cnblogs.com/xiaoyao24256/p/6590885.html