树状数组与线段树

分手后的思念是犯贱 2022-08-07 10:55 219阅读 0赞

**一：树状数组**

树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。

**需求：**有时候我们需要频繁地求数组的前k项和或者求数组从小标i到j的和，这样每次最坏情况下的时间复杂度就会为O(N)，这样效率太低了。而树状数组主要就是为了解决这样一个问题。树状数组在求和及修改都可以在O(lgN)时间内完成。

树状数组需要额外维护一个数组，我们设为C\[N\],原数组为A\[N\], 其中每个元素C\[i\]表示A\[i-2^k+1\]到A\[i\]的和，这里k是i在二进制时末尾0的个数。注意通过位运算有两种求2^k的技巧。这样我们就可以得到：

![Center][]

![Center 1][]

其中类似于树，故称为树状数组。

代码：

(1)求2的k次幂：

//  得到i最后2^k,, k为i在二进制末尾0的个数
    int lowBit(int i){
    	return i & (i^(i-1));
    	// return k & -k;
    }

(2)建立树状数组

// 获得数组C
    void getCArray(int *a, int n){
    	for(int i = 1; i <= n; i++){
    		int k = lowBit(i);
    		C[i] = 0;
    		for(int j = i -k+1; j <= i; j++){
    			C[i]+= a[j];
    		}
    	}
    }

(3) 求前n项和

// 求数组前i项和
    int sum(int i){
    	int s = 0;
    	while(i >= 1){
    		s += C[i];
    		i = i- lowBit(i);
    	}
    	return s;
    }

(4)更新树状数组

// i代表小标i的值， value为需要加的值， n为数组长度
    void update(int i, int value, int n){
    	while(i <= n){
    		C[i] = C[i]+value;   // 改变下标i的值
    		i = i + lowBit(i);
    	}
    }

完整代码：

#include <iostream>
    using namespace std;
    #define N 10
    int C[N];         // 数组C[i]为a[i-2^k+1]到a[i]的和 其中k为i在二进制时末尾0的个数
    
    //  得到i最后2^k,, k为i在二进制末尾0的个数
    int lowBit(int i){
    	return i & (i^(i-1));
    	// return k & -k;
    }
    
    // 获得数组C
    void getCArray(int *a, int n){
    	for(int i = 1; i <= n; i++){
    		int k = lowBit(i);
    		C[i] = 0;
    		for(int j = i -k+1; j <= i; j++){
    			C[i]+= a[j];
    		}
    	}
    }
    
    // 求数组前i项和
    int sum(int i){
    	int s = 0;
    	while(i >= 1){
    		s += C[i];
    		i = i- lowBit(i);
    	}
    	return s;
    }
    
    // i代表小标i的值， value为需要加的值， n为数组长度
    void update(int i, int value, int n){
    	while(i <= n){
    		C[i] = C[i]+value;   // 改变下标i的值
    		i = i + lowBit(i);
    	}
    }
    
    int main(){
    	int n;
    	cin >> n;
    	int *a = new int[n+1];
    	for(int i = 1; i <= n; i++)
    		cin >> a[i];
    
    	getCArray(a, n);    //  获取数组C
    	cout << sum(5) << endl;
    
    	update(3, 2, 5);   // 将a[3]加2
    	cout << sum(5) << endl;
    	cout << sum(4) << endl;
    	delete []a;
    
    	return 0;
    }

**二：线段树**

线段树主要用来求某一区间的最小值、最大值或者和等，都可以在O(lgN)时间内解决，类似于区间树。树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。树状数组有时比较难以理解，比如用树状数组求逆序数，所以个人建议树状数组就行了，没必要透彻，我就不用树状数组。

**(1)概念：**

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是\[a,b\]，那么(c=(a+b)/2)左儿子的区间是\[a,c\]，右儿子的区间是\[c+1,b\]。

**(2)从一个例子理解线段树**

下面我们从一个经典的例子来了解线段树，问题描述如下:从数组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）：

![Center 2][]图片3

