前言 珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构，因那道题题面（CF896C）关于珂朵莉而得名。 珂朵莉树适用于以下的情况：维护一个序列，有区间赋值操作，数据随机。下面是珂朵莉树板子题： 维护一个序列，需要支持以下操作1. 将 $[l,r]$ 区间所有数加上 $x$2. …

题面 题目链接 这是一道模板题。 给出一个  的零矩阵 ，你需要完成如下操作： 1 x y k：表示元素  自增 ； 2 a b c d：表示询问左上角为 ，右下角为  的子矩阵内所有数的和。 思路 一维树状数组的扩展 我们知道，一维树状数组可以求一段区间的和，将其扩展到二维，对于一个矩阵，每一层可以看做一个数，实际上是树状数组，每次求到每一层时求…

前言 问题 有 $n$ 个城市，$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城，假设他们都有足够的钱去购买车票，那么最多有多少人能到达 $T$ 城？ 思路 要使 $S$ 的人到达 $T$ ，首先要找到一条从 $S$ 到 $T$ 的通路（否则就到不了 $T$ 了）。显然，这条路最多只能通过其…

本文部分内容参考自 这篇博客 (写的很好 Orz ，建议大家也去看一下) 树链剖分是什么？用来做什么？ 有一棵树，求解以下问题： 1. 将从 x 到 y 的路径上的每个结点权值增加 z 2. 求从 x 到 y 的路径上的每个结点的权值和/权值最大值/权值最小值 对于问题 1，我们可以用树上差分来求解。 对于问题 2，我们可以用类似前缀和的方法，预处…

LCA问题有多种求法，例如倍增，Tarjan。 本篇博文讲解如何使用Tarjan求LCA。 如果你还不知道什么是LCA，没关系，本文会详细解释。 在本文中，因为我懒为方便理解，使用二叉树进行示范。 LCA是什么，能吃吗? LCA是树上最近公共祖先问题。 最近公共祖先就是树上有两个结点，找一个结点，是他们的公共祖先，并且离他们两个结点最近。 例如这是…