Ericnth的小站

  • 你可能还想了解...
  • 首页
  • 编程学习笔记
  • 系统与软件
  • 摄影
  • 随笔
  • 论坛
  • 公告

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

  • Rolling_Code
  • 2020-08-07
  • 0

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(即建立线段树的英文简写)。

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

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

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

你可能还想了解...

  • A Bayesian Analysis of High School Acceptance Rates in Shanghai
  • HYRing项目代码解读
  • 算法讲解之贪心算法(转)
  • 算法讲解之回溯法(转)
  • C/C++ IDE推荐
© 2023 Ericnth的小站
Theme by Wing
沪ICP备2020025694号 沪公网安备31011202012861号
  • {{ item.name }}
  • {{ item.name }}