由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，**对于包含n个叶子节点的类完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点**，因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作：创建线段树、查询、节点更新 是如何运作的呢（以下所有代码都是针对求区间最小值问题）？

**(3.1)创建线段树**

对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是类完全二叉树，我们也可以用数组来存储，下面的讨论及代码都是数组来存储线段树，节点结构如下（注意到用数组存储时，有效空间为2n-1,实际空间确不止这么多，比如上面的线段树中叶子节点1、3虽然没有左右子树，但是的确占用了数组空间，实际空间是满二叉树的节点数目： 2^(ceil(logN)+1)-1， logN 是树的高度，但是这个空间复杂度也是O(n)的 ）。

structSegTreeNode
    {
    　　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);
        }
    }

**(3.2) 查询线段树**

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

/*
    功能：线段树的区间查询
    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。

**(3.3) 单节点更新**

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

/*
    功能：更新线段树中某个叶子节点的值
    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的值更新后不变，根节点更新后也不变。

**(3.4) 区间更新**

区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其相应的非叶父节点，那么回溯需要更新的非叶子节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不是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\]），就相当于单节点更新，单节点更新只是区间更新的特例。

以上简介来源于：[http://www.cnblogs.com/TenosDoIt/p/3453089.html][http_www.cnblogs.com_TenosDoIt_p_3453089.html]

**(3.5)线段树的应用：**

（1）有一列数，初始值全部为0。每次可以进行以下三种操作中的一种：

a. 给指定区间的每个数加上一个特定值；

b.将指定区间的所有数置成一个统一的值；

c.询问一个区间上的最小值、最大值、所有数的和。

给出一系列a.b.操作后，输出c的结果。

\[问题分析\]

这个是典型的线段树的应用。在每个节点上维护一下几个变量：delta（区间增加值），same（区间被置为某个值），min（区间最小值），max（区间最大值），sum（区间和），其中delta和same属于“延迟标记”。

（2）在所有不大于30000的自然数范围内讨论一个问题：已知n条线段，把端点依次输入给你，然后有m（≤30000）个询问，每个询问输入一个点，要求这个点在多少条线段上出现过。

\[问题分析\]

在这个问题中，我们可以直接对问题处理的区间建立线段树，在线段树上维护区间被覆盖的次数。将n条线段插入线段树，然后对于询问的每个点，直接查询被覆盖的次数即可。

（3）某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票，即车上所有的旅客都有座，售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N为车票张数，售票系统对该售票申请作出受理或不受理的决定，只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理，请你写一个程序，实现这个自动售票系统。

\[问题分析\]

这里我们可以把所有的车站顺次放在一个数轴上，在数轴上建立线段树，在线段树上维护区间的delta与max。每次判断一个售票申请是否可行就是查询区间上的最大值；每个插入一个售票请求，就是给一个区间上所有的元素加上购票数。

这道题目在线段树上维护的信息既包括自下至上的递推，也包括了自上至下的传递，能够比较全面地对线段树的基本操作进行训练。

（4）给一个n\*n的方格棋盘，初始时每个格子都是白色。现在要刷M次黑色或白色的油漆。每次刷漆的区域都是一个平行棋盘边缘的矩形区域。

输入n,M,以及每次刷漆的区域和颜色，输出刷了M次之后棋盘上还有多少个棋格是白色。

\[问题分析\]

首先我们从简单入手，考虑一维的问题。即对于一个长度为n的白色线段，对它进行M次修改（每次更新某一子区域的颜色）。问最后还剩下的白色区域有多长。

对于这个问题，很容易想到建立一棵线段树的模型。复杂度为O(Mlgn)。

扩展到二维，需要把线段树进行调整，即首先在横坐标上建立线段树，它的每个节点是一棵建立在纵坐标上的线段树（即树中有树。称为二维线段树）。复杂度为O(M(logn)^2)。

图4

下面给出自己线段树的完整代码：

Segmentation.h

/*功能： 频繁查询数组某一区间的最小值, 包括更新数组某一区间或者某一结点的值
    实现： 线段树，用一个数组来存取(因为它是类完全二叉树)  具有n个结点的线段树需要2^lg(ceil(n)+1) -1 的空间, 是一个颗平衡查找树
    复杂度：预处理：创建线段树 O(n);; 查询更新时间复杂度O(lgN)， 需要额外的存储空间O(N)*/
    
    #include <iostream>
    using namespace std;
    #define maxInt 0x70000000
    #define N 100
    
    struct SegNode{
    	int minVal;
    	int left;
    	int right;
    	int addMark;
    	SegNode():left(0), right(0), minVal(0), addMark(0){}
    };
    
    class SegTree{
    private:
    	SegNode sn[N];
    	void pushDown(int root);
    
    public:
    	void buildSegTree(int root, int a[], int begin, int end);   // 创建线段树
    	int queryMin(int root, const int &qstart, const int &qend, int start, int end);  // 查找某区间内的最小值
    	void updateOneNode(int root, const int &index, const int &value, int start, int end); // 更新某一结点的值
    	void updateInterval(int root, const int &ustart, const int &uend, const int &value, int start, int end); // 更新区间的值
    	void display(int n);
    };

