线段树知识整理

2024-04-08 11:40| 来源: 网络整理| 查看: 265

目录一：什么是线段树？二：线段树的基本结构及空间复杂度线段树的空间复杂度：三：线段树的常用操作线段树的建树常用函数：1.pushup() 更新操作（子->父）2.pushdown() 更新操作（父->子）3.build() 建树操作3.modify() 修改操作4.query() 查询操作

一：什么是线段树？

线段树的概念：线段树是算法竞赛中常用的用来维护区间信息的数据结构。

线段树可以在 O ( l o g N ) O(logN) O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

二：线段树的基本结构及空间复杂度

线段树的结构（文字解释）：

线段树将每个长度不为 1 1 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，线段树的操作通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。线段树为满二叉树，用一维数组存整颗树

线段树的结构（下图所示）：算法竞赛进阶指南

线段树的空间复杂度：

对于线段树最少要开4倍空间的解释：

若最后一层节点都满，则该层为最后一层，有 N N N个节点，则其上面节点数为 N / 2 + N / 4 + N / 8 + . . . . . . + 1 N/2 + N/4 + N/8 + ...... + 1 N/2+N/4+N/8+......+1，此时所有节点数为 N + N / 2 + N / 4 + N / 8 + . . . . . . + 1 N + N/2 + N/4 + N/8 + ...... + 1 N+N/2+N/4+N/8+......+1 和为 2 N − 1 2N - 1 2N−1若最后一层不满，即、上两图所示的情况，则倒数第二层为 N 个节点 N个节点 N个节点，除倒数第一层以外的所有层节点和为 2 N − 1 2N - 1 2N−1，最后一层为 2 N 2N 2N 个节点，即、总节点为 4 N − 1 4N - 1 4N−1 ，所以保险起见，线段树一律开 4 N 4N 4N 空间三：线段树的常用操作线段树的建树

线段树的节点关系：

若该节点为 x其父节点为 x / 2等效于x >> 1左儿子为 x * 2等效于x 子）

**俗称：**懒标记（支持区间修改）以区间加为例：含义：给当前区间的所有儿子加上 add(懒标记) 如图：在这里插入图片描述

3.build() 建树操作

建立线段树：

从根节点开始，一层层递归到叶子节点每递归一层调用一次 p u s h u p ( ) ( 由子节点更新父节点 ) pushup()(由子节点更新父节点) pushup()(由子节点更新父节点)

一般模板为：

函数参数为：当前区间的编号u 当前区间的左端点l 当前区间的右端点r void build(int u, int l, int r) { tr[u] = {l, r}; if(l == r) return; int mid = l + r >> 1; build(u

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章