线段树及应用

1. 线段树基础

(1) 什么是线段树

线段树是一种数据结构，利用分治思想处理对一段序列进行大量区间操作（如区间修改、区间查询）的问题。其基本特性如下：

• 定义：线段树是一个二叉树结构，其中每个叶子结点表示原序列的一个元素，而每个内部结点表示一个区间，存储着该区间的某种统计信息（例如区间和、区间最大值、最小值等）。
• 时间复杂度：线段树可以在 $O(n \log n)$ 的时间复杂度内完成区间修改和区间查询操作。

线段树的叶节点即为原序列，而每个内部节点除了左右儿子外，还保存着其分管的某段区间信息。

(2) 线段树的拆分原理

• 将区间 $[1, n]$ 分解成若干特定的子区间。
• 将每个区间 $[L, R]$ 再次分解为少量特定的子区间，直到达到最小单位。

通过递归的方式，线段树将一个大的区间划分为小的子区间，每个子区间对应树中的一个节点。

(3) 相关算法对比

(4) 线段树的使用前提

使用线段树的问题必须符合区间加法，即通过合并区间的解一定能得到问题的解。以下是可以使用线段树处理的几类问题：

• 数字和问题：区间总和 = 左区间总和 + 右区间总和。
• 最大公约数（GCD）问题：区间总 GCD = GCD(左区间 GCD, 右区间 GCD)。
• 最大值问题：区间最大值 = max(左区间最大值，右区间最大值)。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com