Segmentation.cpp

#include "SegmentionTree.h"
    #include <iostream>
    
    using namespace std;
    
    
    void SegTree::buildSegTree(int root, int a[], int begin, int end){
    	if(begin == end) {
    		sn[root].minVal = a[begin];
    		sn[root].left = begin;
    		sn[root].right = begin;
    		sn[root].addMark = 0;
    		return;
    	}
    	int mid = (begin + end)/2;
    	buildSegTree(root*2+1, a, begin, mid);
    	buildSegTree(root*2+2, a, mid+1, end);
    	sn[root].minVal = min(sn[root*2+1].minVal, sn[root*2+2].minVal);
    	sn[root].addMark = 0;
    	sn[root].left = begin;
    	sn[root].right = end;
    	return;
    }
    
    void SegTree::pushDown(int root){
    	if(sn[root].addMark){
    		sn[root*2+1].addMark += sn[root].addMark;
    		sn[root*2+1].minVal += sn[root].addMark;
    		sn[root*2+2].addMark += sn[root].addMark;
    		sn[root*2+2].minVal += sn[root].addMark;
    		sn[root].minVal = 0;
    	}
    }
    int SegTree::queryMin(int root, const int &qstart, const int &qend, int start, int end){
    	if(qstart > end || start > qend) return maxInt;     // 如果不想交 则返回
    	if(start >= qstart && end <= qend) return sn[root].minVal;  // 如果查询的范围比待查区间大 则返回该区间的最小值
    	int mid = (start + end)/2;
    
    	pushDown(root);
    	// 如果不在一个区间  则是相邻区间的信息可以被合并成两个区间的并区间的信息
    	return min(queryMin(root*2+1, qstart, qend, start, mid), queryMin(root*2+2, qstart, qend, mid+1, end));
    }
    
    void SegTree::updateOneNode(int root, const int &index, const int &value, int start, int end){
    	if(start == end){
    		if(index == start) sn[root].minVal += value;
    		else cout << "there is no node of index" << endl;
    		return;
    	}
    	pushDown(root);
    	int mid = (start+end)/2;
    	if(index <= mid) updateOneNode(root*2+1, index, value, start, mid);
    	else updateOneNode(root*2+2, index, value, mid+1, end);
    	sn[root].minVal = min(sn[root*2+1].minVal, sn[root*2+2].minVal);	 // 更新叶节点需要回溯更新其父结点的值
    }
    
    /* 我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。
    在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，
    那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。*/
    
    void SegTree::updateInterval(int root, const int &ustart, const int &uend, const int &value, int start, int end){
    	if(uend < start || end < ustart) return;
    	if(ustart <= start && uend >= end){
    		sn[root].addMark += value;
    		sn[root].minVal += value;
    		return;
    	}
    	pushDown(root);
    
    	int mid = (start+end)/2;
    	updateInterval(root*2+1, ustart, uend, value, start, mid);
    	updateInterval(root*2+2, ustart, uend, value, mid+1, end);
    	sn[root].minVal = min(sn[root*2+1].minVal, sn[root*2+2].minVal);	
    }
    
    // 显示结点
    
    void SegTree::display(int n){
    	for(int i = 0; i < n; i++){
    		cout << sn[i].minVal << " " << "[" << sn[i].left << "," << sn[i].right << "]" << endl;
    	}
    }

