【算法】线段树详解-程序员宅基地

前言

这是一篇蒟蒻的博客，可能有许多错误或不详细的地方，欢迎大佬们指出。
这篇文章主要参考了这篇博文：http://blog.csdn.net/zearot/article/details/48299459

什么是线段树

线段树，是一种 二叉搜索树 。它将一段区间划分为若干 单位区间 ，每一个节点都储存着一个区间。它 功能强大 ，支持区间求和，区间最大值，区间修改，单点修改等操作。
线段树的思想和分治思想很相像。
线段树的每一个节点都储存着一段区间 $[L .. R]$ 的信息，其中 叶子节点 $L = R$ 。它的大致思想是：将一段大区间平均地划分成 $2$ 个小区间，每一个小区间都再平均分成 $2$ 个更小区间……以此类推，直到每一个区间的 $L$ 等于 $R$ （这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。
这样一来，每一次单点修改、单点查询的时间复杂度都只为 $O(\log_2n)$ 。
但是，可以用线段树维护的问题必须满足 区间加法 ，否则是不可能将大问题划分成子问题来解决的。

什么是区间加法

一个问题满足区间加法，仅当对于区间 $[L, R]$ 的问题的答案可以由 $[L, M]$ 和 $[M + 1, R]$ 的答案合并得到。
经典的区间加法问题有：

区间求和（ $\sum_{i=L}^Ra_i=\sum_{i=L}^Ma_i+\sum_{i=M+1}^Ra_i\quad ,L\leq M<R$ ）；
区间最大值（ $\max_{i=L}^Ra_i=\max(\max_{i=L}^Ma_i,\max_{i=M+1}^Ra_i)\quad ,L\leq M<R$ ）。

不满足区间加法的问题有：

区间的众数；
区间的最长不下降子序列。

线段树的原理及实现

注意：如果我没有特别申明的话，这里的询问全部都是区间求和
线段树主要是把一段大区间 平均地划分 成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在 $\log$ 级别（因为这棵线段树是平衡的）。也就是说，一个 $[L, R]$ 的区间会被划分成 $\left[L,\left\lfloor\frac{L+R}{2}\right\rfloor\right]$ 和 $\left[\left\lfloor\frac{L+R}{2}\right\rfloor+1,R\right]$ 这两个小区间进行维护，直到 $L = R$ 。
下图就是一棵 $[1, 10]$ 的线段树的分解过程（相同颜色的节点在同一层）

可以发现，这棵线段树的最大深度不超过 $\lfloor\log_2(n-1)\rfloor+2$ 。

储存方式

通常用的都是 堆式储存法 ，即编号为 $k$ 的节点的左儿子编号为 $2 k$ ，右儿子编号为 $2 k + 1$ ，父节点编号为 $\left\lfloor\frac{k}{2}\right\rfloor$ ，用 位运算 优化一下，以上的节点编号就变成了 k<<1 , k<<1|1 , k>>1 。其它储存方式请见 指针储存和动态开点 。
通常，每一个线段树上的节点储存的都是这几个变量：区间左边界，区间右边界，区间的答案（这里为区间元素之和）
注意：线段树的大小其实是 5n 左右的。
下面是线段树的定义：

struct node
{
   
    
	int l/*区间左边界*/,r/*区间右边界*/,sum/*区间元素之和*/,lazy/*懒惰标记，此处默认是区间加，下文会提到*/;
	node(){
   
    l=r=sum=lazy=0;}//给每一个元素赋初值
}a[N];//N为总节点数
inline void update(int k)//更新节点k的sum
{
   
    
	a[k].sum=a[k*2].sum+a[k*2+1].sum+a[k].lazy;
	//很显然，一段区间的元素和等于它的子区间的元素和
	//如果有懒惰标记的话要相应地改变（记得加上懒惰标记的值！！！）感谢duck_master的指正
}

初始化

常见的做法是遍历整棵线段树，给每一个节点赋值，注意要递归到线段树的叶节点才结束。

