分类: 隐藏

7 篇文章

可持久化线段树
可持久化线段树 又称“主席树”,据说是其发明人黄嘉泰(HJT)拼音首字母同某位国家主席而得名。 但个人感觉“可持久化线段树”的英文名 "Persistent Segment Tree" 中的 "Persistent" 和“主席”的英文 "President" 也比较相似? 可持久化线段树在每次修改后都会保存一份历史版本
扫描线
例题 洛谷 P5490:【模板】扫描线 Description Solution Code USACO 5.5:矩形周长 Picture Description Solution Code
线段树合并
字面意思,就是合并几棵线段树。可以有两种合并方式: DFS 将每个点依次合并起来。 先将叶子节点并起来,然后依次 pushup。 存放新树也有两种方式: 新开一个树。 覆盖在原有的树上。 总之最后要把整棵树都遍历一遍,所以时间复杂度为 $O(n \log n)$。 例题 洛谷 P4556:雨天的尾巴 /【模板】线段树合并 Description 村…
动态开点 & 权值线段树
动态开点线段树 一般的线段树,空间复杂度大约要开到 $O(n \times 4)$ ,对于数据范围较大,而询问较少的情况下(如权值线段树)可能不需要开这么多。所以我们需要动态分配内存来应付这种情况。此时我们可以记 segt[k].l 为此段的左子节点,segt[k].r 为此段的右子节点。 看以下一段代码: inline void Insert(i…
拆位线段树
有时我们会遇到一些像异或这样不支持叠加的操作,这时不能打 lazytag,就需要进行二进制拆位。 具体来说,就是把该数的每一位拆分出来,形成一棵单独的二叉树。举个例子,对于 $1 \leq n \leq 10^6$ 这样的范围,就可以拆成 $20$ 位,维护 $20$ 棵线段树。 例题 CF242E: XOR on Segment Descript…
树状数组
树状数组相比线段树代码简洁,在进行单点修改,区间查询的时候也比较方便。 图中的树状数组 $t$ 存放了 $8$ 个数,举个例子: $$ \begin{aligned} t_2&=t_1+a_2=a_1+a_2\\ t_4&=t_2+a_3=a_1+a_2+a_3\\ t_6&=t_5+a_6=…
基础线段树
本篇为线段树的基础操作(模板,Tag 的运用)。 当然也存在一些码量极大的毒瘤题 例题 洛谷 P3372:【模板】线段树 1 Description 已知一个长度为 $n ~ (1 \leq n \leq 10^5)$ 的序列 $a$,有 $m ~ (1 \leq m \leq 10^5)$ 个操作,分为以下两种: 1 l r k:将区间 $[l,…