Tag: 算法

3 篇文章

暴力数据结构 : 珂朵莉树 (ODT)
前言 珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构,因那道题题面(CF896C)关于珂朵莉而得名。 珂朵莉树适用于以下的情况:维护一个序列,有区间赋值操作,数据随机。下面是珂朵莉树板子题: 维护一个序列,需要支持以下操作1. 将 $[l,r]$ 区间所有数加上 $x$2. …
树链剖分算法解析
本文部分内容参考自 这篇博客 (写的很好 Orz ,建议大家也去看一下) 树链剖分是什么?用来做什么? 有一棵树,求解以下问题: 1. 将从 x 到 y 的路径上的每个结点权值增加 z 2. 求从 x 到 y 的路径上的每个结点的权值和/权值最大值/权值最小值 对于问题 1,我们可以用树上差分来求解。 对于问题 2,我们可以用类似前缀和的方法,预处…
详解使用 Tarjan 求 LCA 问题(图解)
LCA问题有多种求法,例如倍增,Tarjan。 本篇博文讲解如何使用Tarjan求LCA。 如果你还不知道什么是LCA,没关系,本文会详细解释。 在本文中,因为我懒为方便理解,使用二叉树进行示范。 LCA是什么,能吃吗? LCA是树上最近公共祖先问题。 最近公共祖先就是树上有两个结点,找一个结点,是他们的公共祖先,并且离他们两个结点最近。 例如这是…