数据结构1:线段树(1)

Hello, 欢迎登录 or 注册!

/ 0评 / 0

本文作者:  本文分类:数据结构 编程学习笔记  浏览:412
阅读时间:679字, 约1分钟

Part 0 前言

2020.8.1留言:介于Rolling_Code今天终于把一道调了3天的包含线段树内容的题目调了出来,就先顺便复习一下线段树。

2020.8.2留言:预计在2020.8.7前发布(内容有点多)。

Part 1 线段树简介

线段树(Segment Tree,有时候被我说成ST树),是一种将区间做多级拆分的数据结构。每个节点维护特定区间上的目标函数值。采用分治的思想。

一棵标准的线段树大概长这样:

线段树长啥样?长这样

那么,线段树有哪些特性呢?

1.看得出来,线段树是一颗二叉树

2.线段树一般用于求区间动态的RMQ(Range Min/Max Query 区间最值问询)和RSQ(Range Sum Query 区间求和一类的问询)问题。(其实其他结构上比如树也是可以,但我还没有学到那么深。)

3.线段树的特殊情况主要有以下两个:BIT(Binary Indexed Tree 二进制索引树/树状数组),和ST表(Sparse Table 稀疏表),这两个数据结构以后会提到,先留着。

PS:当然还有主席树啦一类的东西,没学过,不清楚,不知道。

这么多,全是线段树的“亲戚”

Part 2 线段树功能实现

先来看一道例题:

https://www.luogu.com.cn/problem/P3372 线段树最基础的模板。

Part2.1 建立线段树

我们首先需要写一个函数,暂且称它为BuildST(即建立线段树的英文简写)。

那么我们需要实现什么功能呢?

首先,回顾一下。线段树维护的是一个区间内的属性,在本题中就是区间和。

那么~为了达到我们的目的,让我们开始我们的分治吧!(这里玩了一个不太被注意的梗)

关于作者

本作品采用 知识共享署名-非商业性使用 3.0 (CC BY-NC 3.0) 许可协议进行许可。

发表评论

您的电子邮箱地址不会被公开。