Main.cpp

/*功能： 频繁查询数组某一区间的最小值, 包括更新数组某一区间或者某一结点的值
    实现： 线段树，用一个数组来存取  具有n个结点的线段树需要2^lg(ceil(n)+1) -1 的空间, 是一个颗平衡查找树
    复杂度：预处理：创建线段树 O(n);; 查询更新时间复杂度O(lgN)， 需要额外的存储空间O(N)*/
    
    #include <iostream>
    #include "SegmentionTree.h"
    using namespace std;
    
    int main(){
    	int iArray[6] = {2, 5, 1, 4, 9, 3};
    	int t = ceil(log(6.0)/log(2.0))+1;
    	t = pow(2.0, t)-1;
    
    	SegTree st;
    	// 创建线段树
    	st.buildSegTree(0, iArray, 0 ,5);
    	st.display(t);   // 显示
    	cout << endl;
    
    	cout << st.queryMin(0, 4, 4, 0, 5) << endl; // 查找区间[4 4]的最小值
    	st.display(t);
    	cout << endl;
    
    	st.updateInterval(0, 0, 3, -8, 0, 5);     // 更新区间[0 3]加上-8
    	st.display(t);
    	cout << endl;
    	return 0;
    }

**参考文献：**

1： [ http://baike.baidu.com/link?url=3vo\_VqJ8bP8KF0BfPTFQwJhhv52Jo5oYPt0580DHIkr3-cKuaAD\_godLqJnUNFcX754JENLGE1ctKc63GXxCC\_][http_baike.baidu.com_link_url_3vo_VqJ8bP8KF0BfPTFQwJhhv52Jo5oYPt0580DHIkr3-cKuaAD_godLqJnUNFcX754JENLGE1ctKc63GXxCC]树状数组百度百科

2：[http://www.cppblog.com/Ylemzy/articles/98322.html][http_www.cppblog.com_Ylemzy_articles_98322.html]树状数组

3：[http://www.cnblogs.com/TenosDoIt/p/3453089.html][http_www.cnblogs.com_TenosDoIt_p_3453089.html]一步步理解线段树

4：[http://dongxicheng.org/structure/segment-tree/][http_dongxicheng.org_structure_segment-tree]数据结构之线段树-董的博客

[Center]: /images/20220805/7cbcd3537c4a4dd9847d81084c80ebe3.png
[Center 1]: /images/20220805/873d6c30ecc2499fa54046aa50d9d75b.png
[Center 2]: /images/20220805/0bd46cdbc6e94b32a8955b2d2ba90437.png
[http_www.cnblogs.com_TenosDoIt_p_3453089.html]: http://www.cnblogs.com/TenosDoIt/p/3453089.html
[http_baike.baidu.com_link_url_3vo_VqJ8bP8KF0BfPTFQwJhhv52Jo5oYPt0580DHIkr3-cKuaAD_godLqJnUNFcX754JENLGE1ctKc63GXxCC]: http://baike.baidu.com/link?url=3vo_VqJ8bP8KF0BfPTFQwJhhv52Jo5oYPt0580DHIkr3-cKuaAD_godLqJnUNFcX754JENLGE1ctKc63GXxCC_
[http_www.cppblog.com_Ylemzy_articles_98322.html]: http://www.cppblog.com/Ylemzy/articles/98322.html
[http_dongxicheng.org_structure_segment-tree]: http://dongxicheng.org/structure/segment-tree/