线段树详解以及C++实现代码

 更新时间:2021年7月19日 00:00  
线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中,这篇文章主要给大家介绍了关于线段树以及C++实现的相关资料,需要的朋友可以参考下

应用场景

假设有这样的问题:有n个数,m次操作,操作分为:修改某一个数或者查询一段区间的值

分析下,如果针对数组元素的修改可以是O(1)完成,求某个区间值需要O(n)才可以完成,如果m和n都很大的情况,这个复杂度就很难接受了。

我们之前学过的前缀和算法可以解决区间求和的问题,并且时间复杂度是O(1),但如果涉及到修改操作,前缀和数组都需要重新计算,时间复杂度也是O(n)

有没有什么办法可以兼顾以上两种操作,并且可以将时间复杂度降低?

这就是我们要学习的线段树!把修改和查询的时间复杂度都降到O(logn)!!!

算法思想

先来看下线段树长什么样:

有以下数组(为方便计算,数组下标从1开始)

我们把它转换成线段树,是长这样的:

1)叶子结点(绿色)存的都是原数组元素的值

2)每个父结点是它的两个子节点的值的和

3)每个父结点记录它表示区间的范围,如上图的“1-2”表示1到2的区间

下面我们来看看线段树是如何降低操作复杂度的!

查询操作

例如我们需要查询2-5区间的和

使用递归的思想:

2~5的和

=2~3的和+4~5的和

=3+5+4~5的和

=3+5+11

=19

总之,就是沿着线段树的划分把区间分开,再加到一块就行啦!

修改操作

例如,我们要把结点2的值由3->5,线段树需要沿着红色部分一个一个改,直到根结点:

不管是修改操作还是查询操作,时间复杂度都是O(logn)

下一步我们来看怎么实现线段树!

算法实现

首先我们需要将原始数组建立成一颗线段树,然后在树的基础上提供查询和修改的操作。

建树

观察上图,我们发现线段树是一棵近似完全二叉树,利用完全二叉树的性质,我们就可以直接用一个数组来存它。

就像上图一样把各个节点标上号,如果根节点编号是n,那它的左子树编号是2n,右子树的编号是2n+1

所以说,知道了根节点的编号,我们就可以快速有效的找到左右子树的根节点

void build(int root,int start,int end){
    if(start == end){
        tree[root] = num[start];
        return;
    }
    int leftroot = root * 2;//左结点
    int rightroot = root * 2 + 1;//右结点
    int mid = (start+end)/2;
    build(leftroot,start,mid);//递归计算左结点
    build(rightroot,mid+1,end);//递归计算右结点
    tree[root] = tree[leftroot] + tree[rightroot];//根结点值=左根+右根
}

查询

int query(int root,int start,int end,int l,int r){
    if(l<=start && r>= end){
        return tree[root];
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    int sum = 0;
    if(l<=mid){
        sum += query(leftroot,start,mid,l,r);
    }
    if(r>mid){
        sum += query(rightroot,mid+1,end,l,r);
    }
    return sum;
}

修改

/**
* 修改[l,r]区间里的数,都加上k值
* @param root
* @param start
* @param end
* @param l
* @param r
* @param k
*/
void update(int root,int start,int end,int l,int r,int k){
    if(start == end){
        tree[root] += k;
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    if(l<=mid){
        update(leftroot,start,mid,l,r,k);
    }
    if(r>mid){
        update(rightroot,mid+1,end,l,r,k);
    }
    tree[root] = tree[leftroot] + tree[rightroot];
}

!!!:考虑下按区间修改元素值的复杂度?

注意事项:

1)我们在实现线段树时,实际存储肯定大于原始数组,我们一般让tree数组的长度为原始数据长度的3-4倍。

2)本文只是为了让大家学习线段树的实现原理,实际中我们可以将原始数组的start,end使用结构体存储,这样更简洁

总结

到此这篇关于线段树详解以及C++实现的文章就介绍到这了,更多相关C++实现线段树内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!

相关文章

  • 深入学习C++智能指针之shared_ptr与右值引用的方法

    智能指针的核心实现技术是引用计数,每使用它一次,内部引用计数加1,每析构一次内部的引用计数减1,减为0时,删除所指向的堆内存,今天通过本文给大家分享C++智能指针之shared_ptr与右值引用的方法,需要的朋友跟随小编一起看看吧...2021-07-13
  • C++字符串的处理详解

    这篇文章主要介绍了C++ string字符串类,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-08-13
  • 浅谈C++类型转换几种情况

    本文主要介绍了几种C++类型转换,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-08-05
  • C++实现LeetCode(37.求解数独)

    这篇文章主要介绍了C++实现LeetCode(37.求解数独),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • C++ const关键字分析详解

    C++中的const关键字的用法非常灵活,而使用const将大大改善程序的健壮性。这篇文章主要介绍了C/C++ 中const关键字的用法,需要的朋友可以参考下...2021-08-29
  • C/C++中虚基类详解及其作用介绍

    这篇文章主要介绍了C/C++中虚基类的详解及其作用介绍,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
  • C++变量引用的概念介绍

    这篇文章主要介绍了C++变量引用的概念介绍,简单提到了与指针概念的不同,通过代码场景分析给大家介绍的非常详细,需要的朋友可以参考下...2021-08-04
  • 一文搞懂C++中的四种强制类型转换

    很多朋友向小编了解C语言中怎么进行强制类型转换呢?在这小编告诉大家强制类型转换可以分为两种,一种是隐式类型转换一种是显示类型转换,下面通过示例代码给大家介绍下,需要的朋友参考下吧...2021-07-07
  • C++中char[]能修改char*却不行

    本文主要介绍了C++中char[]能修改char*却不行,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-13
  • C++:构造函数,析构函数详解

    今天小编就为大家分享一篇关于C++构造函数和析构函数的文章,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧...2021-09-01
  • 一篇文章带你了解C++智能指针详解

    这篇文章主要介绍了c++ 智能指针基础的相关资料,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下,希望能给你带来帮助...2021-08-13
  • C++实现矩阵对称正交化的示例代码

    这篇文章主要介绍了C++实现矩阵对称正交化,分为python代码和C++的eigen库实现代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-15
  • C++ 约瑟夫环问题案例详解

    这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
  • 结构体对齐的规则详解及C++代码验证

    在c语言的结构体里面一般会按照某种规则去进行字节对齐。本文就来介绍一下如何实现,具有一定的参考价值,感兴趣的可以了解下...2021-08-17
  • 线段树详解以及C++实现代码

    线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中,这篇文章主要给大家介绍了关于线段树以及C++实现的相关资料,需要的朋友可以参考下...2021-07-19
  • C++实现LeetCode(51.N皇后问题)

    这篇文章主要介绍了C++实现LeetCode(51.N皇后问题),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • 从c++标准库指针萃取器谈一下traits技法(推荐)

    本篇文章基于gcc中标准库源码剖析一下标准库中的模板类pointer_traits,并且以此为例理解一下traits技法,对c++ traits技法源码分析感兴趣的朋友跟随小编一起看看吧...2021-07-14
  • C++手写内存池的案例详解

    这篇文章主要介绍了C++手写内存池的案例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-08-08
  • C/C++实现快速排序(两种方式)图文详解

    这篇文章主要介绍了C/C++实现快速排序的方法,这几天在找工作,被问到快速排序,结果想不出来快速排序怎么弄的;回来搜索了一下,现在记录下来,方便以后查看...2021-08-13
  • C++ 实现桶排序的示例代码

    桶排序或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子,本文详细的介绍了如何实现,感兴趣的可以了解一下...2021-07-12