学习线段树，你需要先完成树、数组、分治思想、递归的学习（可以说是学习成本极低了） 引入 线段树是一个用途极为广泛的数据结构，在提高组及以上的比赛中经常看到它的身影。 现在我有一个问题，给一个长度为 $n$ 的序列，我需要将序列中一个范围内的每一个数进行一次运算，例如加上 $x$ ，也就是区间修改，然后查询修改后一个区间范围内所有值的和或者其他量，也…

主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树 可持久化线段树简介 基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树 总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。 优点解释 每次插入操作最多创建的节点数都为$\log n$…

表达式类型 表达式类型定义示例 前缀表达式（波兰式）运算符位于操作数之前$-*+3456$中缀表达式操作符以中缀的形式处于操作数中间$(3+4)*5-6$后缀表达式（逆波兰式）运算符位于操作数之后$34+5*6-$ 对于前缀表达式和后缀表达式来说，表达式是不需要用括号确定优先级的。 表达式原理 网上的很多教程都没有同时提到这三种表达式转化与表达式树…

左偏树简介 左偏树是一种可并堆，也叫左偏堆、左倾堆、左氏堆，是一种树，具有堆的性质，可以实现快速合并。左偏树不是二叉搜索树，不是平衡树，因为它不满足中序有序性，无法进行二分搜索，因此不可以快速查找或者删除特定值的节点。 左偏树的性质 堆序性 节点的值大于或者等于（或小于等于）其左右子节点的值。对最大堆，父节点大，子节点小，每个结点的值都大于或者等于…

线性动态规划规划简介 在所有动态规划中，线性动态规划的难度最低，同时线性动态规划也是所有动态规划的基础。 顾名思义，线性动态规划就是说动态规划的过程在“一条线”上进行，状态转移只有一个方向。最常见的线性$\rm{DP}$有子集和问题，$\rm{LIS}$问题，$\rm{LCS}$问题，字段和问题等。其实，线性$\rm{DP}$的用处不只如此，很大一…

前言 先前博客中写过“线段树”这一篇文章，而这一次是一种具有新的含义的线段树：权值线段树。 权值线段树简介 定义 权值线段树和普通线段树的形态类似，但是含义不同。普通线段树的节点通常存储该区间的最值或者和值，其节点范围是一个区间：权值线段树的节点存储该值域内的元素个数，其节点范围是一个值域。 基本结构 如图，对于每个节点的位置表示的是元素的值，然后…

二叉堆简介 二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。 二叉堆的结构 从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。由堆性质，树根存的是最大值。对于堆的每个子树，它同样也是一个…

前置知识 在此之前，你需要学习双端队列 简介 单调队列是用于解决滑动窗口类问题的数据结构，即在一个长度为 $n$ 的序列中求连续 $k$ 个数字中的最值问题，单调队列时间复杂度为 $O(n)$ ，这比「ST表」与「线段树」算法更优化。 更广泛地，在以下两种情况时，可以考虑使用单调队列优化。 状态转移方程形如 $dp_i=\min_{0\le j \…

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。 Treap Treap简介 特点与作用 Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不…

树链剖分简介 链剖分 指对树的边进行划分的一种操作，目的是减少在链上修改、查询等操作的复杂度。链剖分分三类：轻重链剖分、虚实链剖分和长链剖分。 树链剖分思想 通过轻重链剖分将树分为多条链，保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分，节点到重儿子，也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间，把所有重链首尾相接组…