莫队算法学习笔记

2016-12-23
先声明一下，所有代码区间均为左闭右开 [ l , r ) [l, r) [ l , r ) ，点的下标均从 0 0 0 开始。 概述 莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。 形式 ......
Read More

虚树学习笔记

2016-12-20
概述 在 OI 比赛中，有这样一类题目：给定一棵树，另有多次询问，每个询问给定一些关键点，需要求这些关键点之间的某些信息。询问数可能很多，但满足所有询问中关键点数量的总和与树的大小同阶。 由于询问数可以非常多，每次无法遍历整棵树，这类题目看似没有办法做，但实际上，我们可以用一种叫做 虚树（virtual tree） 的技术来解决这一问题。 介绍 简单来说，虚树是对一颗有根树中......
Read More

线性基学习笔记

2016-12-12
先说明一点， a i a_i a ​ i ​ ​ 表示一个标量，而加粗的 a i \mathbf{a}_i a ​ i ​ ​ 表示一个向量，以便于区分。 概述 基（basis） 是线性代数中的一个概念，它是......
Read More