线段树

发表于2077-03-02|更新于2025-03-06

|浏览量:

朴素线段树

基础

# 搭配倍增求解左右横跳问题
 # 同种元素只有区间第一个产生影响时，离线并删去上一个元素

优化dp

# 某位歌姬的故事加强版

树剖

典

树剖+差分的例题：# P9808 [POI 2022 ~2023R1] zbo，LCA,旧词

矩阵乘法优化

也可通过此实现更为简便的历史和
# 优化斐波那契数列求解

主席树

"半离线"的二维问题解决方案

# 利用 long long 的压空间方法

[[李超线段树]]

维护区间函数的第一方式

树套树

用于带修二维问题
# 经典dfs序转二维数点-接水果

[[线段树合并]]

单侧递归

一般单侧递归问题都可以换维扫描线 # 第一代图灵机

Trick

[[非重复元素配对问题]]
[[扫描线]] 问题的解决方案

区间中位数也可以用二分答案法解决，区间内仅有大小比较的找数问题，都可以用二分答案+01赋值法解决 # HEOI2016 排序

对于区间每时刻加，加后有上限的问题，可以将所有数分为“已经爆仓”和“没有爆仓”两部分，计算出每个点经过 $a_i$ 秒会变爆仓，设上次修改时间为 $x_i$ ，当前时间为 $T$ ，那么判定他爆仓的标准即为 $T-x_i \ge a_i$ ，变为一个二维数点问题 Little Pony and Lord Tirek

当寻找一个区间内部所有子区间中的最值时，可以考虑扫描线，观察子区间的存在合法方案的左端点的选取是否为一段区间，然后利用“子串=前缀的后缀”解决 [[P7907 Ynoi2005 rmscne 题解 | rmscne]]

文章作者: my9r

文章链接: http://example.com/2077/03/02/%E7%AE%97%E6%B3%95/%E7%BA%BF%E6%AE%B5%E6%A0%91/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 mygr main()！

相关推荐

当字符集较大时，可以考虑使用可持久化数组维护 ch 数组 AC自动机上判断某串的子串，考虑枚举前缀然后跳 $fail$ ，可以考虑建出 $fail$ 树，然后在走前缀的过程中用数据结构或连边建图表示出包含关系 # birthday

相关链接：[[矩阵树定理]]，[[欧拉回路]] 对于一个有向图，对于它的欧拉回路个数 $ec(G)$ ，有 $$ec(G)=root_{w}(G)\sum_{v\in V}(deg_v -1)!$$其中 $root_w(G)$ 表示以 $w$ 为根的 $G$ 的外向生成树有多少种注意BEST定理计算的是两点间若干条边有顺序的方案数，如果是 “某条边能够经过的次数” 则应当除去 $\frac{1}{w!}$ 将顺序消掉例题： # Counting Prefixes # C4

对于 DAG 上的节点，设 $f_{u}$ 表示以点 $u$ 为结束点的路径数，$g_u$ 表示从点 $u$ 开始的路径数，那么对于节点 $u$ 的所有出边，若存在一条边 $u \rightarrow v$ 使得 $2f_{v}>f_{u},2g_{v}>g_{u}$ ，那么我们则称 $u,v$ 是一条重边对于任意一条路径，其路径上的轻边数量一定是 $O(logn)$ 级别的，因为每走一次轻边路径数都会折半最常用的场景是在 [[后缀自动机]] 上快速的子串定位为什么不倍增跳呢？ #under_construction

本质：将一个 $k$ 维的立方体内的点压缩到序列上 $O(n^{1-\frac{1}{k}})$ 个不相交区间而这个序列就可以用正常方法去维护了例题：# P6783 Ynoi2008 rrusq

kmp的fail数组既可以指最长的前后缀长度，也可以指当前位的最长的前缀匹配，也可以指最长的循环节长度 #under_construction 字符串的所有前缀中，有多少个可以构成形如 “ABABA” 由 k 个A 组成的字符串通过不断跳fail的方式可以求出最短的前缀匹配，可以通过继承优化到 $O(n+m)$ 例子

考虑一个 $O(n)$ 预处理，$O(1)$ 查询的 RMQ 算法考虑将序列按照 $logn$ 进行分块，对于不在一个同块内部的询问，我们用ST表维护整块的信息，再额外维护块内的前后缀最大值即可对于在一个块内的查询，我们可以开一个单调栈维护一个前缀的单调下降序列，每一位使用一个整数状压单调栈内拥有的元素，查询 $l,r$ 时直接找 $r$ 对应的单调栈中第一个 $\ge l$ 的位置即可

数据加载中