type
status
date
slug
summary
tags
category
icon
password
线段树
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树可以在 的时间复杂度内实现单点修改、区间修改、区间查询等操作。
线段树的基本结构
为数组（假设下标从1开始）：
构造线段树如下图（采用堆式存储）：
上述数组 用来保存线段树，由于采用的是堆式存储，因此 的左右孩子结点分别为。不难发现上图有两种结点，银色结点括号表示该结点包含的数组 的区间， 的值表示 。且若区间两端点相等为则即值为绿色结点。
线段树的建立
由于树树递归定义的，因此其建立也是递归的：
线段树的区间查询
区间和：
区间修改：
为当前区间，index为要修改的数组的下标，为修改的最终值，为当前节点编号。
此时如果将 改成 ,则树变成(红色表示有修改的节点)：
实验
结果
- Author:Lamyh
- URL:https://blog.ccyh.xyz/article/tree
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!