void build(int k/*当前节点的编号*/,int l/*当前区间的左边界*/,int r/*当前区间的右边界*/)
{
   
    
	a[k].l=l,a[k].r=r;
	if(l==r)//递归到叶节点
	{
   
    
		a[k].sum=number[l];//其中number数组为给定的初值
		return;
	}
	int mid=(l+r)/2;//计算左右子节点的边界
	build(k*2,l,mid);//递归到左儿子
	build(k*2+1,mid+1,r);//递归到右儿子
	update

本文链接：https://blog.csdn.net/huangzihaoal/article/details/81813454

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

leetcode 172. 阶乘后的零-程序员宅基地

文章浏览阅读63次。题目给定一个整数 n，返回 n! 结果尾数中零的数量。解题思路每个0都是由2 * 5得来的，相当于要求n!分解成质因子后2 * 5的数目，由于n中2的数目肯定是要大于5的数目，所以我们只需要求出n!中5的数目。C++代码class Solution {public: int trailingZeroes(int n) { ...

Day15-【Java SE进阶】IO流（一）：File、IO流概述、File文件对象的创建、字节输入输出流FileInputStream FileoutputStream、释放资源。_outputstream释放-程序员宅基地

文章浏览阅读992次，点赞27次，收藏15次。UTF-8是Unicode字符集的一种编码方案，采取可变长编码方案，共分四个长度区:1个字节，2个字节，3个字节，4个字节。文件字节输入流：每次读取多个字节到字节数组中去，返回读取的字节数量，读取完毕会返回-1。注意1:字符编码时使用的字符集，和解码时使用的字符集必须一致，否则会出现乱码。定义一个与文件一样大的字节数组，一次性读取完文件的全部字节。UTF-8字符集:汉字占3个字节，英文、数字占1个字节。GBK字符集:汉字占2个字节，英文、数字占1个字节。GBK规定:汉字的第一个字节的第一位必须是1。_outputstream释放

jeecgboot重新登录_jeecg 登录自动退出-程序员宅基地

文章浏览阅读1.8k次，点赞3次，收藏3次。解决jeecgboot每次登录进去都会弹出请重新登录问题，在utils文件下找到request.js文件注释这段代码即可_jeecg 登录自动退出

数据中心供配电系统负荷计算实例分析-程序员宅基地

文章浏览阅读3.4k次。我国目前普遍采用需要系数法和二项式系数法确定用电设备的负荷，其中需要系数法是国际上普遍采用的确定计算负荷的方法，最为简便;而二项式系数法在确定设备台数较少且各台设备容量差..._数据中心用电负荷统计变压器

HTML5期末大作业：网页制作代码网站设计——人电影网站(5页) HTML+CSS+JavaScript 学生DW网页设计作业成品 dreamweaver作业静态HTML网页设计模板_网页设计成品百度网盘-程序员宅基地

文章浏览阅读7k次，点赞4次，收藏46次。HTML5期末大作业：网页制作代码网站设计——人电影网站(5页) HTML+CSS+JavaScript 学生DW网页设计作业成品 dreamweaver作业静态HTML网页设计模板常见网页设计作业题材有个人、美食、公司、学校、旅游、电商、宠物、电器、茶叶、家居、酒店、舞蹈、动漫、明星、服装、体育、化妆品、物流、环保、书籍、婚纱、军事、游戏、节日、戒烟、电影、摄影、文化、家乡、鲜花、礼品、汽车、其他等网页设计题目, A+水平作业_网页设计成品百度网盘

【Jailhouse 文章】Look Mum, no VM Exits_jailhouse sr-iov-程序员宅基地

文章浏览阅读392次。jailhouse 文章翻译，Look Mum, no VM Exits!_jailhouse sr-iov

随便推点

chatgpt赋能python：Python怎么删除文件中的某一行_python 删除文件特定几行-程序员宅基地

文章浏览阅读751次。本文由chatgpt生成，文章没有在chatgpt生成的基础上进行任何的修改。以上只是chatgpt能力的冰山一角。作为通用的Aigc大模型，只是展现它原本的实力。对于颠覆工作方式的ChatGPT，应该选择拥抱而不是抗拒，未来属于“会用”AI的人。AI职场汇报智能办公文案写作效率提升教程专注于AI+职场+办公方向。下图是课程的整体大纲下图是AI职场汇报智能办公文案写作效率提升教程中用到的ai工具。_python 删除文件特定几行

Java过滤特殊字符的正则表达式_java正则表达式过滤特殊字符-程序员宅基地

文章浏览阅读2.1k次。【代码】Java过滤特殊字符的正则表达式。_java正则表达式过滤特殊字符

CSS中设置背景的7个属性及简写background注意点_background设置背景图片-程序员宅基地

文章浏览阅读5.7k次，点赞4次，收藏17次。css中背景的设置至关重要，也是一个难点，因为属性众多，对应的属性值也比较多，这里详细的列举了背景相关的7个属性及对应的属性值，并附上演示代码，后期要用的话，可以随时查看，那我们坐稳开车了······1: background-color 设置背景颜色2:background-image来设置背景图片- 语法：background-image:url(相对路径);-可以同时为一个元素指定背景颜色和背景图片，这样背景颜色将会作为背景图片的底色，一般情况下设置背景..._background设置背景图片

Win10 安装系统跳过创建用户，直接启用 Administrator_windows10msoobe进程-程序员宅基地

文章浏览阅读2.6k次，点赞2次，收藏8次。Win10 安装系统跳过创建用户，直接启用 Administrator_windows10msoobe进程

PyCharm2021安装教程-程序员宅基地

文章浏览阅读10w+次，点赞653次，收藏3k次。Windows安装pycharm教程新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入下载安装PyCharm1、进入官网PyCharm的下载地址：http://www.jetbrains.com/pycharm/downl_pycharm2021

《跨境电商——速卖通搜索排名规则解析与SEO技术》一一1.1　初识速卖通的搜索引擎...-程序员宅基地

文章浏览阅读835次。本节书摘来自异步社区出版社《跨境电商——速卖通搜索排名规则解析与SEO技术》一书中的第1章，第1.1节，作者：冯晓宁，更多章节内容可以访问云栖社区“异步社区”公众号查看。1.1　初识速卖通的搜索引擎1.1.1　初识速卖通搜索作为速卖通卖家都应该知道，速卖通经常被视为“国际版的淘宝”。那么请想一下，普通消费者在淘宝网上购买商品的时候，他的行为应该..._跨境电商速卖通搜索排名规则解析与seo技术 pdf