首页 > 数据结构 > 树形结构 > 线段树入门-求给定区间的和
2014
06-23

线段树入门-求给定区间的和

考虑以下问题来理解线段树。有一个[0...n-1]的数组,现有一些的操作:
1) 查询:求 下标从 l 到 r ( 0 <= l <= r <= n-1) 区间内所有元素的和
2) 更新:更新数组中任一个元素的值

最直接的解法方法是执行一个循环,求得l到r的总和。更新的话就很简单了,直接操作。时间复杂度分别为O(n)和O(1)。

另一中解法方法是:创建另一个数组sumarr[], 存储从第一个元素到第i个的总和。例如sumarr[3]表示[0...3]区间内元素的总和。现在两个操作的时间复杂度为分别为:O(1)和O(n)。如果查询的次数远多于更新的次数,可以用这种方法。

如果查询和更新的操作数量是相等的呢?这时可以用线段树来解决,两个操作都在O(logN)时间内。

线段树的表示
线段树(Segment Tree)是一种二叉搜索树,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
1. 页节点即输入数组的所有元素
2. 内部节点表示的是部分合并的叶节点.  (合并的方式需要根据不同的问题,对于这个问题,合并就是求和.)

segment-tree1

如何构造线段树对于给定的数组?
我们从arr[0 ...n-1]开始,每次我们将当前数组段分为两半(如果长度大于1), 然后递归调用者两半, 并存储这两个子区间的总和。
可以发现,树将是满二叉树,因为我们在每一层,都是把区间分为两个部分。由于树总的叶子节点为n,因此有 n – 1个 内部节点。因此节点总数为2*n – 1,树的高度为 log(n).由于这是一个满二叉树,而每一个节点存储的元素都是单一的值。因此完全可以用数组可以模拟二叉树,而不是构成传统的二叉树。
对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

查询操作
递归的进行查询,流程如下

int getSum(node, l, r)
{
   if(如果节点node表示的区间 属于 l and r)
        return value in node
   else if (如果节点node表示的区间  完全不输于属于 l and r)
        return 0
   else
   return getSum(node's left child, l, r) +
           getSum(node's right child, l, r)
}

更新操作

和查询操作类似,也是递归的完成。不是直接更新某个值,而是给出 diff 表示某个值需要增加多少,可以为负。然后递归的增加到子区间内。

C语言实现
下面的代码实现了更新和查询操作,使用数组模拟树。

#include <stdio.h>
#include <math.h>

//取中位数
int getMid(int s, int e) {  return s + (e -s)/2;  }

/*
    st    --> 线段树的指针
    index --> 当前节点在线段树中的下标. 初始为 0,因为根节点的下标是0
    ss & se  --> 当前节点st[index]做表示的区间 [ss .... se]
    qs & qe  --> 要查询的区间 起始坐标 */
int getSumRecall(int *st, int ss, int se, int qs, int qe, int index)
{
    // 如果查询的区间 属于当前节点表示的区间
    if (qs <= ss && qe >= se)
        return st[index];

    // 完全不属于
    if (se < qs || ss > qe)
        return 0;

    // 部分属于
    int mid = getMid(ss, se);
    return getSumRecall(st, ss, mid, qs, qe, 2*index+1) +
           getSumRecall(st, mid+1, se, qs, qe, 2*index+2);
}

/*
    st, index, ss 和 se 和函数getSumRecall 相同
    i    --> 要更新的元素下标.(原始数组中的下标)
   diff --> 需要增加的值。 所有包含i的区间都会更新  */
void updateValueRecall(int *st, int ss, int se, int i, int diff, int index)
{
    if (i < ss || i > se)
        return;

    st[index] = st[index] + diff;
    if (se != ss)
    {
        int mid = getMid(ss, se);
        updateValueRecall(st, ss, mid, i, diff, 2*index + 1);
        updateValueRecall(st, mid+1, se, i, diff, 2*index + 2);
    }
}

// 更新i为新的值new_val,主要是调用updateValueRecall
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
    if (i < 0 || i > n-1)
    {
        printf("Invalid Input");
        return;
    }

    int diff = new_val - arr[i];
    arr[i] = new_val;
    // 更新线段树
    updateValueRecall(st, 0, n-1, i, diff, 0);
}

//查询,主要是调用getSumRecall
int getSum(int *st, int n, int qs, int qe)
{
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        printf("Invalid Input");
        return -1;
    }

    return getSumRecall(st, 0, n-1, qs, qe, 0);
}

// 递归来构建区间为 [ss..se] 的线段树 (st[si])
// si 当前节点在线段树中的下标
// return: 当前区间的总和
int constructSTRecall(int arr[], int ss, int se, int *st, int si)
{
    // 如果只有一个元素,说明到达了叶子节点
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }

    // 递归的构建左右区间(子线段树)
    int mid = getMid(ss, se);
    st[si] =  constructSTRecall(arr, ss, mid, st, si*2+1) +
    		constructSTRecall(arr, mid+1, se, st, si*2+2);
    return st[si];
}

/*构建线段树,主要是调用递归函数 constructSTRecall 完成 */
int *constructST(int arr[], int n)
{
    // 分配内存
    int *st = new int[n * 2];

    // 构建线段树
    constructSTRecall(arr, 0, n-1, st, 0);
    return st;
}

//测试
int main()
{
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr)/sizeof(arr[0]);

    // 构建线段树
    int *st = constructST(arr, n);

    printf("Sum of values in given range = %d\n", getSum(st, n, 1, 3));

    // 更新:  arr[1] = 10 and 更新相应的区间
    updateValue(arr, st, n, 1, 10);

    printf("Updated sum of values in given range = %d\n",
                                                  getSum(st, n, 1, 3));

    return 0;
}

输出:

Sum of values in given range = 15
Updated sum of values in given range = 22

时间复杂度分析

树的构建复杂度为 O(n),因为树的节点总数位 2n-1个,每个节点只会被计算一次。

查询和更新的操作都为O(Logn), 由树的高度决定。

参考:http://www.cse.iitk.ac.in/users/aca/lop12/slides/06.pdf


  1. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  3. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  4. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  5. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }