数据结构1：线段树(1) - Ericnth的小站

本文作者：Rolling_Code 本文分类：数据结构编程学习笔记浏览：1369
阅读时间：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 线段树功能实现

先来看一道例题：

Part2.1 建立线段树

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

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

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

那么~为了达到我们的目的，让我们开始我们的分治吧！（这里玩了一个不太被注意的梗）